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

Question

Hi, 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? Thanks

Answer 1

This site has a nice explanation about 3x3 grids, you could probably extend it to 4x4 quite easily.

Answer 2

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

Otherwise your strategy looks sound.

Answer 3

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.

Answer 4

By reduction the only possible case you can't solve must be of the form
1 3
2 X
and you want to get it to
1 2
3 X

by using an additional row and column you can move those to the proper positions with a simple precomputed sequence

Answer 5

There are always up to 4 move positions from any given one. I wonder whether the simple algorithm that goes over all options building 2-4 tree will reach the "solved" position or the stack overflow :)

Answer 6

I think The most effective way of solving this, is using additive patterns, with an admisible heuristic, and IDA* algorithm. As described here - http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf. (I think Felner told us he found a way which is quite better, but I don't remember exactly what it was (bidirectional A*?), but anyhow this should be sufficient (-: ).
Anyhow this course was long ago, so I recommend reading the article..
HTH. Take care.

Answer 7

The solution strategy described by the original poster will always work for a standard solvable 15-puzzle. If Axarydax can reduce a 15-puzzle to the state s/he described and still be unable to solve it, then it was impossible to begin with. Let me explain.

If we treat the blank space in the puzzle as one of the tiles, then each legal move involves swapping that blank "tile" for an adjacent tile. This allows us to regard motions on the puzzle as permutations on 16 characters. That is, elements of the symmetric group S₁₆. Each primitive move is a "swap" or transposition between only two elements (one of which is the blank).

Because the puzzle begins and ends with the blank tile in the lower right, the blank tile must move an even number of times for the puzzle to be solved. (This is easiest to see by imagining an overlaid checkerboard pattern on top of the puzzle -- after an odd number of moves the blank would be on a different color square.) That means that the solution enacted must be a product of evenly many permutations, so it must be an element of the alternating group A₁₆, which has exactly half of S₁₆. (Of the 16! permutations of S₁₆, 16!/2 permutations are even, and 16!/2 are odd. Moreover even*even=even, even*odd = odd, and odd*odd=even.)

If the necessary correcting permutation happens to be odd, it's not possible to solve the puzzle, no matter what you do. If the necessary correcting permutation is even, and if Axarydax follows the strategy described, then the permutation required for the remaining 2x2 block will necessarily be an even permutation fixing the blank square. The only even permutations of only three elements are the rotations 1->2->3->1 (cycle notation (123)) and 1->3->2->1 (cycle notation (132)). These are easily performed on the remaining four squares without disturbing the others.

Since it's implausible that the Axarydax cannot figure out these trivial solutions of the 2x2 blocks, I suspect that either s/he has been pranked, or the 15-puzzle being attempted is nonstandard in some way.