كد:
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
typedef char puzzle_t[3][3];
puzzle_t _puzzle_start = { {1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};
puzzle_t _puzzle_stop = { {1, 2, 3},
{4, 0, 5},
{6, 7, 8}
};
struct context_t {
std::list<puzzle_t*> abort_states;
std::list<std::string> solution;
int max_depth;
};
std::ostream& operator<<(std::ostream &s, const puzzle_t &p)
{
for (int y=0; y<3; ++y) {
for (int x=0; x<3; ++x) {
s << (int)p[y][x] << " ";
}
s << std::endl;
}
return s;
}
bool solver_rec(puzzle_t& start, const puzzle_t& stop, int y0, int x0, int depth, context_t &ctx)
{
// enough CPU cycles wasted
if (depth >= ctx.max_depth) return false;
// is the actual start a abort state?
for (std::list<puzzle_t*>::iterator it = ctx.abort_states.begin(); it != ctx.abort_states.end(); ++it) {
bool abort = true;
for (int y=0; y<3; ++y) {
for (int x=0; x<3; ++x) {
if (start[y][x] != (**it)[y][x]) abort=false;
}
}
// this state will be checked by on of the parents, anyhow
if (abort) {
return false;
}
}
// are we done?
bool done = true;
for (int yy=0; yy<3; ++yy) {
for (int xx=0; xx<3; ++xx) {
if (start[yy][xx] != stop[yy][xx]) done= false;
}
}
if (done) return true;
// add this state to the list of abort states
// it safe to push_front an stack objectpointer
// as we remove it again before stack is unwinded
// or never ever touch it again
puzzle_t p;
memcpy(p, start, sizeof(p));
ctx.abort_states.push_front(&p);
for (int yy=0; yy<3; ++yy) {
for (int xx=0; xx<3; ++xx) {
// if the move is possible, take it
if (((yy+1 == y0) || (yy-1 == y0)) && (xx == x0)) {
std::swap(start[yy][xx], start[y0][xx]);
if (solver_rec(start, stop, yy, x0, depth+1, ctx)) {
std::stringstream s;
s << depth << ". tile " << yy << "/" << x0;
ctx.solution.push_back(s.str());
return true;
}
std::swap(start[yy][xx], start[y0][xx]);
}
if (((xx+1 == x0) || (xx-1 == x0)) && (yy == y0)) {
std::swap(start[yy][x0], start[yy][xx]);
if (solver_rec(start, stop, y0, xx, depth+1, ctx)) {
std::stringstream s;
s << depth << ". tile " << y0 << "/" << xx;
ctx.solution.push_back(s.str());
return true;
}
std::swap(start[yy][x0], start[yy][xx]);
}
}
}
// remove the abort state
ctx.abort_states.pop_front();
return false;
};
bool solver(puzzle_t& start, const puzzle_t& stop, int max_depth)
{
context_t ctx;
// search for the 0 element
int y0=-1, x0=-1;
for (int y=0; y<3; ++y) {
for (int x=0; x<3; ++x) {
if (start[y][x] == 0) {
y0 = y;
x0 = x;
break;
}
}
}
assert(y0 != -1);
assert(x0 != -1);
// breath first search, assures that a shortest solution is found
for (ctx.max_depth=0; ctx.max_depth<max_depth; ++(ctx.max_depth)) {
if (solver_rec(start, stop, y0, x0, 1, ctx)) {
std::cout << "---SOLUTION---" << std::endl;
for (std::list<std::string>::reverse_iterator it = ctx.solution.rbegin(); it != ctx.solution.rend(); ++it) {
std::cout << *it << std::endl;
}
return true;
}
}
return false;
}
int main(int argc, char**argv)
{
// 3 argument == max_depth
if (!solver(_puzzle_start, _puzzle_stop, 20)) {
std::cout << "--- NO SOLUTION ---" << std::endl;
}
return 0;
}