拼图游戏之可解性条件

# 可解的必要条件

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

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

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

# 充分性

# 三元轮换与聚合

我们考虑三元置换的可行性。首先如果我们有$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'$$

# 生成更多的拼图?

参见拼图游戏之打乱拼图