RE: Fifteen puzzle solvability, Numworks Python
(04-24-2020 11:05 PM)Albert Chan Wrote: 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.
Albert, this is very interesting. I'm going to test this with about a dozen 4x4 layouts I have and see if it holds true for them.
thanks, Don
|