Objective : Solve a 15-puzzle program using a realtime search algorithm.
The 15-puzzle problem is some arrangement of numbers 1 to 15 in a 4 x 4 grid with 16 square blocks labeled 1 to 15 and one blank square. The blocks need to be arranged so that they are in order from any starting configuration.
We described the A* algorithm yesterday.
Now, we use a real time algorithm as described by Ian Parberry. It is designed using both greedy and divide-and-conquer techniques.
The algorithm is generalized for (n^2-1) grid puzzles.
The algorithm is described as follows:
procedure puzzle(n)
if n == 3 then solve by brute force else
use a greedy algorithm to put the first row and column into place
call puzzle(n-1) to solve remaining rows and columns.
Step 2 above places tiles in the first row ( 1 <=k <=n ) into place at locations (1, k) followed by
(2 <= k <=n) tiles into place at locations (k,1) for 2 <=k <= n into place, one at a time.
The implementation looks something like this:
Void Solve(Board<Location> b, Board<Location> goal, int n, Location blank)
{
For (int k = 1; k <= n/2; k++)
{
Var tile = goal[1,k];
Var location = getPosition(b, tile);
If (location.row > 1 && location.col > N/2)
{
If (k == 1)
Move_the_blank_to_right_adjacent(1,2,blank.row, blank.col);
else
Move(2,k-1,blank.row, blank.col);
If (k> 1)
Move_the_blank_to _right_adjacent(1,k+1, 2,k-1)
// move the target tile diagonally to nearest axis
If (location.row-1 > location.col-1)
Move_target_tile_to_goal_col(1,k,ref location.row, ref location.col)
Else
Move_target_tile_to_goal_row(1,k, ref location.row, ref location.col)
// location is updated by reference
//move the target tile horizontally or vertically
Move_target_tile_to_goal(1,k, ref location.row, ref location.col);
// assert( location.row ==1 || location.col == k);
}else{
// similar
} // end else
} // end for
}
To move a tile vertically up, the blank must move from its right anticlockwise to the position right above the tile so that the tile can take its place.
To move a tile horizontally to the left, the blank must move anticlockwise to the tile’s left so that the tile can take its place.
To move a tile diagonally to the left, the blank must move anticlockwise to the position right above the tile, so that he tile can take its place and the blank can come down. From this position, the blank has to move clockwise until it is to the adjacent left of the tile so that the tile can take its place.
Location GoAntiClockwiseAround(Location center, int n, int steps)
{
var current = center;
for (int i = 0; i < 8 && steps; i++)
{
switch(i)
{
case 0:
if (center.row - 1 > 0){
current.row = center.row - 1;
current.col = center.col;
steps--;
}
break;
case 1:
if (center.row - 1 > 0 && center.col - 1 > 0){
current.row = center.row - 1;
current.col = center.col - 1;
steps--;
}
break;
case 2:
if (center.col -1 > 0){
current.row = center.row;
current.col = center.col - 1;
steps--;
}
break;
case 3:
if (center.row + 1 < n && center.col - 1 > 0){
current.row = center.row + 1;
current.col = center.col - 1;
steps--;
}
break;
case 4:
if (center.row + 1 < n){
current.row = center.row + 1;
current.col = center.col;
steps--;
}
break;
case 5:
if (center.row + 1 < n && center.col + 1 < n){
current.row = center.row + 1;
current.col = center.col + 1;
steps--;
}
break;
case 6:
if (center.col + 1 < n){
current.row = center.row;
current.col = center.col + 1;
steps--;
}
break;
case 7:
if (center.row - 1 > 0 && center.col + 1 < n){
current.row = center.row - 1;
current.col = center.col + 1;
steps--;
}
break;
default:
break;
}
}
return current;
}
