Sliding Tile Puzzle

The sliding-tile puzzle is a standard testbed problem that has been used for more than 50 years in Artificial Intelligence and search. The generalized sliding-tile puzzle is NP-hard. The 15-puzzle has 16!/2 = 10,461,394,944,000 states. The asymptotic branching factor of the 15-puzzle is 2.1304.

Instructions

1. Reset the puzzle to begin.
2. Try to solve the puzzle in as few moves as possible.
3. In the goal the blank is in the upper-left corner, and all tiles are in order from 1-15.
4. Click on a tile to slide it into the blank position.
5. When you have solved the puzzle, compare your solution length to a fast suboptimal solver.

to random puzzle

Benchmark Problems

Some standard problems that have been used in the literature include:

• 100 Korf instances. Taken from (Korf, 1985).
• 1000 Felner instances. Taken from (Korf and Felner, 2002).

Research Citations

The sliding-tile puzzle has been broadly used in past literature. A sample of past publications using this domain includes the following references. (This list is far from complete, and is still in the process of being updated. If you'd like to submit papers to be listed here, please e-mail bib entries to nathanst@ualberta.ca)