Information Technology Reference
In-Depth Information
Figure 9.10.
The 15-puzzle
1
6
3
8
1
2
3
4
10
2
7
15
=
⇒
5
6
7
8
13
5
4
9
10
11
12
9
14
11
12
13
14
15
initial state
goal state
A partial trace of the
bplan
predicate in action on the monkey and bananas problem
is shown in figure 9.9. Note that if a planning problem cannot be solved, that is, if
there is no sequence of moves that go from the initial state to a goal state, the
bplan
predicate (like the
plan
predicate) will continue searching indefinitely for ever longer
sequences of moves.
9.2.6 A third example: The 15-puzzle
This section considers a more substantial planning problem, the 15-puzzle, attributed
to Noyes Chapman (and sometimes to Sam Loyd). It is a puzzle that consists of a
4
×
4
frame containing tiles numbered 1 to 15 placed in random order (with one space
empty). The object of the puzzle is to place the tiles in numerical order by making
sliding moves that use the empty space. Figure 9.10 shows one possible initial state
and the desired final state.
A state of the puzzle can be represented with a sixteen-element list
[
p
1
,
p
2
,
...
,
p
16
]
,
where each
p
i
is a number from
0
to
15
indicating which tile is in position
i
(and where
0
means that position
i
is empty). For the puzzle in figure 9.10,
the initial state is
[1,6,3,8,10,2,7,15,13,5,4,0,9,14,11,12]
;
the goal state is
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
.
The available moves involve sliding a tile up, down, left, or right, according to
the position of the empty space. The corresponding operators are
up(X)
,
down(X)
,
left(X)
, and
right(X)
, where
X
is a tile.
The easiest way to write
legal_move
for the
up
operator is to write a clause for each
of the twelve locations of the empty square where a tile can go up. For example, to
handle a tile
X
moving up when the empty space is in position 3, one would write the
following:
