algorithm - 如何枚举 8-puzzle 中的所有状态？

Question

我正在解决 8 谜题。这是一个看起来像这样的问题：

图片由：https ://ece.uwaterloo.ca/~dwharder/aads/Algorithms/N_puzzles/ 提供（您还可以在此处查看 8 拼图的更详细描述）。用户可以将与空白相邻的正方形移动到空白中。任务是恢复如图所示的排列，从一些任意排列开始。

现在，当然可以将状态描述为 9 位的排列。在显示的图片的情况下，排列是：

1 2 3 4 5 6 7 8 0

但是，并非所有排列都可以从所示配置中获得。因此，我有以下问题。

1. 通过将瓷砖滑入空白中，从所示的初始配置中可以获得多少排列？

2. 调用上述 N 的答案。现在，我想要一个从 1 到 N 的整数到排列的 1-1 映射。也就是说，我想要一个接受排列并返回适当整数的函数，以及一个接受整数并返回排列的函数。映射必须是双射（即不完美的散列是不够的）。

Answer 1

1. 181440。
2. 将它们放在一个数组中并对其进行排序，例如按字典顺序。然后将整数转换为排列是 O(1)，而另一种方式是 O(log n)。

Answer 2

好吧，如果您只想枚举可以达到的不同可能状态，则可以从初始状态开始进行深度优先搜索。在给定当前状态的情况下，很有可能生成有效的下一个状态，例如：将一个瓦片向下移动到空白空间与在排列中将 0 瓦片与在它之前的瓦片 3 交换（如果有的话）相同。因此，您只需执行 dfs 并将所有排列的哈希集保存为您访问的数组，该数组可以存储为整数或字符串。只有9个！可能的状态只有 362880。如果您需要从整数集中进行 1-1 映射，只需将哈希集设为哈希表，每次找到新状态时，只需将其添加到下一个索引处的哈希表即可。您也可以通过先做广度来找到最短的解决方案，然后在找到解决的状态时才打破。