Fifteen puzzle solvability, Numworks Python

[Albert Chan]

We can do sorting *faster* than even QuickSort !
With sorted(a) == range(n*n), we have sorted(a)[x] = x

Fast Algorithm:
For all items in the list, if a[k] != k, keep swapping a[k] and a[a[k]]
Each swap guaranteed 1 correct spot, 2 if lucky.

[11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5] // puzzle
[13,0,3,8,1,6,15,10,7,14,2,11,4,12,9,5] // swap a[0],a[a[0]]
[12,0,3,8,1,6,15,10,7,14,2,11,4,13,9,5] // swap a[0],a[a[0]]
[4,0,3,8,1,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]]
[1,0,3,8,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]]
[0,1,3,8,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]] *
[0,1,8,3,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,7,3,4,6,15,10,8,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,10,3,4,6,15,7,8,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,2,3,4,6,15,7,8,14,10,11,12,13,9,5] // swap a[2],a[a[2]] *
[0,1,2,3,4,15,6,7,8,14,10,11,12,13,9,5] // swap a[5],a[a[5]] *
[0,1,2,3,4,5,6,7,8,14,10,11,12,13,9,15] // swap a[9],a[a[9]] *
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]


On my laptop, with 100x100 board, this version has speed ≈ 100 times my selection-sort version.
(I expected more, but Python's list.index is coded in C, and very fast)

Code:

def solvable(a, n, t=0):    # assumed sorted(a) = range(n*n)
    a = list(a)             # copy
    x = y = a[0]            # locate hole
    while x: y=x; x=a[x]; a[y]=0; t+=1
    a[0] = 0
    t += (n&1 or y//n) + y
    for x in a:
        while x: y=x; x=a[x]; a[y]=0; t+=1
    return t&1 != 0

(*) Above code doubled counted the lucky cases, instead of skipping them. (parity is maintained)
For lucky case, x and a[x] are the same, and nonzero. It take 2 loops before x=0, thus double counted.
This is why I love Python, I would have not known this without experimentation ...

Replace with this for loop skipped over lucky cases, but is slightly slower

Code:

    for i, x in enumerate(a):
        while x > i: y=x; x=a[x]; a[y]=0; t+=1