Fifteen puzzle solvability, Numworks Python

[Don Shepherd]

(02-20-2021 10:10 AM)danielcharles Wrote:  Hello
Given a 4×4 board with 15 tiles (every tile has one number from 1 to 15) and one empty space. The objective is to place the numbers on tiles in order using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space. For example,


15puzzle

Here X marks the spot to where the elements can be shifted and the final configuration always remains the same the puzzle is solvable.
In general, for a given grid of width N, we can find out check if a N*N – 1 puzzle is solvable or not by following below simple rules :


If N is odd, then puzzle instance is solvable if number of inversions is even in the input state.
If N is even, puzzle instance is solvable if
the blank is on an even row counting from the bottom (second-last, fourth-last, etc.) and number of inversions is odd.
the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.) and number of inversions is even.
For all other cases, the puzzle instance is not solvable.
What is an inversion here?
If we assume the tiles written out in a single row (1D Array) instead of being spread in N-rows (2D Array), a pair of tiles (a, b) form an inversion if a appears before b but a > b.
For above example, consider the tiles written out in a row, like this:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 X
The above grid forms only 1 inversion i.e. (2, 1).

Daniel, I prefer the simpler test for solvability: Add the number of inversions and the row number (1-4) of the empty cell. If that number is odd, the configuration is not solvable, else it is.

If a configuration is not solvable, it can be made solvable by exchanging any two cells.