8谜题有几种可能的状态？ [英] How many possible states does the 8-puzzle have?

问题描述

经典的8拼图属于滑块家族。我的书（《人工智能，斯图尔特·罗素（Stuart Russell）和彼得·诺维格（Peter Norwig）的现代方法》）说，8谜题具有 9！/ 2 可能的状态。但是为什么 / 2 ？

The classical 8-puzzle belongs to the family of sliding blocks. My book (Artificial intelligence A modern approach by Stuart Russell and peter Norwig) says that the 8-puzzle has 9!/2 possible states. But WHY the /2 ? How do you get this?

推荐答案

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

9! is the total number of possible configurations of the puzzle, whereas 9!/2 is the total number of solvable configurations. For example, this configuration doesn't have a solution:

1 2 3
4 5 6
8 7

在此Wikipedia中了解有关n拼图某些配置的可解性的更多信息文章，或如@dasblinkenlight在此MathWorld中指出的解释。

Read more about the solvability of certain configurations of the n-puzzle in this Wikipedia article, or as pointed out by @dasblinkenlight in this MathWorld explanation.

一种可行的方法来找出 9！/ 2 是可解决的配置数量，是从解决难题并从中生成所有可能的有效，非重复动作。

One possible way to find out that 9!/2 is the number of solvable configurations is to start from a solved puzzle and generate all the possible valid, non-repeating movements from it.

这篇关于8谜题有几种可能的状态？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！