可解的必要条件

游戏中只能由不断的空块和相邻的块做交换完成。而可解性也由交换数的奇偶性决定,交换数定义为通过交换任意块使得其恢复原状需要的次数。

考虑包含空块在内的交换数:空格子移动一步的时候,进行了一次交换,交换数的奇偶性发生改变。显然最后的奇偶性取决于空格移动步数的奇偶性。而移动步数奇偶性不依赖于具体路径,只依赖于初末位置。我们可以找一条最简单的路径的长度(曼哈顿距离)的奇偶性来判断可解性。

必要条件 移动步数奇偶性必须等于排列数/交换数的奇偶性

充分性

三元轮换与聚合

我们考虑三元置换的可行性。首先如果我们有$ABC$和空格聚在一起,那么显然很容易将$ABC$做轮换$R$

A  B     C  A     B  C
     -->      --> 
C  O     B  O     A  O

对于大于$(2,2)$显然是容易聚在一起的,而且方块越多,自由度越大,越容易聚在一起。所以这里我们仅考虑$(3,2)$的情况:

xx    Bx    Bx    AB    AB    AB
xx -> xx -> Ax -> xx -> Cx -> CO
xx    xx    xx    xx    xx    xx

对于任意的三个$ABC$,我们设想:

  • 聚合Fusion:先将$ABC$和空格$O$,经过系列操作$F=F_1F_2\cdots F_n$拼到一起
  • 三元轮换Rotation:$R$
  • 拆散Decomposition:$F'=F^{-1}$

至此,我们完成了三元轮换。

双对换

三元轮换$ABC\rightarrow BCA$相当于$AB$和$BC$两对带交叉的对换

通过两个三元轮换$ABC$以及$CBD$,那么可以构造无交叉对换: $$ABCD\rightarrow CABD\rightarrow BADC$$ 结果是$AB$对换,$CD$对换。另外无交叉对换显然可以构造轮换:$$ABCDE\rightarrow BACED\rightarrow BCADE$$

显然轮换和双对换在四块以上时是等价的。

结论

通过多次双对换/轮换,显然只要是偶逆序数(亦即偶交换数)都可以恢复初始值。

复杂度

大小为$n^2$的拼图,每次对换平均大概需要$3n$复杂度,总共有$n^2$块,对应大致需要$n^2$次对换。总的时间复杂度为$n^3$

例子

对于$12$和$34$同时错位,首先我们轮换$214$:

2 1     2 1     4 2     4 2
4 3  F  4 O  R  1 O  F' 1 3
5 O     5 3     5 3     5 O

然后我们轮换$143$,合并过程$F=F_1+F_2$

4 2     1 4     1 4     3 1     1 2
1 3  F1 5 2  F2 3 O  R  4 O  F' 3 4
5 O     O 3     2 5     2 5     5 O

合并两个过程,省略第一个$F'$,我们有:

2 1     2 1     4 2     1 4     3 1      1 2      12
4 3  F1 4 O  R1 1 O  F2 3 O  R2 4 O  F2' 3 O  F1' 34
5 O     5 3     5 3     2 5     2 5      5 4      5O

亦即$$\mathrm{Swap}(1,2)\mathrm{Swap}(3,4)=F_1R_1F_2R_2F_2'F_1'$$

生成更多的拼图?

参见拼图游戏之打乱拼图


Comments

comments powered by Disqus