8 パズル ゲームを解く試みに幅優先探索アルゴリズムを実装しようとしました。しかし、場合によってはメモリ不足になりましたが、より単純なケースでは問題なく解決しました。
アルゴリズムを改善して修正するにはどうすればよいですか?
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;
}