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