Fifteen puzzle solvability, Numworks Python

[Albert Chan]

(04-25-2020 08:58 AM)Don Shepherd Wrote:  Albert, I don't get the expected results for this data:

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

the empty cell is right after 11

the result should be even (52 per my algorithm), but it is odd (11)

parity of swaps = partiy of inversions.

Without shifting hole down to bottom row, for even nxn board, we need to add hole row number:

row + inversions = 1 + 51 = 52 = even
row + swaps = 1 + 11 = 12 = even

But, removing the hole this way, we need another test for odd sized nxn board

      For odd nxn board, solvability = is_even(inversions) = is_even(swaps)

This got me thinking of a simpler test.
Move the hole to any even row, for any nxn board, this make row# even

      Hole at even row: solvability = is_even(inversions) = is_even(swaps)

Quote:the sorted(a) == range(1,n*n) command always returns FALSE, not TRUE

I were using Python 2.6, above expression just compare the list equality
For Python 3, both side only returns an iterator, not actual list. This might work:

      list(sorted(a)) == list(range(1,n*n))