\documentclass[a4paper]{article}
% Use a nicer looking font than computer modern
\usepackage[tt=false]{libertine}
\usepackage{libertinust1math}
\usepackage[scaled=0.85]{sourcecodepro}
\usepackage[T1]{fontenc}
% Enable literate programming
\usepackage{noweb}
\noweboptions{smallcode}
\title{15 Puzzle Solver in C Using Literate Programming}
\author{Keno Goertz}
\begin{document}
\maketitle
\tableofcontents
\section{Introduction}
The \emph{15 puzzle} is a game where 15 numbered square tiles are arranged on a $4\times4$ 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, as shown in Fig.~\ref{fig:15_puzzle}.
\begin{figure}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4\\
\hline
5 & 6 & 7 & 8\\
\hline
9 & 10 & 11 & 12\\
\hline
13 & 14 & 15 &\\
\hline
\end{tabular}
\end{center}
\vspace{-1pc}
\caption{\label{fig:15_puzzle}The solved 15 puzzle}
\end{figure}
This program takes a given board constellation as its input and returns the moves required to solve the puzzle in the least number of moves.
For this, the possible board constellations are represented as nodes in a directed graph.
Two nodes are connected by two edges in the graph if you can get from one node to the other with a legal move in the game---there are always two edges, since you can invariably go back to the previous node by moving the tile in the direction opposite to that in which it has just been moved.
The edges have weights of either $0$ or $1$, depending on whether the tile being moved is getting closer to its final position, or getting further away from it.
Combined with a few properties to be described in later sections, this will be enough to find the solution with the least number of moves.
\paragraph{Overview} The following listing shows the basic structure of our program.
First, we include the needed libraries.
Then, we implement data structures and functions for playing the 15 puzzle game.
After that, we implement functions which abstract board constellations into the previously mentioned graph representation.
Finally, we tie things together by searching through the paths on the graph until finding the solution.
<<15\_puzzle\_solver.c>>=
<>
<>
<>
<>
<>
@
\paragraph{Includes} We only use standard libraries.
<>=
#include
#include
@
\section{Implementing the game}
Before we start writing a solver, we need to implement data structures to hold game information and functions to play it.
<>=
<>
<>
<>
@
\subsection{Constants of the game implementation}
Although our primary focus is on the classical $4\times4$ game, we want to allow alternate board sizes.
This can be achieved by simply adjusting the constants here.
<>=
#define BOARD_ROWS 4
#define BOARD_COLUMNS 4
@
\subsection{Data structures of the game}
We will need a data structure to describe the four possible moves.
We also need a data structure holding the board constellation.
Finally, we write a function to initialize the board to its solved state.
<>=
<>
<>
<>
<>
@
\paragraph{Data structure for moves} We use an enum to refer to the possible moves.
The direction of the move describes in which direction a tile moves to fill up the previous location of the \emph{empty tile}.
We refer to the positions on the board as \emph{squares}, and to the movable numbered tiles as \emph{tiles}.
We also use the concept of an \emph{empty tile}, which is not really a tile at all, but rather finds itself at the square where no real tile is present.
<>=
enum move
{
UP, DOWN, LEFT, RIGHT, NONE
};
@
\paragraph{Data structure for the board} The data structure for the board consists of a two-dimensional array of unsigned integers.
This array contains the tiles at the indices of the squares of the board.
The empty tile gets assigned the number 0.
The data structure also contains the row and column index of the empty tile, because it is inefficient to search through the array for it every time we want to make a move.
<>=
struct board
{
unsigned tiles[BOARD_ROWS][BOARD_COLUMNS];
size_t empty_tile_row;
size_t empty_tile_column;
};
@
\paragraph{\texttt{malloc} helper function} If \texttt{malloc} ever fails, we just want to print an error message about this and exit the program.
We are going to let a function call \texttt{malloc} and do the check by itself so that we don't have to put the checks everywhere in our code.
<>=
void *safe_malloc (size_t size)
{
void *ptr = malloc (size);
if (!ptr)
{
fprintf (stderr, "malloc failed\n");
exit (EXIT_FAILURE);
}
return ptr;
}
@
We implement the same for \texttt{realloc}.
<>=
void *safe_realloc (void *ptr, size_t size)
{
ptr = realloc (ptr, size);
if (!ptr)
{
fprintf (stderr, "realloc failed\n");
exit (EXIT_FAILURE);
}
return ptr;
}
@
\paragraph{Initializing the board} We also write a function to initialize our board struct.
It returns a pointer to a board that has the tiles arranged in the solution of the puzzle.
<>=
struct board *board_init ()
{
struct board *board = safe_malloc (sizeof (struct board));
for (size_t row = 0; row < BOARD_ROWS; row++)
{
for (size_t column = 0; column < BOARD_COLUMNS; column++)
{
board->tiles[row][column] = (row * BOARD_COLUMNS) + column + 1;
}
}
board->tiles[BOARD_ROWS - 1][BOARD_COLUMNS - 1] = 0;
board->empty_tile_row = BOARD_ROWS - 1;
board->empty_tile_column = BOARD_COLUMNS - 1;
return board;
}
@
\subsection{Functions for playing the game}
We need to implement the following functions to play the game on our board struct.
<>=
<>
<>
<>
<>
@
\subsubsection{Checking if a move is allowed}
We need to check whether a certain move is allowed given the position of the empty tile.
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 row = board->empty_tile_row;
size_t column = board->empty_tile_column;
if ((move == UP && row >= BOARD_ROWS - 1)
|| (move == DOWN && row < 1)
|| (move == LEFT && column >= BOARD_COLUMNS - 1)
|| (move == RIGHT && column < 1))
{
return 0;
}
return 1;
}
@
\subsubsection{Getting the position of the tile that should be moved}
We define a function to obtain the row and column of the tile that should be moved in a specified move.
<>=
void board_get_moving_tile_pos (struct board const *b, enum move move,
size_t *row, size_t *column)
{
*row = b->empty_tile_row;
*column = b->empty_tile_column;
switch (move)
{
case UP:
*row += 1;
break;
case DOWN:
*row -= 1;
break;
case LEFT:
*column += 1;
break;
case RIGHT:
*column -= 1;
break;
}
}
@
\subsubsection{Making moves on the board}
This function takes a board and a move as its input and returns the board after making the move by creating a new board struct.
The original board struct remains unchanged.
This is needed so that we can go back when our search along our graph has led us into hopeless territory---which happens in the majority of cases, since there is just one solution among the approximately $10^{13}$~board constellations.
If something goes wrong (for example, the move is not allowed), a \textsc{null} pointer is returned.
<>=
struct board *board_make_move (struct board const *b, enum move move)
{
<>
<>
<>
}
@
\paragraph{Do not make an unallowed move} If the specified move is not allowed, we abort the function and return \textsc{null}.
<>=
if (!board_check_move (b, move))
{
return NULL;
}
@
\paragraph{Allocate and initialize the new board} We need to allocate the struct for the new board into memory and initially set it to be equal to the current board.
<>=
struct board *newb = safe_malloc (sizeof (struct board));
*newb = *b;
@
\paragraph{Set the tiles of the new board and return it} Finally, we need to change the \texttt{tiles} array and the empty tile position of the new board to reflect on the move.
<>=
// Position of tile before the move
size_t prev_row, prev_column;
board_get_moving_tile_pos (b, move, &prev_row, &prev_column);
// Position of tile after the move
size_t row = b->empty_tile_row;
size_t column = b->empty_tile_column;
newb->tiles[row][column] = newb->tiles[prev_row][prev_column];
newb->tiles[prev_row][prev_column] = 0;
newb->empty_tile_row = prev_row;
newb->empty_tile_column = prev_column;
return newb;
@
\subsubsection{Printing the board}
Especially for debugging purposes, it is useful to be able to print the board.
<>=
void board_print (struct board const *board)
{
printf ("[");
for (size_t row = 0; row < BOARD_ROWS; row++)
{
printf ("[");
for (size_t column = 0; column < BOARD_COLUMNS; column++)
{
printf ("%u, ", board->tiles[row][column]);
}
printf ("\b\b], ");
}
printf ("\b\b]\n");
}
@
\section{Graph representation}
We treat a board constellation as a node on a directed graph.
The possible moves are represented by edges.
The edges are labeled with a $0$ if the moving tile is getting closer to its final position, and with a 1 if it is getting further away.
We call these labels the \emph{cost} of the move.
We have already defined a function to check whether a move is allowed.
Now we need functions to get the cost of a move and to check whether a board is solved.
<>=
<>
<>
@
\subsection{Getting the cost of a move}
This function returns $-1$ if the specified move is not allowed.
If it is allowed, the cost of the move (either $0$ or $1$) is returned.
<>=
int board_get_move_cost (struct board const *board, enum move move)
{
<>
<>
<>
}
@
\paragraph{Handle unallowed moves when getting the cost} We return a cost of $-1$ (representing infinity) for unallowed moves.
<>=
if (!board_check_move (board, move))
{
return -1;
}
@
\paragraph{Calculate various positions of the tile} We first get the position of the tile that is to be moved.
Then, we calculate the position that this tile would have in the solution of the puzzle.
Finally, we calculate the position that the tile would have after the move.
<>=
size_t row, column;
board_get_moving_tile_pos (board, move, &row, &column);
unsigned tile = board->tiles[row][column];
size_t solved_row = (tile - 1) / BOARD_COLUMNS;
size_t solved_column = (tile - 1) % BOARD_COLUMNS;
size_t moved_row = board->empty_tile_row;
size_t moved_column = board->empty_tile_column;
@
\paragraph{Calculate the cost of moving the tile} At last, we return a cost of $0$ if the tile moves closer to its solved position, and a cost of $1$ if it moves away from it.
<>=
if (abs (moved_row - solved_row) < abs (row - solved_row)
|| abs (moved_column - solved_column) < abs (column - solved_column))
{
return 0;
}
return 1;
@
\subsection{Checking whether a board is solved}
This function simply returns $1$ if the board is solved, i.e., every tile is at the correct position, and $0$ if this is not the case.
<>=
int board_is_solved (struct board const *board)
{
for (size_t row = 0; row < BOARD_ROWS; row++)
{
for (size_t column = 0; column < BOARD_COLUMNS; column++)
{
unsigned solved_tile = ((row * BOARD_COLUMNS + column + 1)
% (BOARD_ROWS * BOARD_COLUMNS));
unsigned tile = board->tiles[row][column];
if (tile != solved_tile)
{
return 0;
}
}
}
return 1;
}
@
\section{\label{sec:searching_the_graph}Searching the graph}
We will use the following properties to perform the graph search:
\begin{itemize}
\item The optimal solution is evidently the one that minimizes the number of moves with a cost of~$1$.
\item If the board can be solved with only zero-cost moves, the numbers of moves required will be the sum of the \emph{Manhattan distances} of all tiles to their positions in the solution.
We will refer to this sum simply as the Manhattan distance $d$~of the board.
\item If $n$~moves of cost~$1$ are needed to solve the board, the total number of moves will be~$d+2n$, since moving a tile away from its solved position requires an additional move to bring it closer again.
\end{itemize}
Thus, we first search all paths of zero cost with length $d$ and see if one of them leads to the solution.
If none of them do, we check all paths with cost $1$ and length $d+2$.
If that fails, we check all paths with cost $2$ and length $d+4$, and so on.
<>=
<>
<>
<>
@
\subsection{Data structures of the search}
We will perform the graph search using a recursive function.
This function will have several lists as its arguments, for example the moves performed so far and the added up cost alongside each move.
For this, we need to implement a generic list data type.
<>=
<>
<>
<>
<>
<>
<>
<>
@
\paragraph{List data type} The following struct defines our generic list.
We also use a constant for the initial size of our lists.
<>=
#define LIST_INIT_SIZE 64
struct list
{
void **elements;
size_t length;
size_t size;
size_t sizeof_element;
};
@
\paragraph{Initializing the list} This allocates a list and all of its void pointers into memory.
We pass the size of a list element as the argument.
For example, if we want a list of \texttt{int}, we pass \texttt{sizeof(int)} as the argument.
<>=
struct list *list_init (size_t sizeof_element)
{
struct list *list = safe_malloc (sizeof (struct list));
list->length = 0;
list->size = LIST_INIT_SIZE;
list->elements = safe_malloc (sizeof (void*) * LIST_INIT_SIZE);
list->sizeof_element = sizeof_element;
for (size_t i = 0; i < LIST_INIT_SIZE; i++)
{
list->elements[i] = safe_malloc (sizeof_element);
}
return list;
}
@
\paragraph{Destroying the list} This frees all the memory of a list.
<>=
void list_destroy (struct list *list)
{
for (size_t i = 0; i < list->size; i++)
{
free (list->elements[i]);
}
free (list->elements);
free (list);
}
@
\paragraph{Setting an element of the list} With this function, we can set an element of our list to the given value.
We use \texttt{char} pointers to fill up the elements because a \texttt{char} has a size of one byte.
If our data type is larger than one byte, we can hence use pointer arithmetic on the \texttt{char} pointers to fill up all bytes of the element.
<>=
void list_set (struct list *list, size_t pos, void *value)
{
if (pos < 0 || pos >= list->length)
{
fprintf (stderr, "Tried to set list element out of bounds\n");
exit (EXIT_FAILURE);
}
for (size_t i = 0; i < list->sizeof_element; i++)
{
*((char*) list->elements[pos] + i) = *((char*) value + i);
}
}
@
\paragraph{Getting an element of the list} The following function enables us to get the value of a list element.
<>=
void *list_get (struct list *list, size_t pos)
{
if (pos < 0 || pos >= list->length)
{
fprintf (stderr, "Tried to get list element out of bounds\n");
exit (EXIT_FAILURE);
}
return list->elements[pos];
}
@
\paragraph{Getting the last element of the list} We will often want to get the last element of the list, so we define a function for this.
<>=
void *list_get_last (struct list *list)
{
return list_get (list, list->length - 1);
}
@
\paragraph{Pushing back to the list} This resizes the list if necessary and appends the value to its end.
<>=
void list_push_back (struct list *list, void *value)
{
size_t pos = list->length;
if (pos >= list->size)
{
list->size *= 2;
list->elements = safe_realloc (list->elements,
list->size * sizeof (void*));
for (size_t i = pos; i < list->size; i++)
{
list->elements[i] = safe_malloc (list->sizeof_element);
}
}
list->length += 1;
list_set (list, pos, value);
}
@
\subsection{Calculating the Manhattan distance}
For our algorithm to work as described in Sec.~\ref{sec:searching_the_graph}, we need to calculate the Manhattan distance $d$ of the board.
<>=
unsigned manhattan_distance (struct board const *board)
{
unsigned manhattan_distance = 0;
for (size_t row = 0; row < BOARD_ROWS; row++)
{
for (size_t column = 0; column < BOARD_COLUMNS; column++)
{
unsigned tile = board->tiles[row][column];
if (tile == 0)
{
continue;
}
size_t solved_row = (tile - 1) / BOARD_COLUMNS;
size_t solved_column = (tile - 1) % BOARD_COLUMNS;
manhattan_distance += abs (row - solved_row);
manhattan_distance += abs (column - solved_column);
}
}
return manhattan_distance;
}
@
\subsection{Performing the search}
To perform the search, we will use a recursive function that searches all moves for which the total cost stays below a certain maximum.
Our main function will continuously increase this maximum cost until the recursive function is able to find a solution.
We will also set up utility functions to be used by the recursive search.
<>=
<>
<>
<>
@
\subsubsection{Main search function}
The solution that minimizes the number of moves is also the one that minimizes the combined cost of all moves.
Thus, we start searching for a solution with a cost of zero.
Such a solution must have exactly $d$~moves, where $d$ is the Manhattan distance.
If we don't find a solution, we continuously increase the total allowed cost until a solution is found.
The number of moves of the solution will be exactly $d+2n$ where $n$ is the number of moves with cost 1 that are needed to solve the puzzle.
Our recursive search function returns \textsc{null} if no solution can be found within these constraints for the cost, otherwise it returns a list of the moves that solve the puzzle.
<>=
struct list *search_solution (struct board const *board)
{
<>
unsigned max_cost = 0;
while (1)
{
struct list *solution =
search_solution_recursive (boards, moves, costs, max_cost,
distance);
if (solution)
{
<>
return solution;
}
<>
max_cost += 1;
}
}
@
\paragraph{Set up arguments of the recursive search} These variables are needed by the recursive search.
They are three lists, corresponding to the moves made so far.
The first is the list of the board constellations made by the moves so far, starting with the inital board constellation (the one to be solved).
The second is simply the list of moves made so far.
The third is a list of the accumulated cost at each given move (\texttt{costs[i]} is the sum of the costs of all moves up to \texttt{i}).
<>=
struct list *boards = list_init (sizeof (struct board*));
struct list *moves = list_init (sizeof (enum move));
struct list *costs = list_init (sizeof (unsigned));
unsigned distance = manhattan_distance (board);
unsigned cost = 0;
enum move move = NONE;
list_push_back (boards, &board);
list_push_back (costs, &cost);
list_push_back (moves, &move);
@
\paragraph{Free memory of recursive search arguments} When we find our solution, we need to free the memory that was allocated for the lists which are the arguments to our recursive search (except the list of moves, which we return).
<>=
for (size_t i = 1; i < boards->length; i++)
{
struct board *board = *((struct board**) list_get (boards, i));
free (board);
}
list_destroy (boards);
list_destroy (costs);
@
\paragraph{Reset variables to start search from scratch} Before we increase the allowed cost and start the next iteration of our search function's loop, we reset the arguments of the recursive search so that it starts from scratch.
<>=
for (size_t i = 1; i < boards->length; i++)
{
struct board *board = *((struct board**) list_get (boards, i));
free (board);
}
boards->length = 1;
moves->length = 1;
costs->length = 1;
@
\subsubsection{Search recursively with maximum cost}
We search through all possible moves recursively and exit recursion when the cost has exceeded the allowed cost or when our number of moves is greater than $d+2n$, where $n$ is the allowed number of moves with cost 1, or when we find our solution.
Finally, if we can not find a solution, we return \textsc{null}.
<>=
struct list *search_solution_recursive (struct list *boards,
struct list *moves,
struct list *costs,
unsigned max_cost,
unsigned distance)
{
<>
<>
<>
return NULL;
}
@
\paragraph{Variables inside the recursive search} The variables used inside the function are just the last elements of the lists which are the function arguments.
<>=
struct board *board = *((struct board**) list_get_last (boards));
unsigned cost = *((unsigned*) list_get_last (costs));
enum move move = *((enum move*) list_get_last (moves));
@
\paragraph{Conditions to exit recursion} We stop searching further along a path when our cost or the number of moves have exceeded their allowed maximum values.
In this case we return \textsc{null}.
We of course also stop when we have found the solution, in which case we return the list of moves that solve the puzzle.
<>=
if (cost > max_cost
|| boards->length - 1 > distance + 2 * max_cost)
{
return NULL;
}
if (board_is_solved (board))
{
return moves;
}
@
\paragraph{Recursively try all moves} We just try one move after another, going into the next level of recursion.
Our exit conditions defined above will take care of the rest.
<>=
struct list *result;if (board_check_move (board, UP) && move != DOWN)
{
search_solution_make_move (boards, moves, costs, UP);
result = search_solution_recursive (boards, moves, costs,
max_cost, distance);
if (result)
return result;
search_solution_undo (boards, moves, costs);
}
if (board_check_move (board, DOWN) && move != UP)
{
search_solution_make_move (boards, moves, costs, DOWN);
result = search_solution_recursive (boards, moves, costs,
max_cost, distance);
if (result)
return result;
search_solution_undo (boards, moves, costs);
}
if (board_check_move (board, LEFT) && move != RIGHT)
{
search_solution_make_move (boards, moves, costs, LEFT);
result = search_solution_recursive (boards, moves, costs,
max_cost, distance);
if (result)
return result;
search_solution_undo (boards, moves, costs);
}
if (board_check_move (board, RIGHT) && move != LEFT)
{
search_solution_make_move (boards, moves, costs, RIGHT);
result = search_solution_recursive (boards, moves, costs,
max_cost, distance);
if (result)
return result;
search_solution_undo (boards, moves, costs);
}
@
\subsubsection{Functions for the recursive search}
The first utility function used in the recursive search is simply responsible for making a move and pushing the appropriate values to the back of the lists.
<>=
void search_solution_make_move (struct list *boards,
struct list *moves,
struct list *costs,
enum move move)
{
unsigned cost = *((unsigned*) list_get_last (costs));
struct board *board = *((struct board**) list_get_last (boards));
cost += board_get_move_cost (board, move);
struct board *board2 = board_make_move (board, move);
list_push_back (boards, &board2);
list_push_back (moves, &move);
list_push_back (costs, &cost);
}
@
If we have made a move that lead to one of the exit conditions of our recursion, we need to be able to undo it.
<>=
void search_solution_undo (struct list *boards,
struct list *moves,
struct list *costs)
{
struct board *board = *((struct board**) list_get_last (boards));
boards->length -= 1;
moves->length -= 1;
costs->length -= 1;
free (board);
}
@
\section{Example main function}
We are done!
The following main function shows how to use the above code to find the solution to a given board.
Of course, one could also define a function to construct the initial board from user input, but this is left as an exercise to the reader.
The example board we use looks as shown in Fig.~\ref{fig:15_puzzle_example}.
Its optimal solution is found by this code in a couple of seconds and takes 52 moves.
\begin{figure}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
15 & 14 & 1 & 6\\
\hline
9 & 11 & 4 & 12\\
\hline
& 10 & 7 & 3\\
\hline
13 & 8 & 5 & 2\\
\hline
\end{tabular}
\end{center}
\vspace{-1pc}
\caption{\label{fig:15_puzzle_example}The example board used in the main function.}
\end{figure}
<>=
int main ()
{
struct board board = {
.tiles = {{15,14,1,6},
{9,11,4,12},
{0,10,7,3},
{13,8,5,2}},
.empty_tile_row = 2,
.empty_tile_column = 0,
};
struct list *moves = search_solution (&board);
<>
list_destroy (moves);
return 0;
}
@
\paragraph{Print the solution} This just iterates through the list of moves in the solution and prints out corresponding letters.
<>=
for (size_t i = 1; i < moves->length; i++)
{
enum move move = *((enum move*) list_get (moves, i));
switch (move)
{
case UP:
printf ("U");
break;
case DOWN:
printf ("D");
break;
case LEFT:
printf ("L");
break;
case RIGHT:
printf ("R");
break;
default:
printf ("X");
}
}
printf ("\n");
@
\end{document}