An instance of which is shown in figure (4), consists of a 3 x 3 board with eight numbered files and a blank space. A file adjacent to the blank space can slide into the space. The object is to reach a specified goal state, such as the one shown on the right of the figure. The standard formulation is as follows:

- States: A state description specifies the location of each of the eight files and the blank in one of the nine squares.

- Initial state: Any state can be designated as the initial state. Note that any given goal can be reached from exactly half of the possible initial states.

- Successor function: This generates the legal states that result from trying the four actions (blank moves left, right, up or down)

- Goal test: This checks whether the state matches the goal configuration shown in figure (4).

- Path cost: Each step costs 1, so the path cost is the number of steps in the path.

Figure (4) A typical instance of the 8 – puzzle.

The 8 – puzzle belongs to the family of sliding – block puzzles, which are often used as test problems for new search algorithms in AI. This general class is known to be NP-complete, so one does not expect to find methods significantly better in the worst case than the search algorithms described. The 8 – puzzle has 9 ½ z 181, 440 reachable states and is easily solved.

The 15 – puzzle (On a 4 x 4 board) has around 1.3 trillion states and random instances can be solved optimally in a few million seconds by the best search algorithms.

The 24 – puzzle (On a 5 x 5 board) has around $10^{25}$ states and random instances are still quite difficult to solve optimally with current machines and algorithms.