拼图游戏之打乱拼图

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

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 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

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

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