使用 BFS 改进 8-Puzzle

Question

我尝试将广度优先搜索算法应用到解决 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;
}

Answer 1

8 字谜题的可能位置数是 9！ = 362880。（其中一半无法从给定的起始位置到达，因此实际上只有 181440 种可能性。）

另一方面，解决这个难题可能需要多达 31 步，according to wikipedia。在每个位置，有 2、3 或 4 种可能的移动。因此，广度优先搜索可以很容易地排入 2^31 个位置。

这就导致了一个明显的矛盾。当只有 181440 个位置可能时，BFS 如何排队 2^31 个位置？很简单，有很多不同的方法可以到达同一个棋盘位置，而BFS正在入队大量重复。

解决方案：只对尚未尝试过的位置进行排队。这可以使用一个包含 362880 个布尔值的数组来完成，这些布尔值跟踪已经尝试过的位置。通过避免重复，您可以保证队列中的条目数永远不会超过 181440。

使用 BFS 改进 8-Puzzle

Improve 8-Puzzle using BFS

c

algorithm

queue

breadth-first-search

sliding-tile-puzzle