8 puzzle problem

Original article was published on Artificial Intelligence on Medium


Photo by Htun Teza on Unsplash

The 8 puzzle consists of eight numbered, movable tiles set in a 3×3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Such a puzzle is illustrated in following diagram.

The program is to change the initial configuration into the goal configuration.

A solution to the problem is an appropriate sequence of moves, such as “move tile 5 to the right, move tile 7 to the left, move tile 6 to the down” etc…

To solve a problem, we must specify the global database, the rules, and the control strategy.

For the 8 puzzle problem that correspond to three components.

These elements are the problem states, moves and goal.

In this problem each tile configuration is a state.

The set of all possible configuration in the problem space, consists of 3,62,880 different configurations of the 8 tiles and blank space.

For the 8-puzzle, a straight forward description is a 3X3 array of matrix of numbers. Initial global database is this description of the initial problem state. Virtually any kind of data structure can be used to describe states.

A move transforms one problem state into another state.

Figure 1: Solution of 8 Puzzle problem

The 8-puzzle is conveniently interpreted as having the following for moves.

  • Move empty space (blank) to the left, move blank up, move blank to the right and move blank down.
  • These moves are modeled by production rules that operate on the state descriptions in the appropriate manner.

The goal condition forms the basis for the termination.

The control strategy repeatedly applies rules to state descriptions until a description of a goal state is produced.

It also keeps track of rules that have been applied so that it can compose them into sequence representing the problem solution.

A solution to the 8-puzzle problem is given in the above figure 1.