Information Technology Reference
In-Depth Information
Figure 9.12.
Decomposing the 15-puzzle
1
2
3
4
-
-
-
5
6
7
8
-
-
-
-
-
9
10
11
12
-
-
-
-
-
13
14
15
first goal
second goal
third goal
place breaks down into independent subgoals, as shown in figure 9.12. The first goal
is to get the top row and left column of tiles in place without regard for the placement
of any of the others. Once this first goal is achieved, the tiles in the top row and left
column are not disturbed, and the second goal can be considered as a
3
3
puzzle.
The second goal involves getting what is left of the second row and second column in
place, again without regard for the other three tiles. Once this second goal is achieved,
the third goal, with the remaining three tiles, is handled as a
2
×
×
2
puzzle. Note that
each of the goals can be solved independently, as required. Moreover, the first goal
itself can be broken down into two independent goals: getting the first row into place
and then getting the remaining three tiles of the first column into place.
Problem decomposition in Prolog
∗
One way to encode this type of problem decomposition in Prolog is to assume that the
general planner is given a set of
stages
that it must pass through to solve a problem.
If there is no knowledge at all about how to decompose the problem, there would
be exactly two stages: an initial one (applying to every state of the problem) and a
final one (applying to just the goal states). Other problems would have additional
intermediate stages. For example, for the 15-puzzle, the intermediate stages might be
one that applies to every state where the first row is in place, another where both the
first row and first column are in place, and a third where the first two rows and two
columns are in place. Note that these stages are ordered and that each stage applies to
all states of the subsequent stages. This guarantees that as the planner passes through
each stage, it moves ever closer to the final goal.
A Prolog program that plans in stages is shown in figure 9.13. It uses the predicate
legal_move
and
initial_state
as before. But instead of a predicate for
goal_state
,
it expects to see two predicates:
stages
, which provides a list of the names of the
