The 15 Puzzle is a classic sliding-tile puzzle where scrambled tiles need to set in the proper order. The tiles are set in a 4x4 grid with one position empty, and tiles can only be moved by sliding into the empty space. It is a one-player, perfect-information game: the player always knows the exact position of tiles and possible moves. This makes it a useful test of search algorithms, which automatically play out various moves and evaluate the result to find the best sequence of moves.

Challenges for AI Research

• The 15 Puzzle is a version of the Sliding Tile Puzzle, which is an important test domain for heuristic search.
• A heuristic is an estimation of the distance remaining from the current position in the game to the goal.
• A state is a possible configuration of the tiles in the puzzle.
• There are 16! possible configurations of the tiles in the 15 Puzzle. Half of these configurations are not solvable, and it is easy to tell whether or not a configuration can be solved. Even with 16!/2 remaining configurations that can be solved, there are still far more states than can be stored in memory in a computer. 
• Search algorithms look for the shortest (optimal) path of moves from the current state of the game to the goal.
• A* finds the shortest possible path, but even on the 15 Puzzle, it is impossible to store all the states of the game in memory. Therefore, other variations of A* must be used to reduce memory requirements. An example is IDA*, which uses a technique called iterative-deepening.
• Current techniques can find the shortest possible path in the 15 Puzzle, but larger versions of the sliding tile puzzle is still difficult. 

 Research History

• The 15 Puzzle was invented in the late 1800s.
• Dijkstra's algorithm for finding the shortest path in a graph was invented in 1959. 
• The search algorithm A* was invented in 1968, and improve on Dijkstra's algorithm by introducing the use of heuristics into the search.
• Since then, many improvements to A* have been made, including strategies for pruning states that will not lead to the goal, and other methods of determining which paths to explore next.
• The choice of heuristics is also another interesting research area. Heuristics are giving an estimate of the distance to the goal, but it is often difficult to come up with a very accurate estimate without already knowing the solution.