15Puzzle (This is
another
failure)
Honestly I really don't know how many edition I have tried. I have commented out more lines than remained.
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.
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):
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:
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.
There are few points to mention.
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;
}