Example for a fully asynchronous solver for the fifteen puzzle. This example is explain at: http://stellar.cct.lsu.edu/?p=877

15_puzzle.cpp

//  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;
}