15 puzzle solver
Table of Contents
1. Introduction
The 15 puzzle is a game where 15 numbered square tiles are arranged on a 4x4 grid. They can be moved to fill the empty square. The objective of the game is to arrange the tiles so that they are in order:
+---+---+---+---+ | 1 | 2 | 3 | 4 | +---+---+---+---+ | 5 | 6 | 7 | 8 | +---+---+---+---+ | 9 | 10| 11| 12| +---+---+---+---+ | 13| 14| 15| | +---+---+---+---+
This program takes a randomly configured board as its input and returns the solution with the least number of moves. For this, the possible board constellations are represented as nodes in a tree. Together with a heuristic that estimates how far away we are from the solution, the A* algorithm is used to find the shortest path on this tree (from initial constellation to solution).
2. Structure of the program
This is a basic overview of our program. First, we simply include the needed libraries. Then, we implement data structures and functions for playing the 15 puzzle game. After that, we implement the A* algorithm. At last, we need to tie A* and our game implementation together so that we can find solutions for the 15 puzzle game.
<<Includes>> <<Implementing the game>> <<Astar algorithm>> <<Tying things together>>
2.1. Includes
We only use standard libraries.
#include <stdint.h> #include <stdio.h> #include <stdlib.h>
3. Implementing the game
Before we start writing a solver, we need to implement a data structure for the board and functions with which to make moves on it.
<<Constants of the game implementation>> <<Data structure of the board>> <<Functions for playing the game>>
3.1. Constants of the game implementation
Although our primary focus is on the classical 4x4 game, we want to allow alternate board sizes.
#define BOARD_ROWS 4 #define BOARD_COLUMNS 4
It is critical that we keep the data structure for the board small, because A*
will have to hold lots of board constellations in memory. The best solutions
seems to be storing the board constellation in an array of 8 bit unsigned
integers. However, an array index does not necessarily correspond to an index
on the board. Instead, if BOARD_ROWS*BOARD_COLUMNS fits into N bits, we
want to use N bits for each board position. The following example demonstrates
this for N = 5.
Array index: 00000000|11111111|22222222|33333333|... Board position: 00000111|11222223|33334444|45555566|...
In the case of a 4x4 game, we have 16 tiles on the board which fit into four bits. This means that our array of 8 bit unsigned integers needs 8 elements to hold the board constellation.
#define BOARD_NUM_TILES 16 #define BOARD_TILE_BITS 4 #define BOARD_ARRAY_SIZE 8
3.2. Data structure of the board
We define a data type for the four possible moves that we can make (up, down,
left and right). It also includes a NONE move. The reason for this becomes
apparent when looking at our board struct. Aside from the array holding our
board constellation, it includes the parent_move (the move leading up to its
constellation). This is necessary so that when we find a solution, we can trace
back the board constellations leading up to it to obtain the sequence of moves.
For efficiency reasons, the board struct also includes the index of the empty
tile's position. Note that this index is in terms of our N bit groupings as
described in section 3.1, and not in terms
of the constellation array indices.
enum move
{
UP, DOWN, LEFT, RIGHT, NONE
};
struct board
{
uint8_t constellation[BOARD_ARRAY_SIZE];
size_t empty_tile_index;
enum move parent_move;
};
3.3. Functions for playing the game
First, we will implement functions dealing with the messy bitshifting arithmetic needed for our board constellation array, as described in section 3.1. Then, we will add functions to make moves on the board.
<<Interface to board constellation array>> <<Making moves on the board>> <<Printing the board>>
3.3.1. Interface to board constellation array
Please check section 3.1 for how the board constellation array is to be interpreted. We want to have an interface that makes it as seemless to use as regular array indexing.
<<Get a range of bits from a uint8_t buffer>> <<Set a range of bits of a uint8_t buffer>> <<Wrapper functions to get and set tiles on our board struct>>
3.3.1.1. Get a range of bits from a uint8_t buffer
This code is responsible for getting the specified range of bits from our
uint8_t array. Note that it only supports ranges spanning at most 8 bits.
However, this is more then enough for our purposes (A* would not finish in a
reasonable time on boards with more than 256 tiles anyways).
We start by shifting the bits to the left by the amount they are offset from the
start of the byte. Then, we shift them to the right by 8 - num_bits. The
result is that the num_bits right-most bits are set to the value we want to
extract and everything to the left of them has been set to zero thanks to the
shifting.
However, if our bits range multiple bytes, some bits on the right are still
missing (they will be set to zero due to the shifting). In this case, we
calculate how much the last bit is offset from the end of the second byte, shift
to the right by that amount and add it to value.
uint8_t uint8_t_buffer_get_bits (uint8_t const *buf, unsigned start_bit,
unsigned num_bits)
{
size_t start_byte = start_bit / 8;
unsigned offset = start_bit % 8;
uint8_t value = buf[start_byte] << offset;
value >>= 8 - num_bits;
if (offset + num_bits > 8) // Bits range through different bytes
{
offset = 8 - (offset + num_bits) % 8;
value += buf[start_byte + 1] >> offset;
}
return value;
}
The following example visualizes how this works.
In this example, (num_bits = 5) and (start_bit = 5). The bits are marked below: Byte 1 Byte 2 |01101101|10011100| ^^^ ^^ Shift Byte 1 to the left by offset: value = 10100000 Shift it back by (8 - num_bits): value = 00010100 Shift Byte 2 to the right by offset of end bit from end of byte: value += 00000010 value = 00010110
3.3.1.2. Set a range of bits of a uint8_t buffer
Refer to section 3.3.1.1 to understand the
idea behind the shifting operations. We use a bitmask that has all of its bits
set to one except for those in the range that we want to set. We then do a
bitwise and of the buffer and the bitmask, so that our bit range is cleared to
all zeroes. Once that is done, we can use a bitwise or of the buffer and the
value (shifted to the proper position) to set the desired bits in the buffer to
the specified value.
Note that the variable bitmask actually is the opposite of what was just
written: All of its bits are set to zero except for those in the range that we
want to set. This is why we prepend it with a bitwise not before doing the
bitwise and with the buffer.
void uint8_t_buffer_set_bits (uint8_t *buf, unsigned start_bit,
unsigned num_bits, uint8_t value)
{
size_t start_byte = start_bit / 8;
unsigned offset = start_bit % 8;
uint8_t bitmask = UINT8_MAX << 8 - num_bits;
bitmask >>= offset;
uint8_t valmask = value << (8 - num_bits);
valmask >>= offset;
buf[start_byte] &= ~bitmask;
buf[start_byte] |= valmask;
if (offset + num_bits > 8) // Bits range through different bytes
{
offset = 8 - (offset + num_bits) % 8;
bitmask = UINT8_MAX << offset;
valmask = value << offset;
buf[start_byte + 1] &= ~bitmask;
buf[start_byte + 1] |= valmask;
}
}
3.3.1.3. Wrapper functions to get and set tiles on our board struct
Now we simply wrap the functions from the previous sections so that we can use them directly on the board struct. We can now get and set tiles as if we were dealing with a regular 2D array.
unsigned int board_get_tile (struct board const *board, size_t row,
size_t column)
{
size_t tile_index = BOARD_COLUMNS * row + column;
unsigned start_bit = tile_index * BOARD_TILE_BITS;
unsigned tile = uint8_t_buffer_get_bits (board->constellation, start_bit,
BOARD_TILE_BITS);
return tile;
}
void board_set_tile (struct board *board, size_t row, size_t column,
uint8_t value)
{
size_t tile_index = BOARD_COLUMNS * row + column;
unsigned start_bit = tile_index * BOARD_TILE_BITS;
uint8_t_buffer_set_bits (board->constellation, start_bit, BOARD_TILE_BITS,
value);
}
3.3.2. Making moves on the board
First, we define a function for checking whether a move is allowed. For example, we can't move down if the empty tile is in the top row.
int board_check_move (struct board const *board, enum move move)
{
size_t empty_tile_row = board->empty_tile_index / BOARD_COLUMNS;
size_t empty_tile_column = board->empty_tile_index % BOARD_COLUMNS;
switch (move)
{
case UP:
if (empty_tile_row >= BOARD_ROWS - 1)
{
printf("[WARNING] Moving up is not possible.\n");
return 0;
}
break;
case DOWN:
if (empty_tile_row < 1)
{
printf("[WARNING] Moving up is not possible.\n");
return 0;
}
break;
case LEFT:
if (empty_tile_column >= BOARD_COLUMNS - 1)
{
printf("[WARNING] Moving right is not possible.\n");
return 0;
}
break;
case RIGHT:
if (empty_tile_column < 1)
{
printf("[WARNING] Moving left is not possible.\n");
return 0;
}
break;
default:
return 0;
}
return 1;
}
If the move is allowed, we make it and return a new board struct, leaving the
old one intact (this is needed for A*). If something fails, just return NULL.
struct board *board_make_move (struct board const *board, enum move move)
{
if (!board_check_move (board, move))
{
return NULL;
}
struct board *new_board = malloc (sizeof (struct board));
if (new_board == NULL)
{
perror ("Failed to allocate board struct");
return NULL;
}
*new_board = *board;
new_board->parent_move = move;
size_t empty_tile_row = board->empty_tile_index / BOARD_COLUMNS;
size_t empty_tile_column = board->empty_tile_index % BOARD_COLUMNS;
size_t switch_tile_row = empty_tile_row;
size_t switch_tile_column = empty_tile_column;
switch (move)
{
case UP:
switch_tile_row += 1;
break;
case DOWN:
switch_tile_row -= 1;
break;
case LEFT:
switch_tile_column += 1;
break;
case RIGHT:
switch_tile_column -= 1;
break;
}
uint8_t tile = board_get_tile (board, switch_tile_row, switch_tile_column);
board_set_tile (new_board, empty_tile_row, empty_tile_column, tile);
board_set_tile (new_board, switch_tile_row, switch_tile_column, 0);
new_board->empty_tile_index = (switch_tile_row * BOARD_COLUMNS
+ switch_tile_column);
return new_board;
}
3.3.3. Printing the board
Especially for debugging purposes, it is useful to be able to print the board constellation.
void board_print(struct board *board)
{
printf ("[");
for (size_t row = 0; row < BOARD_ROWS; row++)
{
printf ("[");
for (size_t column = 0; column < BOARD_COLUMNS; column ++)
{
uint8_t tile = board_get_tile (board, row, column);
if (column != BOARD_COLUMNS - 1)
printf ("%u, ", tile);
else
printf ("%u", tile);
}
if (row != BOARD_ROWS - 1)
printf ("], ");
else
printf ("]");
}
printf ("]\n");
}
4. Tying things together
int main (int argc, char *argv[])
{
struct board *board = malloc (sizeof (struct board));
for (size_t row = 0; row < BOARD_ROWS; row++)
{
for (size_t column = 0; column < BOARD_COLUMNS; column++)
{
uint8_t tile = row * BOARD_COLUMNS + column + 1;
tile %= BOARD_NUM_TILES;
board_set_tile (board, row, column, tile);
}
}
board->empty_tile_index = BOARD_NUM_TILES - 1;
board_print (board);
board = board_make_move (board, DOWN);
board_print (board);
board = board_make_move (board, RIGHT);
board_print (board);
board = board_make_move (board, UP);
board_print (board);
board = board_make_move (board, LEFT);
board_print (board);
}