The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3x3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4x4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces.
The object of the puzzle is to place the tiles in order by making sliding moves that use the empty space. The n-puzzle is a classical problem for modelling algorithms involving heuristics.
Commonly used heuristics for this problem are:
H1: counting the number of misplaced tiles, and H2: finding the sum of the Manhattan distances between each block and its position in the goal configuration