failure

15Puzzle (This is another failure)

    A. second? Edition

    Honestly I really don't know how many edition I have tried. I have commented out more lines than remained.

    B.The problem

Do you know the problem? 4x4 board, 15 nodes with index number, scrambled, you need to move them around with

one space node so that the index number of each node match its position index.

My problem is like following:

1 | 2 | 5 | 3
¡¡ | 7 | 6 | 4
9 | 8 | 10 | 11
12 | 13 | 14 | 15

¡¡

1. This is current position I run into.

1 | 2 | 5 | 3
¡¡ | 9 | 6 | 4
7 | 8 | 10 | 11
12 | 13 | 14 | 15

¡¡

¡¡

2. This is target position I want to reach.

¡¡

1 | 2 | 5 | 3
9 | 7 | 6 | 4
¡¡ | 8 | 10 | 11
12 | 13 | 14 | 15

¡¡

¡¡

3. This is the position I stuck. You see I want the 9 to go up and then the space block is stuck there! As I

set all finished square 8,10,11,12,13,14,15 as restricted area and 9 is current "highLight" square which also

cannot be touched by space block. The following page is extracted from that genius's web and I don't bother to

read it as my mind is already numbed after more 30hours struggle and torture of both coding and hungry.

¡¡

C.The idea of program
¡¡

After simple Depth-First-Search failed, I have to consider a more effective algorithm. This is actually from

following page which I googled.

15 Puzzle: Technical stuff | ¡¡

¡¡

"Artificial intelligence (AI) is a process by which mechanical devices are able to perform tasks which, when they are performed by humans, require some thought." Paul Y. Gloess, Understanding Artificial Intelligence, 1981

I'm not sure I would go so far as to call the solution algorithm of this game artificial intelligence. The irony of it is, the 15 puzzle doesn't take much intelligence at all to solve. It was after figuring this out that I knew I could make the applet self-solving. (I've seen it done with the full "decision-tree" artillery as well, but why bother?) And once you know how it works, it becomes pretty boring to play. A monkey could do it. One with a bit of discipline, anyway. I'll explain the technique here, so read no further if you want to keep the legendary 15 puzzle a challenge.

The "trick" is to break it up into smaller sub-problems that are trivial to solve, or become trivial to solve if you do them in the right order. We'll take it from a human perspective first. Start with getting the 1 and 2 into their proper places. 1 first, then 2. After you're done with that, you don't put 3 right next to them. You place it in the top right corner, and then the 4 right below, like this:

¡¡

1 | 2 |  | 3
14 | 12 | 6 | 4
5 | 11 | 13 | 7
15 | 9 | 10 | 8

After placing the hole between the 2 and 3, you can then drag both 3 and 4 along into their proper positions. That takes care of the first row. The second one works exactly the same. 5 and 6 first, followed by 7 out on the right edge with the 8 just below it, and then you are halfway done.

The final two rows are easiest to solve if you work them through sideways, just like you did with the 3 and 4 and the 7 and 8 earlier. Place the 13 and 9 like this:

1 | 2 | 3 | 4
5 | 6 | 7 | 8
13 | 9 | 15 | 12
| 14 | 11 | 10

Use the hole to drag them both along into their proper column. Then you do the same with the 14 and the 10. After that, you only have the bottom right 2x2 square left. You solve it by simply rotating the pieces, which is done by moving the hole around inside that square one or more full rotations. It

¡¡

¡¡

doesn't matter which way.

¡¡

1 | 2 | 3 | 4
5 | 6 | 7 | 8
9 | 10 | 12 | 15
13 | 14 |  | 11

This sounds a little too unproblematic -- and it is. Every now and then you won't be able to pull the drag-along trick off directly. We'll take the 3 and 4 as an example. Odds are that when you have put the 3 in the top right corner, the 4 happens to be in such an awkward place that you can't move it to the position below the 3 without moving the 3 (or the 2) as well. Like this, or something similar (I'm only showing the top right 2x3 pieces):

4 | 3
| 9
12 | 15

But this is perfectly OK. You just need to send the 4 on a little detour down the left-hand side of this 2x3 group, and then up on the right-hand side, to dock with the 3. These are the steps:

¡¡

| 3
4 | 9
12 | 15

3 |
4 | 9
12 | 15

3 | 9
| 15
4 | 12

3 | 9
15 | 12
| 4

3 | 9
12 |
15 | 4

| 3
12 | 9
15 | 4

12 | 3
9 |
15 | 4

12 | 3
9 | 4
15 |

You do the same thing if you run into trouble with the 7 and 8, the 9 and 13 or the 10 and 14, except that in the last two cases you have to think sideways, or lean your head 90 degrees to the left, whichever feels easier.

This description is of no real use to a computer yet, however. We need to break it up into even smaller sub-problems. Like how do you move a piece from its current position to a given destination without disturbing any of the pieces you have already aligned? How do you select a proper path? It turns out that, given the above order, you just have to move it sideways and then up. This will always work, with the exception of the "awkward" cases. They, on the other hand, are few enough to be handled mechanically using some kind of lookup table.

The next level of sub-problems is how to move the piece each step along a selected path. This is, of course, done by moving the hole to the next step position and then moving the piece into the hole. So how to you select a path for the hole? Well, to begin with, you should mark the already aligned pieces as "obstacles". Then you break this problem up one final time. First you select a path for the hole to one of the (up to) 8 neighboring positions of the target piece. Take one step at a time, horizontally or vertically, in whichever proper direction isn't blocked.

Once you are in a neighboring position, you know that the target place of the hole is just in another neighboring position. To get to it, pick either the clockwise or counter-clockwise path that is the shortest and/or not blocked by anything. Formulating an algorithm for this is rather easy. Check the source code on the ingredients page for details.

¡¡

    D.The major functions

    There are few points to mention.

    ¡¡

    E.Further improvement

    ¡¡

    F.File listing

    1. node.h

    2. node.cpp

    3. main.cpp (main)

    ¡¡

    file name: node.h

    #include <stdio.h>

    const int BoardSize=4;
    const int MaxNodesLength=BoardSize*2-1;
    const int MaxBoardSize=10;
    const int MinimumRotateSize=2;

    enum Direction
    {
    	U, D , L , R, None
    };

    enum Position
    {
    	Right, DownRight, Down, DownLeft, Left, UpLeft, Up, UpRight
    };

    class Puzzle;

    class Coord
    {
    	friend class Puzzle;
    private:
    	int row;
    	int col;
    public:
    	const Coord& operator=(const Coord& rhs);
    	bool operator==(const Coord& rhs);
    	bool operator!=(const Coord& rhs);
    	bool neighbour(const Coord& rhs);
    };

    class Puzzle
    {
    private:
    	int board[MaxBoardSize][MaxBoardSize];
    	bool restricted[MaxBoardSize][MaxBoardSize];
    	int size;//this is the original size
    	//int bound;//this is the current virtual size
    	Coord space;
    	Coord highLight;
    	//void setHighLight();
    	void moveSpace(const Coord& dest);
    	void swapNode(Coord& lhs, Coord& rhs);
    	void moveHighLight(const Coord& dest);
    	//Direction checkPosition(const Coord& dest);
    	//Coord nextMove(const Coord& source, const Coord& dest);
    	Coord nextNode(const Coord& source, Direction dir);
    	//Position relativePos(const Coord& source, const Coord& center);
    	bool rowMove(Coord& source, int destRow);
    	bool colMove(Coord& source, int destCol);
    	bool testRestrict(const Coord& source, Direction dir);
    	void doMoveNode(Coord& source, Direction dir);
    	void moveNode(Coord& source, const Coord& dest);
    	bool testMove(const Coord& source, Direction dir);
    	void doRotate(int r);
    	Coord nextMove(const Coord& source, const Coord& center, bool clockWise);
    	Coord findNumber(int number);
    public:
    	void setBoard(int* array, int theSize);
    	void display();
    	void solve();
    };

    file name: node.cpp

    #include "node.h"
    #include <stdio.h>
    #include <math.h>

    char dirStr[4]={'U', 'D' , 'L' , 'R'};

    bool Puzzle::testMove(const Coord& source, Direction dir)
    {
    	Coord next;
    	next=nextNode(source, dir);
    	return next.row>=0&&next.row<size&&next.col>=0&&next.col<size;

    	/*
    	bool result;
    	switch (dir)
    	{
    	case U:
    		result= source.row-1>0;
    		break;
    	case D:
    		result= source.row+1<size;
    		break;
    	case L:
    		result= source.col-1>0;
    		break;
    	case R:
    		result= source.col+1<size;
    		break;
    	}
    	return result;
    	*/
    }

    Coord Puzzle::nextNode(const Coord& source, Direction dir)
    {
    	Coord result;
    	result=source;
    	switch (dir)
    	{
    	case U:
    		result.row--;
    		break;
    	case D:
    		result.row++;
    		break;
    	case L:
    		result.col--;
    		break;
    	case R:
    		result.col++;
    		break;
    	}
    	return result;
    }

    bool Puzzle::testRestrict(const Coord& source, Direction dir)
    {
    	Coord next;
    	if (!testMove(source, dir))
    	{
    		return false;
    	}
    	next=nextNode(source, dir);
    	return !restricted[next.row][next.col];

    }

    void Puzzle::doMoveNode(Coord& source, Direction dir)
    {
    	Coord next;
    	next = nextNode(source, dir);
    	swapNode(source, next);
    }

    Direction opposite(Direction dir)
    {
    	Direction result;
    	switch(dir)
    	{
    	case U:
    		result=D;
    		break;
    	case D:
    		result=U;
    		break;
    	case R:
    		result=L;
    		break;
    	case L:
    		result=R;
    		break;
    	}
    	return result;
    }

    void Puzzle::moveSpace(const Coord& dest)
    {
    	bool isNeighbour=false;
    	bool clockWise=true;
    	Coord next;
    	while (space!=dest)
    	{
    		display();
    		if (isNeighbour)
    		{
    			next=nextMove(space, highLight, clockWise);
    			if (restricted[next.row][next.col])
    			{
    				clockWise=!clockWise;
    			}
    			else
    			{
    				swapNode(space, next);
    			}
    		}
    		else
    		{
    			if (!rowMove(space, dest.row))
    			{
    				if (space.neighbour(highLight))
    				{
    					isNeighbour=true;
    				}
    				else
    				{
    					if (!colMove(space, dest.col))
    					{
    						if (space.neighbour(highLight))
    						{
    							isNeighbour=true;
    						}
    					}
    				}
    			}
    			else
    			{
    				if (!colMove(space, dest.col))
    				{
    					if (space.neighbour(highLight))
    					{
    						isNeighbour=true;
    					}
    				}
    			}
    		}

    		/*
    			if (space.col!=0)
    			{
    				colMove(space, space.col-1);
    			}
    			else
    			{
    				colMove(space, space.col+1);
    			}
    			rowMove(space, dest.row);
    			colMove(space, dest.col);

    		/*
    		display();
    		if (!rowMove(space, dest.row))
    		{
    			if (space.col!=0)
    			{
    				colMove(space, space.col-1);
    			}
    			else
    			{
    				colMove(space, space.col+1);
    			}
    			rowMove(space, dest.row);
    			colMove(space, dest.col);
    			//rowMove(space, dest.row);
    		}
    		else
    		{
    			display();
    			if (!colMove(space, dest.col))
    			{
    				if (space.row!=0)
    				{
    					rowMove(space, space.row-1);
    				}
    				else
    				{
    					rowMove(space, space.row+1);
    				}

    				//rowMove(space, 0);
    				colMove(space, dest.col);
    				rowMove(space, dest.row);
    			}
    		}
    		display();
    		*/
    	}
    }
    	/*
    	while (space.row!=0)
    	{
    		if (!rowMove(space, 0))
    		{
    			if (space.col!=0)
    			{
    				colMove(space, space.col-1);
    			}
    			else
    			{
    				colMove(space, space.col+1);
    			}
    			display();
    		}
    	}
    	while (space.col!=dest.col)
    	{
    		if (!colMove(space, dest.col))
    		{
    			rowMove(space, 1);
    			//colMove(space, dest.col);
    			display();
    		}
    	}
    	while (space.row!=dest.row)
    	{
    		if (!rowMove(space, dest.row))
    		{
    			if (space.col!=0)
    			{
    				colMove(space, space.col-1);
    			}
    			else
    			{
    				colMove(space, space.col+1);
    			}
    			rowMove(space, dest.row);
    			display();
    		}
    	}
    }
    	}
    }
    */

    void Puzzle::moveNode(Coord& source, const Coord& dest)
    {

    	Coord old;
    	if (source==dest)
    	{
    		return ;
    	}
    	Coord next;
    	next=source;

    	while (source.row!=0)
    	{
    		old=source;
    		next.row--;
    		restricted[old.row][old.col]=true;
    		moveSpace(next);
    		swapNode(source, space);
    		restricted[old.row][old.col]=false;
    		next=source;
    	}

    	while (source.col!=dest.col)
    	{
    		old=source;
    		if (source.col<dest.col)
    		{
    			next.col++;
    		}
    		else
    		{
    			next.col--;
    		}
    		restricted[old.row][old.col]=true;
    		moveSpace(next);
    		swapNode(source, space);
    		restricted[old.row][old.col]=false;
    		next=source;
    	}
    	while (source.row!=dest.row)
    	{
    		old=source;
    		next.row++;
    		restricted[old.row][old.col]=true;
    		moveSpace(next);
    		swapNode(source, space);
    		restricted[old.row][old.col]=false;
    		next=source;
    	}

    	//rowMove(source, 0);
    	//colMove(source, dest.col);
    	//rowMove(source, dest.row);
    	/*
    	Direction opposite(Direction dir);
    	Coord last;
    	Direction primary, lastDir=None, dirs[4];//first, second, third, fourth, lastDir=-1;
    	//bool trySide=false, tryThird=false;
    	//int tryCount, tryStep;
    	last=source;//initialize
    	/*
    	if (source.row>dest.row)
    	{
    		first=U;
    		third=D;
    	}
    	else
    	{
    		first=D;
    		third=U;
    	}
    	if (source.col>dest.col)
    	{
    		second=L;
    		fourth=R;
    	}
    	else
    	{
    		second=R;
    		fourth=L;
    	}
    	if (abs(source.row-dest.row)<abs(source.col-dest.col))
    	{
    		//swap, primary as hold
    		primary=first;//hold
    		first=second;
    		second=primary;
    	}
    	*/
    	/*
    	if (source.row>dest.row)
    	{
    		dirs[0]=U;
    		dirs[2]=D;
    	}
    	else
    	{
    		dirs[0]=D;
    		dirs[2]=U;
    	}
    	if (source.col>dest.col)
    	{
    		dirs[1]=L;
    		dirs[3]=R;
    	}
    	else
    	{
    		dirs[1]=R;
    		dirs[3]=L;
    	}
    	if (abs(source.row-dest.row)<abs(source.col-dest.col))
    	{
    		//swap, primary as hold
    		primary=dirs[0];//hold
    		dirs[0]=dirs[1];
    		dirs[1]=primary;
    	}
    	while (source!=dest)
    	{
    		/*
    		if (source.row>dest.row)
    		{
    			first=U;
    		}
    		else
    		{
    			first=D;
    		}
    		if (source.col>dest.col)
    		{
    			second=L;
    		}
    		else
    		{
    			second=R;
    		}

    		if (testRestrict(source, first))
    		{
    			primary=first;
    		}
    		else
    		{
    			if (testRestrict(source, second))
    			{
    				primary=second;
    			}
    			else
    			{
    				//it means last stock here
    				if (last==source)
    				{
    					primary=third;
    					third=fourth;
    					fourth=primary;
    					primary=first;
    					first=second;
    					second=primary;
    				}
    				else
    				{
    					last=source;
    				}
    				if (testRestrict(source, third))
    				{
    					primary=third;
    				}
    				else
    				{
    					primary=fourth;
    				}
    			}
    		}

    		for (int i=0; i<4; i++)
    		{
    			if (dirs[i]!=lastDir)
    			{
    				if (testRestrict(source, dirs[i]))
    				{
    					primary=dirs[i];
    					lastDir=opposite(dirs[i]);
    					break;
    				}
    			}
    		}
    		doMoveNode(source, primary);

    		display();
    	}
    	*/
    }

    /*
    enum SpacePosition
    {
    	//relative to destination
    	Left, Right,//these are space and highlight not adjacent
    	Up, Down,  //these are space and highlight not adjacent
    	RowCol,//nothing is same, neither space and highlight is adjacent
    	SameRowLeft, SameRowRight,//these are
    	SameColUp, SameColDown,
    */

    /*

    Direction Puzzle::checkPosition(const Coord& dest)
    {
    	bool isLineUp;

    	isLineUp=(space.row==highLight.row&&space.row==dest.row)||
    		(space.col==highLight.col&&space.col==dest.col);
    	if (isLineUp)
    	{
    		if (space.row==dest.row)
    		{
    			//either up or down, default U
    			if (space.row!=0)
    			{
    				return U;
    			}
    			else
    			{
    				return D;
    			}
    		}
    		else
    		{
    			//must have same col, default is L
    			if (space.col!=0)
    			{
    				return L;
    			}
    			else
    			{
    				return R;
    			}
    		}
    	}
    	else
    	{
    		if (space.row==highLight.row)
    		{
    			//space and dest must have different row
    			if (space.row>dest.row)
    			{
    				return U;
    			}
    			else
    			{
    				return D;
    			}
    		}
    		else
    		{
    			//space and highLight have same col because they are
    			//adjacent, and space and dest must have different col
    			if (space.col>dest.col)
    			{
    				return L;
    			}
    			else
    			{
    				return R;
    			}
    		}
    	}
    }
    }
    	/*

    	bool isAdjacent;
    	bool isLineUp;
    	isAdjacent=space.neighbour(highLight);
    	if (!isAdjacent)
    	{
    		if (space.row==dest.row)
    		{
    			//this means it must be either L or R
    			if (space.col>dest.col)
    			{
    				return L;
    			}
    			else
    			{
    				return R;
    			}
    		}
    		else
    		{
    			//this means we start from U or D
    			if (space.row>dest.row)
    			{
    				return U;
    			}
    			else
    			{
    				return D;
    			}
    		}
    	}
    	else
    	{
    		isLineUp=(space.row==highLight.row&&space.row==dest.row)||
    			(space.col==highLight.col&&space.col==dest.col);
    		if (isLineUp)
    		{
    			if (space.row==dest.row)
    			{
    				//either up or down, default U
    				if (space.row!=0)
    				{
    					return U;
    				}
    				else
    				{
    					return D;
    				}
    			}
    			else
    			{
    				//must have same col, default is L
    				if (space.col!=0)
    				{
    					return L;
    				}
    				else
    				{
    					return R;
    				}
    			}
    		}
    		else
    		{
    			if (space.row==highLight.row)
    			{
    				//space and dest must have different row
    				if (space.row>dest.row)
    				{
    					return U;
    				}
    				else
    				{
    					return D;
    				}
    			}
    			else
    			{
    				//space and highLight have same col because they are
    				//adjacent, and space and dest must have different col
    				if (space.col>dest.col)
    				{
    					return L;
    				}
    				else
    				{
    					return R;
    				}
    			}
    		}
    	}
    }

    */
    void Puzzle::setBoard(int * array, int theSize)
    {
    	size=theSize;
    	//bound=size;//this is the default.
    	for (int i=0; i<size; i++)
    	{
    		for (int j=0; j<size; j++)
    		{
    			if (array[i*size+j]==0)
    			{
    				space.row=i;
    				space.col=j;
    			}
    			board[i][j]=array[i*size+j];
    			restricted[i][j]=false;
    		}
    	}
    }

    void Puzzle::display()
    {
    	printf("the size of board is %d\n", size);
    	for (int i=0; i<size; i++)
    	{
    		for(int j=0; j<size; j++)
    		{
    			printf("%2d\t", board[i][j]);
    		}
    		printf("\n");
    	}
    }

    void Puzzle::swapNode(Coord& lhs, Coord& rhs)
    {
    	int number;
    	Coord hold;
    	//first swap numbers
    	number=board[lhs.row][lhs.col];
    	board[lhs.row][lhs.col]=board[rhs.row][rhs.col];
    	board[rhs.row][rhs.col]=number;
    	hold=lhs;
    	lhs=rhs;
    	rhs=hold;
    }

    /*
    Position Puzzle::relativePos(const Coord& source, const Coord& center)
    {
    	int r, c;
    	r=source.row-center.row;
    	c=source.col-center.col;
    	if (r==0)
    	{
    		if (c==1)
    		{
    			return Right;
    		}
    		else
    		{
    			//must be -1
    			return Left;
    		}
    	}
    	else
    	{
    		if (r==-1)
    		{
    			if (c==0)
    			{
    				return Up;
    			}
    			else
    			{
    				if (c==-1)
    				{
    					return UpLeft;
    				}
    				else
    				{
    */

    Coord Puzzle::nextMove(const Coord& source, const Coord& center, bool clockWise)
    {
    	Coord next;
    	next=source;
    	int offset=clockWise?-1:1;

    	if (next.row>center.row)
    	{
    		//test to see if clockwise , col reach the limit
    		if (abs(next.col+offset-center.col)==2)
    		{
    			next.row--;//col reach the limit, col unchanged
    		}
    		else
    		{
    			next.col+=offset;
    		}
    	}
    	else
    	{
    		if (next.row<center.row)
    		{
    			if (abs(next.col-offset-center.col)==2)
    			{
    				next.row++;
    			}
    			else
    			{
    				next.col-=offset;
    			}
    		}
    		else
    		{
    			//row==row
    			if (next.col>center.col)
    			{
    				next.row-=offset;
    			}
    			else
    			{
    				next.row+=offset;
    			}
    		}
    	}
    	return next;
    }
    /*

    void Puzzle::rowMove(int destRow)
    {

    }

    void Puzzle::moveSpace(const Coord& dest)
    {
    	/*
    	bool clockWise=highLight.col>=highLight.row;
    	if (clockWise)
    	{
    		if (highLight.row!=dest.row)
    		{
    			if (highLight.row<dest.row)
    			{
    				colMove(dest.row);
    				rowMove(dest.col);
    			}
    			else
    			{
    				colMove(dest.row+1);
    				if (dest.col==0)
    				{
    					rowMove(1);
    				}
    				else
    				{
    					rowMove(dest.col-1);
    				}
    				colMove(dest.row);
    				rowMove(dest.col);
    			}

    		}
    		else
    		{
    			if (dest.row==0)
    			{
    				colMove(1);
    			}
    			else
    			{
    				colMove(dest.row-1);
    			}
    			rowMove(dest.col);
    			colMove(dest.row);
    		}
    	}
    	else
    	{
    		if (highLight.col!=dest.col)
    		{
    			if (highLight.col<dest.col)
    			{
    				rowMove(dest.col);
    				colMove(dest.row);
    			}
    			else
    			{

    		}
    		else
    		{
    			if (dest.col==0)
    			{
    				rowMove(1);
    			}
    			else
    			{
    				rowMove(dest.col-1);
    			}
    			colMove(dest.row);
    			rowMove(dest.col);
    		}
    	}

    	Coord next;
    	Direction dir;
    	while (!(space==dest))//I only overload the ==
    	{
    		dir=checkPosition(dest);
    		next=space;
    		switch (dir)
    		{
    		case U:
    			next.row--;
    			break;
    		case D:
    			next.row++;
    			break;
    		case L:
    			next.col--;
    			break;
    		case R:
    			next.col++;
    			break;
    		}
    		swapNode(next, space);//swap space with next
    	}

    }
    */

    //this is usually within boundary, so move freely
    /*
    Coord Puzzle::nextMove(const Coord& source, const Coord& dest)
    {
    	Coord next;
    	next=source;
    	if (source.row==dest.row)
    	{
    		if (source.col>dest.col)
    		{
    			next.col--;
    		}
    		else
    		{
    			next.col++;
    		}
    	}
    	else
    	{
    		if (source.row>dest.row)
    		{
    			next.row--;
    		}
    		else
    		{
    			next.row++;
    		}
    	}
    	return next;
    }
    */

    Coord Puzzle::findNumber(int number)
    {
    	Coord result;
    	for (int i=0; i<size; i++)
    	{
    		for (int j=0; j<size; j++)
    		{
    			if (board[i][j]==number)
    			{
    				result.row=i;
    				result.col=j;
    				break;
    			}
    		}
    	}
    	return result;
    }

    void Puzzle::solve()
    {
    	Coord dest;
    	//bool clockWise=dest.col>=dest.row;
    	int number;
    	for (int i=size-1; i>=2; i--)
    	{
    		for (int j=size-1; j>=0; j--)
    		{
    			if (i>=MinimumRotateSize&&j>=MinimumRotateSize)
    			{
    				number=i*size+j;
    				dest.row=i;
    				dest.col=j;

    			}
    			else
    			{
    				if (j==1)
    				{
    					number=i*size+0;//the small number first
    					dest.row=i;
    					dest.col=j;
    				}
    				else
    				{
    					number=i*size+1;
    					dest.row=i-1;
    					dest.col=j+1;
    				}

    			}
    			highLight=findNumber(number);
    			moveHighLight(dest);
    			restricted[dest.row][dest.col]=true;
    			display();
    			if (j==0)
    			{
    				doRotate(i);
    			}
    			display();

    		}
    	}
    }

    void Puzzle::doRotate(int r)
    {
    	Coord dest, source;
    	dest.row=r;
    	dest.col=0;
    	source.row=r;
    	source.col=1;
    	//moveNode(space, dest);
    	moveSpace(dest);
    	swapNode(space, source);
    	source.row=r-1;
    	source.col=1;
    	swapNode(space, source);
    	restricted[r][0]=restricted[r][1]=true;
    	restricted[r-1][1]=false;
    }

    void Puzzle::moveHighLight(const Coord& dest)
    {
    	Coord old;
    	if (highLight.neighbour(dest))
    	{
    		old=highLight;
    		restricted[old.row][old.col]=true;
    		moveSpace(dest);
    		restricted[old.row][old.col]=false;
    		swapNode(highLight, space);

    		return;
    	}
    	moveNode(highLight, dest);
    /*
    	Coord last, next;
    	Direction primary, first, second, third, fourth;
    	//bool trySide=false, tryThird=false;
    	//int tryCount, tryStep;
    	last=highLight;//initialize
    	if (highLight.row>dest.row)
    	{
    		first=U;
    		third=D;
    	}
    	else
    	{
    		first=D;
    		third=U;
    	}
    	if (highLight.col>dest.col)
    	{
    		second=L;
    		fourth=R;
    	}
    	else
    	{
    		second=R;
    		fourth=L;
    	}
    	if (abs(highLight.row-dest.row)<abs(highLight.col-dest.col))
    	{
    		//swap, primary as hold
    		primary=first;//hold
    		first=second;
    		second=primary;
    	}

    	while (highLight!=dest)
    	{
    		if (testRestrict(highLight, first))
    		{
    			primary=first;
    		}
    		else
    		{
    			if (testRestrict(highLight, second))
    			{
    				primary=second;
    			}
    			else
    			{
    				//it means last stock here
    				if (last==highLight)
    				{
    					primary=third;
    					third=fourth;
    					fourth=primary;
    					primary=first;
    					first=second;
    					second=primary;
    				}
    				else
    				{
    					last=highLight;
    				}
    				if (testRestrict(highLight, third))
    				{
    					primary=third;
    				}
    				else
    				{
    					primary=fourth;
    				}
    			}
    		}
    		//set highlight as restricted first for space to move
    		restricted[highLight.row][highLight.col]=true;
    		//doMoveNode(source, primary);
    		next=nextNode(highLight, primary);
    		moveNode(space, next);
    		restricted[highLight.row][highLight.col]=false;
    		swapNode(highLight, space);
    		display();
    	}
    */
    }

    bool Puzzle::colMove(Coord& source, int destCol)
    {
    	Coord next;
    	int offset;
    	next=source;
    	if (source.col<destCol)
    	{
    		offset=1;
    	}
    	else
    	{
    		offset=-1;
    	}

    	while (source.col!=destCol)
    	{
    		next.col+=offset;
    		if (restricted[next.row][next.col])
    		{
    			return false;
    		}
    		swapNode(source, next);
    	}
    	return true;
    }

    bool Puzzle::rowMove(Coord& source, int destRow)
    {
    	Coord next;
    	int offset;
    	next=source;
    	if (source.row<destRow)
    	{
    		offset=1;
    	}
    	else
    	{
    		offset=-1;
    	}
    	while (source.row!=destRow)
    	{
    		next.row+=offset;
    		if (restricted[next.row][next.col])
    		{
    			return false;
    		}
    		swapNode(source, next);
    	}
    	return true;
    }

    	/*
    	Coord next;
    	bool outside;
    	//bool onRowEdge, onColEdge;
    	bool lastStep;
    	Coord subDest;
    	//this is trivial
    	if (highLight==dest)
    	{
    		return;
    	}
    	//only one step
    	if (highLight.neighbour(dest))
    	{
    		next = dest;
    		moveSpace(next);
    		swapNode(); //this is space and highLight swap
    		return;
    	}

    	//this sub destination is the temp dest within bound
    	//so I divide the job into two parts, first go to sub destination
    	if (dest.row==bound)
    	{
    		subDest.row--;
    	}
    	else
    	{
    		//dest.col==bound
    		subDest.col--;
    	}
    	//the situation of dest.row==dest.col==bound is also included
    	//because it must be the very first one, so don't worry

    	outside=highLight.row==bound||highLight.col==bound;
    	//onRowEdge=highLight.row==bound-1;
    	//onColEdge=highLight.col==bound-1;

    	//first move within boundary
    	if (outside)//go back for sure
    	{
    		next=highLight;
    		if (highLight.row==bound)
    		{
    			next.row--;
    		}
    		else
    		{
    			//it must be col
    			next.col--;
    		}
    		moveSpace(next);
    		swapNode(); //this is space and highLight swap
    	}
    	while (!(highLight==subDest))
    	{
    		next=nextMove(highLight, subDest);
    		moveSpace(next);
    		swapNode(); //this is space and highLight swap
    	}

    	}
    	//now it is at sub destination
    	while (!(highLight==dest))
    	{
    		next=nextMove(highLight, dest);
    		moveSpace(next);
    		swapNode(); //this is space and highLight swap
    	}
    	*/

    //assignment of coord
    const Coord& Coord::operator =(const Coord& rhs)
    {
    	row=rhs.row;
    	col=rhs.col;
    	return *this;
    }

    bool Coord::operator !=(const Coord& rhs)
    {
    	return !(this->operator==(rhs));
    }

    bool Coord::operator ==(const Coord& rhs)
    {
    	if (row==rhs.row&&col==rhs.col)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }

    bool Coord::neighbour(const Coord& rhs)
    {
    	//next row
    	if (abs(row-rhs.row)==1)
    	{
    		return col==rhs.col;
    	}
    	else
    	{
    		//same row
    		if (row==rhs.row)
    		{
    			//next col
    			return abs(col-rhs.col)==1;
    		}
    		else
    		{
    			//nothing
    			return false;
    		}
    	}
    }

    file name: main.cpp (main)

    #include <stdio.h>
    #include "node.h"

    int boards[BoardSize][BoardSize]=
    {
    	{1, 5,   2,  3 },
    	{4, 10,   0,  7 },
    	{8, 9,    6, 11},
    	{12, 13, 14,  15}
    };

    int main()
    {
    	Puzzle P;
    	P.setBoard((int*)boards, BoardSize);
    	P.display();
    	P.solve();
    	P.display();
    	return 0;
    }

    The result is like following:

    failure!!!!