Last active
December 12, 2015 06:38
-
-
Save sithhell/4731009 to your computer and use it in GitHub Desktop.
Example for a fully asynchronous solver for the fifteen puzzle. This example is explain at: http://stellar.cct.lsu.edu/?p=877
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Copyright (c) 2013 Thomas Heller | |
// Copyright (c) 2013 Andreas Schaefer | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See accompanying | |
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
#include <hpx/hpx_main.hpp> | |
#include <hpx/hpx.hpp> | |
#include <hpx/include/iostreams.hpp> | |
struct fifteen_puzzle | |
{ | |
fifteen_puzzle(std::string const & config) | |
{ | |
for (std::size_t y = 0; y < 4; ++y) | |
{ | |
for(std::size_t x = 0; x < 4; ++x) | |
{ | |
std::size_t idx = y * 4 + x; | |
tiles[idx] = config[idx]; | |
if(tiles[idx] == 'X') | |
{ | |
c_x = x; | |
c_y = y; | |
} | |
} | |
} | |
} | |
std::vector<fifteen_puzzle> next_moves() const | |
{ | |
std::size_t num = 0; | |
std::size_t idx = c_y * 4 + c_x; | |
std::vector<fifteen_puzzle> res; | |
res.reserve(4); | |
if(c_x > 0) | |
{ | |
res.push_back(*this); | |
std::swap(res.back().tiles[idx], res.back().tiles[idx - 1]); | |
--res.back().c_x; | |
++num; | |
} | |
if(c_x < 3) | |
{ | |
res.push_back(*this); | |
std::swap(res.back().tiles[idx], res.back().tiles[idx + 1]); | |
++res.back().c_x; | |
++num; | |
} | |
if(c_y > 0) | |
{ | |
res.push_back(*this); | |
std::swap(res.back().tiles[idx], res.back().tiles[idx - 4]); | |
--res.back().c_y; | |
++num; | |
} | |
if(c_y < 3) | |
{ | |
res.push_back(*this); | |
std::swap(res.back().tiles[idx], res.back().tiles[idx + 4]); | |
++res.back().c_y; | |
++num; | |
} | |
return res; | |
} | |
bool is_solution() const | |
{ | |
for(std::size_t i = 1; i < 15; ++i) | |
{ | |
if((tiles[i-1] + 1) != tiles[i]) | |
{ | |
return false; | |
} | |
} | |
return true; | |
} | |
boost::array<char, 16> tiles; | |
std::size_t c_x; | |
std::size_t c_y; | |
}; | |
std::size_t const max_depth = 6; | |
template <typename Puzzle> | |
bool solve(Puzzle const & p, std::size_t depth) | |
{ | |
if(p.is_solution()) return true; | |
if(max_depth == depth) return false; | |
std::vector<Puzzle> next_moves = p.next_moves(); | |
std::vector<hpx::future<bool> > solve_futures; | |
solve_futures.reserve(next_moves.size()); | |
for(Puzzle const & next : next_moves) | |
{ | |
bool (*solve_fun)(Puzzle const &, std::size_t) = solve; | |
solve_futures.push_back( | |
hpx::async( | |
hpx::util::bind( | |
solve_fun | |
, next | |
, depth+1 | |
) | |
) | |
); | |
} | |
while(!solve_futures.empty()) | |
{ | |
hpx::util::tuple<int, hpx::future<bool> > | |
wait_result = hpx::wait_any(solve_futures); | |
std::size_t idx = hpx::util::get<0>(wait_result); | |
std::size_t res = hpx::util::get<1>(wait_result).get(); | |
solve_futures.erase(solve_futures.begin() + idx); | |
if(res) | |
{ | |
if(!solve_futures.empty()) | |
{ | |
hpx::wait(solve_futures); | |
} | |
return true; | |
} | |
} | |
return false; | |
} | |
int main() | |
{ | |
fifteen_puzzle puzzle( | |
"Xabc" | |
"efgd" | |
"ijkh" | |
"mnol" | |
); | |
if(solve(puzzle, 0)) | |
{ | |
hpx::cout << "Solution found!\n" << hpx::flush; | |
} | |
else | |
{ | |
hpx::cout << "No solution found!\n" << hpx::flush; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment