1

我需要知道是否有任何算法可以预先知道,而无需搜索初始集合的所有可能解决方案,如果我们可以达到第二个给定集合。

例如:

[1,0,2,3,5,6,4,8,7] -> [2,3,4,5,8,0,7,1,6]

如果从第一个集合可以到达第二个集合,则该算法将返回 True ,否则返回False 。

我想了一下,我可以肯定地说,如果初始集合是可解的(可以将所有正方形按顺序排列),第二个也是如此,那么这个算法将返回 True,因为:

[1,2,3,4,5,6,7,0,8] <-> [1,2,3,4,5,6,7,8,0] <-> [1,2,3 ,4,5,0,7,8,6]

对于任何给定的可解谜题,可以将其反转以获得原始集合。

另一方面,如果一个集合是可解的,而第二个是不可解的,那么算法肯定会返回 False,因为如果你可以从不可解集开始达到可解集,那么我们就会产生矛盾。

现在,真正的问题是当两个集合都无法解决时。出于某种原因,我很肯定给定一个不可解的集合,有可能达到任何其他不可解的集合配置,因为当集合是可解的时候就会发生这种情况。但我找不到证据或任何文件!有人可以启发我吗?

4

1 回答 1

1

由于棋盘状态的数量有限(9!= 362,880),因此棋盘状态对之间的转换数量有限(9!^ 2 = 131,681,894,400 = 17 GB 的信息)。如此蛮力一次,永远快乐。

于 2015-05-15T02:26:23.823 回答