say there is an image made into a slide puzzle in a grid of sections 4 wide and 6 high, the missing piece that is missing so you can slide the other pieces of the puzzle around is always the bottom right piece of the grid if the picture matches the complete puzzle, so, if all the pieces of the image even the missing one were randomly placed on the grid, is there ANY chance that the puzzle would be impossible to complete?
[Math] Slide Puzzle logic?
linear algebramathematical modelingpuzzle
Best Answer
It's entirely analogous to the 15-puzzle.
To show that not all initial positions allow you to get to the desired final position, note the following invariant.
Assume that in the final position you have the numbers from 1 to 23 written on the pieces starting in the top left corner, and proceeding row-wise to the bottom right corner, where you put 24 to represent the missing piece. Associate to this the identity permutation, obtained by reading the images of the numbers $1, \dots, 24$ row-wise from top left to bottom right.
When you exchange 24 with another piece, you are composing the given permutation with a $2$-cycle, thereby changing the parity. But you are also changing the block distance of 24 from the bottom right corner by 1, so $$ P = \text{parity of the permutation} + \text{parity of the block distance} $$ is preserved.
Now the final position has $P$ even. If you start with the initial position in which 22 and 23 are exchanged, $P$ for this position is odd, so you will never be able to get to the final position from here.