💾 Archived View for kenogo.org › literate_programming › 15_puzzle_solver.c captured on 2023-01-29 at 02:48:44.
-=-=-=-=-=-=-
#include <stdio.h>
#include <stdlib.h>
#define BOARD_ROWS 4
#define BOARD_COLUMNS 4
enum move
{
UP, DOWN, LEFT, RIGHT, NONE
};
struct board
{
unsigned tiles[BOARD_ROWS][BOARD_COLUMNS];
size_t empty_tile_row;
size_t empty_tile_column;
};
void *safe_malloc (size_t size)
{
void *ptr = malloc (size);
if (!ptr)
{
fprintf (stderr, "malloc failed\n");
exit (EXIT_FAILURE);
}
return ptr;
}
void *safe_realloc (void *ptr, size_t size)
{
ptr = realloc (ptr, size);
if (!ptr)
{
fprintf (stderr, "realloc failed\n");
exit (EXIT_FAILURE);
}
return ptr;
}
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;
}
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;
}
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;
}
}
struct board *board_make_move (struct board const *b, enum move move)
{
if (!board_check_move (b, move))
{
return NULL;
}
struct board *newb = safe_malloc (sizeof (struct board));
*newb = *b;
// 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;
}
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");
}
int board_get_move_cost (struct board const *board, enum move move)
{
if (!board_check_move (board, move))
{
return -1;
}
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;
if (abs (moved_row - solved_row) < abs (row - solved_row)
|| abs (moved_column - solved_column) < abs (column - solved_column))
{
return 0;
}
return 1;
}
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;
}
#define LIST_INIT_SIZE 64
struct list
{
void **elements;
size_t length;
size_t size;
size_t sizeof_element;
};
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;
}
void list_destroy (struct list *list)
{
for (size_t i = 0; i < list->size; i++)
{
free (list->elements[i]);
}
free (list->elements);
free (list);
}
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);
}
}
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];
}
void *list_get_last (struct list *list)
{
return list_get (list, list->length - 1);
}
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);
}
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;
}
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);
}
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);
}
struct list *search_solution_recursive (struct list *boards,
struct list *moves,
struct list *costs,
unsigned max_cost,
unsigned distance)
{
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));
if (cost > max_cost
|| boards->length - 1 > distance + 2 * max_cost)
{
return NULL;
}
if (board_is_solved (board))
{
return moves;
}
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);
}
return NULL;
}
struct list *search_solution (struct board const *board)
{
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);
unsigned max_cost = 0;
while (1)
{
struct list *solution =
search_solution_recursive (boards, moves, costs, max_cost,
distance);
if (solution)
{
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);
return solution;
}
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;
max_cost += 1;
}
}
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);
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");
list_destroy (moves);
return 0;
}