algorithm - 8-puzzle 有多少种可能的状态？

Question

经典的 8 拼图属于滑块系列。我的书（Stuart Russell 和 peter Norwig 的人工智能现代方法）说 8 谜题有9!/2种可能的状态。但是为什么/2？你怎么得到这个？

Answer 1

9!是拼图可能配置的总数，而9!/2是可解决配置的总数。例如，此配置没有解决方案：

1 2 3
4 5 6
8 7

在这篇 Wikipedia文章中阅读有关 n-puzzle 某些配置的可解性的更多信息，或者正如 @dasblinkenlight 在此 MathWorld解释中所指出的那样。

找出9!/2可解配置数量的一种可能方法是从一个已解决的谜题开始，并从中生成所有可能的有效、非重复动作。