# 15 puzzle and A-Star

I heard that A-Star can be used to solve 15 Puzzle. Can anyone show me how to do this in details!?
###### Who is Participating?

x

Commented:
Here is the code I wrote when I was a 1'st degree student
in AI course, It implements A* on 8-puzzle...
The puzzle is represented by a LONG type 9 digits number.

As the code is self documented,

Compiles welll on VC6...

#include <math.h>
#include <iostream.h>
#define MaxSize 10000
#define NumberOfPuzzles 100

long InitialStates[NumberOfPuzzles]={
396842751      ,241867539      ,139674825      ,194785263      ,657438291
,697234518      ,178943562      ,642513879      ,319267548      ,197485236
,398642157      ,261753489      ,632174859      ,236759814      ,891527463
,463827519      ,853172649      ,283916547      ,538726491      ,756219834
,798562314      ,138476925      ,692384175      ,189276354      ,793148256
,861327954      ,287359461      ,426583197      ,231596478      ,652871349
,253476198      ,724368591      ,394615872      ,592138674      ,218753649
,784691235      ,964712358      ,854639271      ,957841623      ,431782659
,987246513      ,985741623      ,916845237      ,295176384      ,741962538
,954361827      ,236148957      ,675491238      ,397651248      ,873145269
,197634825      ,178345296      ,672594138      ,378294561      ,934867512
,593468217      ,147623985      ,394865721      ,534897621      ,928173456
,657482139      ,256794138      ,324981756      ,274169583      ,761928543
,271693485      ,276958431      ,251837694      ,857296341      ,642193785
,945278631      ,674529381      ,156347829      ,584291763      ,356872149
,851372649      ,392185467      ,342859176      ,586429713      ,597463281
,296437185      ,239518647      ,263518479      ,642318957      ,127435986
,941823567      ,124369875      ,147586329      ,938264175      ,735689241
,431675892      ,213698475      ,625187439      ,978124563      ,648293175
,379265841      ,359487261      ,973182546      ,584327169      ,793256418
};

class node
{
public:
long puzzle;
int val;
bool WasOpened;
int TreeLevel;
};

class puzzle
{
int WhereIsDigitInNum(int,long);
node list[MaxSize];
int ListIndex, CurrentTreeLevel;
long original, goal;
int MDistance(long,long);
void ReturnSons(long,long&,long&,long&,long&);
long swap(long, int, int);
void SolvePuzzle();
void InsertToList(long,long,long,long);
long FindBest();
//int LinerConflict(long);
public:
puzzle();
};

puzzle::puzzle()
{
int i;
float AvPath=0, AvListIndex=0;

goal=123456789;

for (i=0; i<NumberOfPuzzles; i++)
{
ListIndex=0;
CurrentTreeLevel=-1;                        // first level is zero...

original=InitialStates[i];
cout << "Puzzle: " << i+1 << '\t';
SolvePuzzle();

AvPath+=CurrentTreeLevel;
AvListIndex+=ListIndex;
}

AvPath/=NumberOfPuzzles;
AvListIndex/=NumberOfPuzzles;

cout << endl << "Average path: " << AvPath << endl;
cout << "Average Num of Nodes: " << AvListIndex << endl;
}

void puzzle::SolvePuzzle()
{
long CurrentNum,s1,s2,s3,s4;
CurrentNum=original;

InsertToList(CurrentNum,0,0,0);

while (CurrentNum!=goal && ListIndex<MaxSize-4)
{
CurrentNum=FindBest();
ReturnSons(CurrentNum, s1, s2, s3, s4);
InsertToList(s1, s2, s3, s4);
}

if (CurrentNum!=goal)
cout << "Fail" << endl;
else
cout << "Success" << '\t';

cout << ListIndex << '\t';
cout << CurrentTreeLevel << endl;
}

long puzzle::FindBest()
{
int min, i, j, mini;
bool found=false;
// set the first minimal value
for (i=0; i<ListIndex && !found; i++)
if (list[i].WasOpened==false)
{
found=true;
min=list[i].val;
mini=i;
}

// search the most minimal value
for (j=i; j<ListIndex; j++)
if ((list[j].val<=min) && (list[j].WasOpened==false))
{
min=list[j].val;
mini=j;
}

list[mini].WasOpened=true;
CurrentTreeLevel=list[mini].TreeLevel;

return list[mini].puzzle;
}

void puzzle::InsertToList(long a,long b,long c,long d)
{
long arr[4];
int index=0, i;
bool found;

if (a)
{
arr[index]=a;
index++;
}
if (b)
{
arr[index]=b;
index++;
}
if (c)
{
arr[index]=c;
index++;
}
if (d)
{
arr[index]=d;
index++;
}

index--;
while (index>=0)
{
found=false;
for (i=0; i<ListIndex && !found; i++)
if (arr[index]==list[i].puzzle)
found=true;

if ((found && CurrentTreeLevel+1+MDistance(arr[index],goal)<list[i-1].val) || (!found))
{
list[ListIndex].puzzle=arr[index];
list[ListIndex].WasOpened=false;
list[ListIndex].TreeLevel=CurrentTreeLevel+1;
list[ListIndex].val=list[ListIndex].TreeLevel+MDistance(arr[index],goal);
ListIndex++;
}
index--;
}
}

long puzzle::swap(long num,int a, int b)
{
long v[10];
int i, temp;

for (i=9; i>=1; i--)
{
v[i]=num%10;
num/=10;
}

temp=v[a];
v[a]=v[b];
v[b]=temp;

num=0;
for (i=1; i<=9; i++)
{
num*=10;
num+=v[i];
}

return num;
}

int puzzle::WhereIsDigitInNum(int digit,long num)
{
bool found=false;
int DigitFromNum, pos=9;

while (!found && num)
{
DigitFromNum=num%10;
if (digit==DigitFromNum)
found=true;
else
{
pos--;
num/=10;
}
}

return pos;
}

void puzzle::ReturnSons(long num,long& sr,long& sl,long& su,long& sd)
{
int SpacePos;
SpacePos=WhereIsDigitInNum(1,num);

// shift with right
if (SpacePos%3==0)
sr=0;
else
sr=swap(num,SpacePos,SpacePos+1);

// shift with left
if (SpacePos%3==1)
sl=0;
else
sl=swap(num,SpacePos,SpacePos-1);

// shift with upper
if (SpacePos<4)
su=0;
else
su=swap(num,SpacePos,SpacePos-3);

// shift with lower
if (SpacePos>6)
sd=0;
else
sd=swap(num,SpacePos,SpacePos+3);
}

int puzzle::MDistance(long org, long tar)
{
int i,MSum=0,OrgPos,TarPos,OrgRow,TarRow,OrgLine,TarLine;
for (i=2; i<=9; i++)
{
OrgPos=WhereIsDigitInNum(i,org);
TarPos=WhereIsDigitInNum(i,tar);
OrgLine=(OrgPos-1)/3;
TarLine=(TarPos-1)/3;

OrgRow=OrgPos%3;
if (OrgRow==0)
OrgRow=3;

TarRow=TarPos%3;
if (TarRow==0)
TarRow=3;

MSum+=abs(OrgLine-TarLine)+abs(OrgRow-TarRow);
}

//MSum+=LinerConflict(org);
return MSum;
}

/*
int puzzle::LinerConflict(long puzzle)
{
int OrgPos,NextPos,OrgRow,NextRow,OrgLine,NextLine,DownPos,DownLine, DownRow,i,r=0;
for (i=2; i<=8; i++)
{
OrgPos=WhereIsDigitInNum(i,puzzle);
NextPos=WhereIsDigitInNum(i+1,puzzle);
OrgLine=(OrgPos-1)/3;
NextLine=(NextPos-1)/3;

OrgRow=OrgPos%3;
if (OrgRow==0)
OrgRow=3;

NextRow=NextPos%3;
if (NextRow==0)
NextRow=3;

if ((OrgLine==NextLine) && (OrgRow-NextRow==1))
r+=2;

if (i<=6)
{
DownPos=WhereIsDigitInNum(i+3,puzzle);
DownLine=(DownPos-1)/3;

DownRow=DownPos%3;
if (DownRow==0)
DownRow=3;

if ((OrgRow==DownRow) && (OrgLine-DownLine==1))
r+=2;
}

}
return r;
}
*/

void main()
{
puzzle p;
}

0

Commented:
Hi jiminika,

this question is surely worth the 200 points. To answer your question right away: A* *CAN* be used to solve the 15 puzzle. However it might not be the best approach; I'll get to that in a minute.

As this is going to become a bit lengthy let me offer you a table of contents so you don't get lost:
1. Breaking down the problem
2. Dijkstra's algorithm
3. Dijkstra + knowledge -> A*
4. Can you picture this?

All code priveded is optimized for readablity only.

1. Breaking down the problem:

As with all problems you'd like to present to a computer you will have to transform it, so that a machine can 'understand' it. Thus transformation usually means abstraction of the nature of the problem.
Let's go back to the 15 puzzle. There are 4 pieces of information to describe the entire problem. A set of states (S), a set of transitions (T) to move from one state to another, a start state (start), and a goal state (goal).
Set of states (S): this is a machine-readable description of all possible constellations of the puzzle. I'd suggest using a 4x4 array
char tile[16];
to describe the layout, where tile[0] is the top left corner, tile[3] the top right corner, tile[15] the bottom right corner. Fill this array with the respective number of the tile and mark the empty spot with a '0'. This way you have just created the start state (start). Your goal state (goal) is {1, 2, 3, ..., 14, 15, 0}.
Set of transitions (T): this refers to sliding pieces on the board to get from one layout to another. For any state of the puzzle this can be 2, 3, or 4 legal moves (2 at corners, 3 on edges, and 4 on the interior). We'll use
char dir;
for transitions and declare the directions as follows:
right: 00000001b (1)
top: 00000010b (2)
left: 00000100b (4)
bottom: 00001000b (8)
Information on which tile is to be moved can be gathered from the direction code (d) and the current state (cs). Let's say d == 4 (left) and cs = { 0, .... } then the 2nd tile (tile[1]) is to be moved.
Let's take a step back and see what we have so far: We know WHAT the puzzle looks like (start), we know WHERE we are headed (goal), and we know HOW to walk (set of transitions T). Still with me? Good!

2. Dijkstra's algorithm

With all the WHAT, WHERE, and HOW we still don't know WHICH step at any give puzzle state will get us closer to our goal. There aren't many means to choose from when there is nothing to decide upon, so let's face it: a situation like this calls for brute force. Beginnig with the start state we do the following:
a.) set cs = start
b.) if( cs == goal ) return GOAL_REACHED;
c.) for each legal direction set cs = transform( cs, dir ) and goto b.)
[transform( const char[16]& state, const char dir ) returns new puzzle state after sliding the appropriate tile into the specified direction]
Simplified - and not quite accurate, I admit - this is Dijkstra's algorithm: Check for ALL possibilities until we reach the goal. Cool! We've reached the goal then? Technically speaking, yes, cs == goal. From a human perspective, though, the interest is more towards 'can you tell me how?'. Damn, we forgot the housekeeping. We need some structure to hold information on where we came from.
struct node {
char tile_state[16];
char dir_parent;
};
And we need some means to 'remember' where a possible parent of a parent came from. What about some sort of long term memory that stores all puzzle states we've examined so far? Let's just call it closed (as in 'closed for examination'):
#include <list>
std::list<node> closed;
Let's refine the algorithm above:
a.) node n = {start, 0};
b.) if( n.tile_state == goal ) return solution;
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent = rev_dir( dir ); goto b.); }
Now we have all the information to construct a solution. Starting at goal, we check for equality with start. If not, we retrieve node n from closed, where n.tile_state == cs, and append n.dir_parent to our solution list, ... The list is still doubly inverted. All we have to do is to change the order from back to front and reverse each direction. Voila - here it is.
Well, possibly, but not necessarily. We did not take any precautions to avoid ending up in an endless loop (i.e. moving a tile to the left and moving it to the right again, then left, right, left, right, ...) And possibly we could use the little information we have gathered on our way to speed up calculation. Let's redesign our node structure:
class node {
char tile_state[16];
char dir_parent;
int move_count;
};
move_count is set to 0 for the start node and increased by 1 for each expansion. We'll also be using a short term memory list that holds all nodes open for examination and call it open. Before expanding a node the open list is sorted in ascending order, so we'll expand all nodes whose tile_state can be reached with one move, then those, that can be reached in two moves, and so on.
To finish this section, here is the more complete algorithm in pseudo-code:
a.) node n = { s, 0, 0 }; open.push_back( n );
b.) if( 0 == open.size() ) return FAILED;  // no solution!
c.) open.sort( ASCENDING ); n = open.front(); open.pop_front();
d.) if( n.tile_state == goal ) return solution;
e.) closed.push_back( n );
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
g.) goto b.)

Enough for today, my girlfriend needs attention...

regards,
.:fl0yd:.
0

Commented:
What a night...

Anyway, let's go over what we have so far. With Dijkstra's algorithm we have a - computationally expensive - method to solve problems given a search space (S, T), a start state (start), and the goal state (goal). Btw. this algorithm can be applied to any problem that can be abstracted to search space, start, and goal. Now why is this approach so computationally expensive? Because the algorithm applied is basically dumb, i.e. it doesn't use any means to decide, which transition seems to be the most promising one to take at any given puzzle state.

3. Dijkstra + knowledge -> A*:

To reduce the effort necessary to find a solution we will have to find some means to favor one transition over another at a given state. For the 15 puzzle there is no actual information to gain from looking at the layout, as far as I can see. So we will have to guess which one of any two given states is closer to our goal. Let's call additional information on a problem 'heuristic' (h). One thing we can be sure about the 15 puzzle is, that if
h = number of tiles at wrong locations
we will need at least h moves (at least 1 move for each incorrect tile) to reach the goal. How can we use this information to reduce the amount of searching necessary to find a solution? Let's go back to Dijkstra's algorithm. Instead of sorting our open list with respect to the number of moves taken so far, let's take our estimate on the 'distance' from the goal into account. While Dijkstra's sorting predicate is
f = g (g = costs so far)
we'll use costs + estimate
f = g + h
and call this 'new' algorithm A*. So the difference between Dijkstra's algorithm and A* is, that Dijkstra is searching indifferent in all possible directions whereas A* is searching in favor of those directions, that are presumably closer to the goal. Bare in mind though that our presumtions are based on guessing only.

3.1. Small guess-ology:

It appears to be logical that A* will find a solution faster than Dijkstra if our presumtions are all correct. But what happens if not? What if only some of them are wrong? Let's discover the different degrees of, hmm, wrongness? wrongity? anyone? If our estimated distance is wrong it can be either too large or too small. Overestimating is dangerous in that we may be skipping potential solutions. Understimating is not only harmless, but essential to ensure that the returned solution requires the least number of transitions to be reached.

3.2. It's all in the heuristics:

Let's check the heuristic above against this. It is obvious that if n tiles are in wrong locations it takes n moves at best to reach the solution. Since A* uses the heuristic as a decisive means to cut down computational effort, the heuristic's quality is the key component to success. If it comes close to the actual effort it unleashes A*'s power. In fact, if every guess is correct, i.e. we have a perfect heuristic, A*'s very first try at the puzzle will return the best possible solution. However, our heuristic only returns values in the range of [0..15] and becomes somwhat void after about 100 moves. In the introduction I said that 'it might not be the best approach'. There is some computational overhead involved in calculating the heuristic. In our case this might not really matter, however, if our chosen heuristic is very poor, A* can become even more timeconsuming than Dijkstra! In other words: While Dijkstra will find the best solution, A*'s heuristic is in charge of the time spent to discover it.

So what do we have now? In section 1 we found a way to present the problem in a machine-readable form. Section 2 introduced a method to blindly search for a solution. In section 3 we discovered a possibility to bring orientation into the darkness. 'Yeah, I know, but this is all theoretical. Don't you have a more specific explanation, a more visual one?' I hear you ask.

4. Can you picture this?:

Well, no. The 1-dimensionality of the 15 puzzle seems to be ungraspable for my mind. If you don't mind, let's leave this problem behind and look at something different. Pretend we're implementing pathfinding strategies for a tile-based RTS-game. The search space is defined by our grid consisting of w * h tiles. In this case the open list can be depicted as the outer border of all tiles that have been examined in search of a solution. The closed list contains all tiles 'inside' the open list. When applying Dijkstra's algorithm to find the shortest path from A to B, the search radius will extend in a circular fashion around A (if we allow diagonal moves, otherwise it would be a square) until the border touches B. Thus the open list forms a circle, and closed contains everything inside forming a disc. A*'s search pattern is more irregular and extends more towards the presumably best path. If we have a perfect heuristic the closed list will be nothing but a single line containing the path with the open list surrounding it. In a worst case scenario though, after an A*-search has completed, the closed list can contain all positions, but the goal B, which would be the last one in the open list. I hope this can help to clarify why an A* equipped with a bad - even though correctly underestimating - heuristic can perform worse than Dijkstra.

This is it. For now. Give me a day and I'll come up with some code. If anyone cares about, let me know and I'll mail it to you. I'd like to post it here, but without a fixed-font (and possibly syntax highlighting) it doesn't really turn out readable. If you have questions, insults, comments, ... let me know.

regards,
.:fl0yd:.

------------------------------------------------------------------------------------
errata (guess noone is perfect, oh well...):

c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent
= rev_dir( dir ); goto b.); }

should be:

c.) closed.push_back( n );
++n.move_count;
for each legal dir {
n.tile_state = transform( n.tile_state, dir );
if( !closed.find( n ) ) {        // == if not already visited
n.dir_parent = rev_dir( dir );
goto b.)
}
}
return FAILED;        // no solution

f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}

should be:

f.) ++n.move_count;
for( char d = 1; d <= 8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node node_new( transform( n.tile_state, d ), rev_dir( d ), n.move_count );
if( !closed.find( n_new ) )        // not visited yet
if( !open.find( n_new ) )        // and not already in examination queue
open.push_back( n_new );
else        // if already in examination queue
if( *open.find( n_new ).move_count > n_new.move_count )
*open.find( n_new ) = n_new;    // if faster to reach replace it
}
}

disclaimer: no animals were harmed during the course this production
0

Commented:
Not quite done benchmarking yet. However for the special case of start_state =
[[  0,  1,  2,  3]
[  6,  7,  8,  4]
[  5,  9, 10, 11]
[ 13, 14, 15, 12]]
Dijkstra's algorithm will find the 12-move solution in about 8 minutes, while A* will do it in less than a second!!!

Just in case: The solution is: left, left, left, up, right, right, right, up, left, left, left, up.

.:fl0yd:.

p.s.: updates will follow, as soon as i implemented the rest of the benchmarking stuff.
0

Commented:
Thanks a heap for NOT responding to my post at all. Since there was no feedback whatsoever I won't post any results nor will I share my src -- btw, it's way more structured and speed optimized than yairy's "1'st degree student in AI course"-implementation, with tons of information I gathered when working in the gaming industry. Too bad...
Yairy, you don't talk about your heuristic - the heart and soul of any A*-implementation. Looks like you're using the sum of all tile-distances to their respective goal-positions. However, this will only speed up the last portion of the search and MAY significantly slow down search in more complex situations.

somewhat disappointed,
.:fl0yd:.

ps: I don't believe that posting src-code without any explanation is helpful. It certainly doesn't do justice to "Can anyone show me how to do this in details".
0

Commented:
dear fl0yd,

I am only tring to help.

I think you expanded the subject far too long.

I didn't attached a document cause I wanted to filter
fox that just know to cut and paste.

I still think is a good program.
I used Manhatten-distance (total sum of distnces) to evalute f().
It a good heuristic, not perfect.
but it apply the rules and very fast to calculate.
Maybe it can be even updated instead of re-calculating from father to sons.

I'll be very interested to hear how you "speed optimized"
the algorithm.

I'll give you half the points too.

Yair
0

Commented:
0

Commented:
ahhhh, crappy internet connections at our university pool, didn't mean to say nothing :(

yairy,
sorry, I got a little carried away. I hope I didn't insult you, I just felt that posting uncommented src isn't too helpful. I'll have to stick to my principles though and won't post any of my own src. However, I can point you in the right direction. First of all, using long's might seem reasonable at first sight, however, I used a char[16] instead. Could have packed 2 tiles into one byte and used char[8] with a bit of overhead for access. Using long's has two backdraws: a.) if you use base 10 for encoding you won't make life easy from a computer's point of view - try using base 2 whenever possible. b.) it's dangerous, as you cannot make any assumptions on the size. long's could very well be 1 byte long and still comply with the ANSI standard. [sizeof( char ) <= sizeof( long )].
Btw. you're solving an 8-puzzle, not a 15-puzzle...
As far as speed is concerned your LinerConflict and MDistance make excessive use of '/' and '%', both are computationally expensive, with '%' being even worse than '/'. If you want speed, get rid of those first.
you say that manhatten distance is a good heuristic. Like I said in my previous (non-empty) post, it only speeds up the last portion of the search, but tends to slow down the rest of it in complex situations.

Hope that helps, bare with me, sorry, again,
.:fl0yd:.
0

Commented:
hi, all, can i talk with you guys? i'm kinda lost in a star algorithm, i've been studying pathfinding algorithm from bryan stout's tutorial, i've tried to imitate his program in msvc++ but i'm wholly stuck in best-first search, and the a* algorithm, well... my dijkstra's algorithm runs in a bit different manner than his'... i guess, there's something wrong with the cost function (for dijkstra) and the heuristic estimate (for a* algo)... can you help me out guys? can we get in contact? my email is copet@lycos.com

thanks guys
0

Commented:
will be happy to give a hand....

0

Commented:
true. this is a forum to exchange knowledge. now what would happen if we all just posted our email-addresses? it would turn into an email-directory...
0

Commented:
does "fl0yd and yairy still exist is the forum?
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.