3
$\begingroup$

Current board

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)

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Note to start not all n-puzzles are solvable - and in fact half don't have a solution. But there is also a way to tell if a given n-puzzle is solvable (courtesy of here):

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.

$\endgroup$
4
  • 1
    $\begingroup$ Or simpler: assign number 25 (or M*N for a MxN puzzle) to the empty square and count the inversions. It must be even to be solvable regardless of the size. $\endgroup$
    – Florian F
    Sep 22 at 21:13
  • $\begingroup$ @FlorianF are you sure, as the second bullet point seems to suggest it is still possible to be solvable with an odd amount of inversions based on a certain condition? $\endgroup$ Sep 22 at 22:10
  • $\begingroup$ I think the issue there is that those arrangements involve an odd number of moves to get the blank (or M*N) onto the bottom row, and the resulting arrangement will have an even number of inversions. (I'm not familiar enough with these to know how to prove any of this, though.) $\endgroup$
    – Ed Murphy
    Sep 23 at 1:33
  • 1
    $\begingroup$ Sorry, you are right. For instance if you start from the solved state and you shift just one square, you already have an odd permutation of the 25 squares. The parity of the permutation of the 25 squares (with empty) must not be even but must match the parity of the position of the empty square. BG's solution takes care of that. $\endgroup$
    – Florian F
    Sep 23 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy