8-拼图有多少种可能的状态？

Question

经典的8数码拼图属于滑块家族。我的书籍（《人工智能：一种现代方法》by Stuart Russell和Peter Norwig）指出，8数码拼图有9!/2个可能状态。但是，为什么要除以2呢？如何得出这个结果呢？

- Ghost

---

这里有一个关于MathWorld的解释：http://mathworld.wolfram.com/15Puzzle.html。 - Sergey Kalinichenko

Answer 1

9!是这个难题可能的总配置数，而9!/2是可解配置的总数。例如，这个配置没有解：

1 2 3
4 5 6
8 7

在这篇维基百科的文章中，您可以查阅有关n-拼图某些配置可解性的更多信息。另外，正如@dasblinkenlight在这篇MathWorld的解释中所指出的那样。

确定9!/2是可解配置数量的一种可能方法是从一个已解决的拼图开始，并生成所有可能的有效非重复移动。

- Óscar López

---

虽然这可能是正确的，但这还不是为什么我们必须除以2的解释。或者说呢？ - phimuemue

那么，一些配置不可能的事实如何导致我们将其除以2？ - Ghost

简单来说，正好有一半的配置是不能从任何选定的起点到达（或者换句话说，不能到达任意随机选择的终点），因此我们将总配置数（9！）除以2，得到能够逐步移动到解决方案的状态总数。如果您想知道为什么恰好有一半无法到达，则需要了解“奇偶性”。一个合理的起点是http://www.jimloy.com/puzz/15.htm。 - Penguino

如果你绘制每个状态及其可能的转换的图表，最终会得到9！/2个状态和9！个转换。存在一些状态不在图表上，这些状态是“无解”的。恰好有一半的9！是无解状态。 - user427390

我对第一句话有所异议。在9！种配置中，我们可能能够在9个空间上放置8个方块，但是在这个滑动拼图中，只有9！/2个可达的配置。 - mateor