# Slide Puzzle logic??

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?

-

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.

-
is there an equation to seperate the solvable configurations from the impossible configurations? –  JRowan Feb 27 '13 at 15:03
As @ChrisTaylor said in his answer, you can solve exactly those (half of the total number of) configurations for which $P$ is even. This is a bit more complicated to show. –  Andreas Caranti Feb 27 '13 at 15:06
thanks for your time, is it half of the P even and half of P odd are the solvable ones and vice versa for impossible? or either even or odd are solvable? im just trying to get it through my head. –  JRowan Feb 27 '13 at 15:13
Even P = solvable, odd P = unsolvable. (PS You're welcome!) –  Andreas Caranti Feb 27 '13 at 15:16
im so happy right now, thank you, you live and you learn, notch on the belt –  JRowan Feb 27 '13 at 16:47

Yes. Exactly half of all random starting positions are solvable, and the other half are unsolvable.

-