Skip to content

Instantly share code, notes, and snippets.

@sithhell sithhell/15_puzzle.cpp
Last active Dec 12, 2015

Embed
What would you like to do?
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
You can’t perform that action at this time.