As you can see, I have a sliding 5x5 puzzle, but no matter what way I scramble it and solve it again, I always seem to have two pieces that need to be swapped. Is there a way to swap the two pieces? (19 and 20 in the screenshot)
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 - or 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.
And here an 'inversion' is where when written in a 1D array (i.e. the numbers are listed left to right, top to bottom), a pair of numbers are not increasing in order.
So, applying this to the above puzzle:
- N is odd (5)
- There is 1 inversion (20 > 19)
Therefore we can conclude that this puzzle is not solvable - so unfortunately there is no way to swap the pieces and get a solution.