覆盖整个网格的随机路径

Question

我有一个 3 * 3 的网格。我有一个 9 个字母的单词，我必须在网格中随机排列。这种排列应该使得网格中有一条有效路径依次覆盖单词。网格中的有效移动是：上、下、左、右、对角线。无法再次访问相同的元素。

你能给我指出正确的方向吗？我只想知道在这种情况下我应该使用什么算法？

抱歉，如果我之前没说清楚。通过随机安排，我的意思是路径不应该是固定的。

如果我有 BUZZINGLY 这个词，示例路径可以是： |卜兹 | |尼兹 | | GLY | , 所以无论我选择什么安排，每次都应该不同。

Answer 1

没有太多选择，如果排除对称变体，选择也很少。您可以将它们全部计算出来，存储起来，然后随机选择一个。然后选择一个随机的旋转和镜像操作。

为了帮助您开始，这会考虑 3 个可能的起点：拐角、中心和中间边缘，并找到所有有效路径。

#include <stdio.h>

int b[3][3];

void print(void) {
  for (int i = 0; i < 3; ++i) printf("%d %d %d\n", b[i][0], b[i][1], b[i][2]);
  printf("\n");
}

void search(int n, int i, int j) {
  if (i < 0 || j < 0 || i > 2 || j > 2 || b[i][j]) return;
  b[i][j] = n;
  if (n == 9) print();
  else {
    search(n + 1, i + 1, j);
    search(n + 1, i - 1, j);
    search(n + 1, i, j + 1);
    search(n + 1, i, j - 1);
    search(n + 1, i + 1, j + 1);
    search(n + 1, i - 1, j + 1);
    search(n + 1, i + 1, j - 1);
    search(n + 1, i - 1, j - 1);
  }
  b[i][j] = 0;
}

int main(void) {
  search(1, 0, 0); search(1, 0, 1); search(1, 1, 1);
  return 0;
}

覆盖整个网格的随机路径

Random Path that covers entire grid

algorithm

graph-algorithm

data-structures