0

我的 n-puzzle 求解器有问题。以为它有效,但事实证明它正在解决无法解决的难题。我试图追踪它,但这是很多追踪,到目前为止我没有看到任何作弊行为。我想我了解确定溶解度的算法,并且我的实现与网络上一些示例的奇/偶校验一致......也就是说,当我计算给定瓷砖之后小于的瓷砖数量时它,对于每个图块,然后添加空白图块的行索引,我得到的奇数或偶数与其他人得到的相同。

于是,我产生了一个念头。在我的 8 谜题模型中,我的解决方案状态是:

_ 1 2
3 4 5
6 7 8

而不是

1 2 3
8 _ 4
7 6 5

或者

1 2 3
4 5 6
7 8 _

就像在其他一些配方中一样。这会影响哪些谜题是可解的,哪些不是吗?

谢谢!

z。

4

1 回答 1

1

一般来说,是的:如果一个配置可以解决到标准解决方案,它就不能解决到一个不可解决的配置。

特别是,它取决于您用作解决方案的确切配置。您将需要检查是否可以从该配置解决到标准配置。

编辑: 这样:

设 A 为标准解。让 B 成为您的首选解决方案。让 C 成为您的起始配置。

如果你可以从 A 到 B,你可以从 C 到 A,那么你可以从 C 到 B。但是如果你不能从 A 到 B,而你可以从 C 到 A,那么你不能从 C 到 B。

于 2012-10-07T15:11:12.863 回答