拼图游戏之打乱拼图

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

计算交换次数(鸠占鹊巢)

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

  • 鸠现在占着鹊(Magpie)巢
  • 鸠的巢(nest)被麻雀(sparrow)占领
  • 鸠和麻雀换巢:鸠回到自己的巢,麻雀挪到鹊的巢
In [1]:
def rev_index(l):
    '''Construct nest<->bird reversed index'''
    rev …
more ...

拼图游戏之可解性条件

可解的必要条件

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

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

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

充分性

三元轮换与聚合

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

A …
more ...