Fifteen puzzle solvability, Numworks Python

[Albert Chan]

I discovered a neat trick to solve this another way.
First, slide down hole to the bottom row. Example:

\(\begin{bmatrix}
11 & & 3 & 8 \\
1 & 6 & 15 & 10 \\
7 & 14 & 2 & 13 \\
4 & 12 & 9 & 5 \\
\end{bmatrix}
⇒
\begin{bmatrix}
11 & 6 & 3 & 8 \\
1 & 14 & 15 & 10 \\
7 & 12 & 2 & 13 \\
4 & & 9 & 5 \\
\end{bmatrix}
\)

With the hole out of the way, simply flattened the matrix as a list, and sort the numbers.

For nxn board, puzzle solvability = is_even(swaps needed to sort the list)

Example, this is my selection sort routine to get swaps.
Note: different sort algorithm produce different swap numbers, but parity is preserved.
Note: no need for actual swaps, we only need number of swaps required.

Code:

def swaps(a, t=0):  # assumed sorted(a) == range(1,n*n)
    a = list(a)     # copy
    for i,x in enumerate(a,1):
        if x != i:
            a[a.index(i,i)] = x
            t += 1
    return t

>>> n = 4
>>> a = [11,6,3,8, 1,14,15,10, 7,12,2,13, 4,9,5]
>>> sorted(a) == range(1,n*n)
True
>>> swaps(a)     # even swaps = solvable
12

---

Another example, if list is in reverse order, is it solvable ?

Try n=3: [8 7 6 5 4 3 2 1] → (swap 18,27,36,45) → [1 2 3 4 5 6 7 8]

For n=3, swaps = 4 = even, thus solvable.

In general, for integer n > 1, swaps = floor((n^2-1)/2)

If n=2k,     swaps = floor(((2k)^2-1)/2) = (4k^2-2)/2 = 2k^2-1 = odd
If n=2k+1, swaps = floor((2k+1)^2-1)/2) = (4k^2 + 4k)/2 = 2k(k+1) = even

→ "reversed" puzzle can only be solved for odd nxn board.