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...

The rest will follow tomorrow.

regards,

.:fl0yd:.