How to programmatically solve the 15 (moving numbers) puzzle?

Question

all of you have probably seen the moving number/picture puzzle. The one where you have numbers from 1 to 15 in a 4x4 grid, and are trying to get them from random starting position to

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15 

My girlfriend or some of my non-programmer friends can solve this with some mumbo-jumbo magic, that they can't explain to me. I can't solve the puzzle.

The most promising approach I have found out is to solve first row, then I'd get

1   2  3  4
X   X  X  X
X   X  X  X
X   X  X 

then first column without touching solved cells

1   2  3  4
5   X  X  X
9   X  X  X
13  X  X 

then second row to

1   2  3  4
5   6  7  8
9   X  X  X
13  X  X 

then second column

1   2  3  4
5   6  7  8
9   10  X  X
13  14  X 

the problem is, that remaining X (random) tiles are sometimes in unsolvable position and this is where my solution fails. But I feel as if I'm on the right path.

My program does the solving of specified row/column by trying to get number X to specified position without messing up the correct cells, if possible. But it can't do the last 3 tiles on 2x2 grid. What am I missing?

Answer 1

Make sure that your puzzle is solvable first. Not all are.

Otherwise your strategy looks sound.

Answer 2

You're definitely on the right track, but rather than solving by row/column iteratively to the point of being left with a 2x2, solve until you have a minimum 3x3 and then solve just that grid. 3x3 is the smallest size you need to properly re-order the grid (while 2x2 doesn't give you the complete flexibility you may need as you've already discussed). This approach is scalable too - you can solve 5x5, 10x10 etc.