Example for a fully asynchronous solver for the fifteen puzzle. This example is explain at: http://stellar.cct.lsu.edu/?p=877
// 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