Fifteen puzzle solvability, Numworks Python

[Albert Chan]

Hi Don,

FYI, your original algorithm is also counting swaps (bubble sort)
Again, there is no actual sorting, only swaps counting.

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

Above case would swap 11⇄3, 11⇄8 11⇄1, 11⇄6, 11⇄10, 11⇄7, 11⇄2, 11⇄4, 11⇄9, 11⇄5, like this:

Removed hole: [11,3,8,1,6,15,10,7,14,2,13,4,12,9,5]
10 bubbles => [3,8,1,6,10,15,7,2,14,4,13,9,12,5,11]
 2 bubbles => [1,8,2,6,10,15,7,3,14,4,13,9,12,5,11]
 6 bubbles => [1,2,6,7,10,15,3,4,14,5,13,9,12,8,11]
 3 bubbles => [1,2,3,7,10,15,4,5,14,6,13,9,12,8,11]
...

total swaps = 10 + 2 + 6 + 0 + 3 + 9 + 5 + 3 + 6 + 0 + 4 + 0 + 2 + 1 + 0 = 51

→ row + swaps = 1 + 51 = 52 = even, thus solvable.

Switching to selection sort, and let the code do the logic, solvable(a, n) work for any nxn board

Code:

def solvable(a, n):     # assumed sorted(a) == range(n*n)
    a = list(a)         # copy
    h = a.index(0)      # locate hole
    a.pop(h)            # remove hole
    t = n&1 or h//n     # handle odd or even nxn board
    for i,x in enumerate(a,1):
        if x != i:
            a[a.index(i,i)] = x
            t += 1      # add selection sort swaps
    return t&1 != 0

>>> solvable([11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5], n=4)
True
>>> solvable([1,8,2,0,4,3,7,6,5], n=3)
True