拼图游戏¶

可解的必要条件¶

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

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

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

充分性¶

三元轮换与聚合¶

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

生成拼图¶

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

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

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

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

In [ ]:

from pylab import *
def rev_index(l):
    '''Construct nest<->bird reversed index'''
    rev=empty_like(l)
    for i, j in enumerate(l):
        rev[j]=i
    return rev
def count_swap(nest2bird, bird2nest):
    '''Count swaps needed by an order'''
    count=0
    for dove, magpie in enumerate(bird2nest):
        if dove!=magpie:
            count+=1
            sparrow=nest2bird[dove]
            nest2bird[magpie]=sparrow
            bird2nest[sparrow]=magpie
    return count

from pylab import * def rev_index(l): '''Construct nest<->bird reversed index''' rev=empty_like(l) for i, j in enumerate(l): rev[j]=i return rev def count_swap(nest2bird, bird2nest): '''Count swaps needed by an order''' count=0 for dove, magpie in enumerate(bird2nest): if dove!=magpie: count+=1 sparrow=nest2bird[dove] nest2bird[magpie]=sparrow bird2nest[sparrow]=magpie return count

根据奇偶性判断拼图的可解性¶

In [ ]:

def isSolvable(puzzle):
    '''Judge solvability of 2D matrix A,
    with largest elem representing empty O'''
    m,n = puzzle.shape
    empty = puzzle.size - 1
    nest2bird = puzzle.flatten()
    bird2nest = rev_index(nest2bird)
    ds=sum(divmod(empty - bird2nest[empty], n))
    cnt=count_swap(nest2bird, bird2nest)
    return (cnt+ds)%2 == 0

def isSolvable(puzzle): '''Judge solvability of 2D matrix A, with largest elem representing empty O''' m,n = puzzle.shape empty = puzzle.size - 1 nest2bird = puzzle.flatten() bird2nest = rev_index(nest2bird) ds=sum(divmod(empty - bird2nest[empty], n)) cnt=count_swap(nest2bird, bird2nest) return (cnt+ds)%2 == 0

生成拼图¶

先随机洗牌，然后如果奇偶性错误则对换一组不含空格的块

In [ ]:

def puzzle(m, n=None, shufall=True):
    if not n:
        n=m
    if (n<2 or m<2):
        raise Exception('Puzzle too small')
    A=arange(m*n)
    if shufall:
        shuffle(A)
    else:
        shuffle(A[:-1])
    A=A.reshape([m,n])
    if not isSolvable(A):
        if A[0,0] != A.size-1 and A[0,1] != A.size-1:
            A[0,0],A[0,1]=A[0,1],A[0,0]
        else:
            A[1,0],A[1,1]=A[1,1],A[1,0]
    return A

def puzzle(m, n=None, shufall=True): if not n: n=m if (n<2 or m<2): raise Exception('Puzzle too small') A=arange(m*n) if shufall: shuffle(A) else: shuffle(A[:-1]) A=A.reshape([m,n]) if not isSolvable(A): if A[0,0] != A.size-1 and A[0,1] != A.size-1: A[0,0],A[0,1]=A[0,1],A[0,0] else: A[1,0],A[1,1]=A[1,1],A[1,0] return A

生成的例子¶

In [ ]:

puzzle(6, shufall=False) # 最后一个格子不变

puzzle(6, shufall=False) # 最后一个格子不变

Out[ ]:

array([[18, 26, 10, 17, 30, 11],
       [16, 27, 29,  8, 13, 21],
       [ 7,  5,  3, 34, 33, 25],
       [15, 14, 20,  2, 23, 19],
       [12,  9, 31, 24,  1, 28],
       [32,  6,  4,  0, 22, 35]])

In [ ]:

puzzle(6) # 最后一个格子位置随机

puzzle(6) # 最后一个格子位置随机

Out[ ]:

array([[11,  3,  4, 21,  7, 22],
       [26,  9, 18, 10,  0, 32],
       [29, 24, 14,  5, 12, 33],
       [34, 15,  2, 27, 31, 35],
       [19, 28,  1, 30, 20, 13],
       [16, 25, 23,  6, 17,  8]])

A*最短路径算法¶

这是一个经典的可以用A* heuristics求解的问题 https://github.com/peijunz/code-snippets/blob/master/sliding_puzzle_astar.py

In [ ]: