8 Puzzle
Problem.
The 8 puzzle consists of eight
numbered, movable tiles set in a 3x3 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 tiles 5 to the right, move tile
7 to the left ,move tile 6 to the down, etc”.
To solve a problem using a
production system, we must specify the global database the rules, and the
control strategy. For the 8 puzzle problem that correspond to these three
components. These elements are the problem states, moves and goal. In this problem
each tile configuration is a state. The set of all configuration in the space
of problem states or the problem space, there are only 3,62,880 different
configurations o the 8 tiles and blank space. Once the problem states have been
conceptually identified, we must construct a computer representation, or
description of them . this description is then used as the database of a
production system. For the 8-puzzle, a straight forward description is a 3X3
array of matrix of numbers. The 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. The 8-puzzle is convenjently 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 rules each have
preconditions that must be satisfied by a state description in order for them
to be applicable to that state description. Thus the precondition for the rule
associated with “move blank up” is derived from the requirement that the blank
space must not already be in the top row.
The problem goal condition
forms the basis for the termination condition of the production system. The
control strategy repeatedly applies rules to state descriptions until a
description of a goal state is produced . it also keep track of rules that have
been applied so that it can compose them into sequence representing the problem
solution.
