Fifteen Puzzle

A classic puzzle played on a 4 by 4 grid using tiles numbered 1 to 15. There are 16 locations but only 15 tiles, so there's always a blank cell that you can slide neighboring tiles into. The goal is to return a scrambled puzzle to its pristine state, which consists of the tiles in order from 1 to 15. This is a nice, simple puzzle, and so is a common test problem for ArtificialIntelligence algorithms, such as AstarSearch.

Interestingly, the original version of the 15 puzzle came out of the box with all the tiles already in order, from 1 to 15, except tiles 14 and 15 were swapped. But it's impossible to swap just 14 and 15!

Weirdly enough, the puzzle pretty much describes my apartment in Manhattan. -- AndyPierce

They sell these with a large picture instead of numbers on the tiles. The puzzle is solved when you have restored the picture. Adds a level of interest.

The set of all positions reachable from the solved puzzle that have the blank space at the lower right form the group A_{15}, the alternating group on fifteen elements, which is index 2 in the symmetric group of all permutations.

Similarly, if you were to take RubiksCube apart, there would be 8! 3^{8} 12! 2^{12} ways of putting it back together. The set of positions that can be reached from (and therefore can reach) the solved puzzle is 1/12 as large; only 1 out of every 12 random arrangements can be solved. This is a good way to anger your friends. See the out-of-print book by David Singmaster, Notes on Rubik's Magic Cube, ISBN 0894900579 for details. -- Eric Jablow

CategoryMath