I've tried to implement Breadth First Search algorithm into my attempt to solve the 8 Puzzle Game. But in some cases, I ran out of memory, but on simpler cases it solves without problem.
How can I improve my algorithm to fix it?
main.c
/* Standard Libraries */
#include <stdio.h>
#include <stdlib.h>
/* Game */
#include <8puzzle/queue.h>
#include <8puzzle/node.h>
#include <8puzzle/state.h>
#include <8puzzle/action.h>
#include <8puzzle/game.h>
/* Main */
int main(void)
{
/* Queue containing the States */
Queue *q = create_queue();
/* Create Root State */
State *root_state = malloc(sizeof(State));
/* Read the State */
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
unsigned int temp;
scanf("%u", &temp);
root_state->game[i][j] = temp;
if (temp == 0)
{
root_state->empty_space.line = i;
root_state->empty_space.column = j;
}
}
/* Create a Node */
Node *root = malloc(sizeof(Node));
root->data = root_state;
/* Check if it's finished */
if (is_finished(root->data))
{
printf("Já está finalizado.\n");
return 0;
}
/* Add State to Queue */
enqueue(q, root);
/* Iterate while queue isn't empty */
while (!is_queue_empty(q))
{
/* Get current node */
Node *node = dequeue(q);
/* Check if it's correct */
if (is_finished(node->data))
{
Node *parent = node->prev;
while (parent)
{
printf("1\n");
parent = parent->prev;
}
return 0;
}
/* Generate possible moves */
Coordinate *sucessors = malloc(4 * sizeof(Coordinate));
int amount_of_sucessors = generate_state_sucessors(node->data, sucessors);
/* For each new possibility of empty space coordinate */
for (int i = 0; i < amount_of_sucessors; i++)
{
/* Create the new state */
State *new_state = swap_state((State *)node->data, sucessors[i]);
/* Add it to queue */
Node *new_node = malloc(sizeof(Node));
new_node->data = new_state;
node->next = new_node;
new_node->prev = node;
enqueue(q, new_node);
}
}
/* Return to operating system */
return 0;
}
game.c
/**
* Game Implementation
*
* This file will produce the implementation of the game, along with the BFS
* algorithm to solve the 8-Puzzle Problem.
*/
/* Standard Libraries */
#include <stdbool.h>
/* Game Files */
#include <8puzzle/state.h>
#include <8puzzle/node.h>
#include <8puzzle/queue.h>
#include <8puzzle/action.h>
#include <8puzzle/game.h>
bool is_finished(State *s)
{
if (s->game[0][0] != 1) return false;
if (s->game[0][1] != 2) return false;
if (s->game[0][2] != 3) return false;
if (s->game[1][0] != 8) return false;
if (s->game[1][2] != 4) return false;
if (s->game[2][0] != 7) return false;
if (s->game[2][1] != 6) return false;
if (s->game[2][2] != 5) return false;
return true;
}
The number of possible positions of an 8-puzzle is 9! = 362880. (Half of those cannot be reached from a given starting position, so there's really only 181440 possibilities.)
On the other hand, it could take up to 31 moves to solve the puzzle, according to wikipedia. At each position, there are 2,3, or 4 possible moves. Hence, a breadth-first-search could easily enqueue 2^31 positions.
This leads to an obvious contradiction. How can the BFS enqueue 2^31 positions when only 181440 positions are possible? Simple, there are many different ways to reach the same board position, and the BFS is enqueuing a large number of duplicates.
The solution: only enqueue positions that haven't already been tried. This can be done using an array of 362880 booleans that keep track of the positions that have been tried. By avoiding duplicates, you're guaranteed that the number of entries in the queue will never be more than 181440.