图8兼容国家

Question

我需要知道是否有任何算法允许事先知道，而不是寻找每一个可能的解决方案的初始集，如果我们可以达到第二个给定的集合。

例如：

1,0,2,3,5,6,4,8,7 -> 2，3，5，8，0，7，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，因为如果您可以从不可解集开始到达可解集，那么我们就会有一个矛盾。

现在，真正的问题是当两个集合都是不可解的时候。由于某些原因，我肯定，给定一个不可解集，就有可能达到任何其他不可解集配置，因为这就是当集合可解时发生的情况。但我找不到证据或任何文件！有人能启发我吗？

Answer 1

由于板状态的数量是有限的(9！= 362,880)，所以板状态对之间的转换量是有限的(9!^2 = 131,681,894,400 = 17 GB信息)。如此蛮横一次，永远快乐。