原理请参见拼图游戏之可解性条件

# 线性时间计算排列的奇偶性

# 计算交换次数（鸠占鹊巢）

扫描所有的鸟，命名为鸠(Dove):

• 鸠现在占着鹊(Magpie)巢
• 鸠的巢(nest)被麻雀(sparrow)占领
• 鸠和麻雀换巢：鸠回到自己的巢，麻雀挪到鹊的巢

# 可解的必要条件

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

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

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