334 • CHAPTER 12 Problem Solving
goal would be to move the large disc that is on the left over to the peg on the right.
However, if we are to obey the rules, we can’t accomplish this in just one step, because
we can move only one disc at a time and can’t move a disc if another disc is on top
of it. To solve the problem we therefore set a series of subgoals, some of which may
involve a few moves.Subgoal 1: Free up the large disc so we can move it onto peg 3. Do this by
(1) removing the small disc and placing it on the third peg
(● Figure 12.12a; this is state 2 in the problem space in Figure 12.11).
(2) Remove the medium disc and place it on the second peg
(Figure 12.12b; state 3 in the problem space). This completes the
subgoal of freeing up the large disc.Subgoal 2: Free up the third peg so we can move the large disc onto it. Do this by
moving the small disc onto the medium one (Figure 12.12c; state 4 in
the problem space).Subgoal 3: Move the large disc onto peg 3 (Figure 12.12d; state 5 in the problem
space).Now that we have reached state 5 in the problem space, let’s stop and decide how
to achieve subgoal 4, freeing up the medium-sized disc. We can move the small disc
either onto peg 3 (state 9) or onto peg 1 (state 6). These two possible choices illustrate
that to fi nd the shortest path to the goal, we need to look slightly ahead. When we do
this, we can see that we should not move the small disc to peg 3, because that blocks
moving the medium disc there, which would be our next subgoal. Thus, we move
the disc back to peg 1, which makes it possible to move the medium disc to peg 31823459 67Initial stateGoal state●FIGURE 12.11 Problem space for the Tower of Hanoi problem. The most effi cient path
from the initial state (1) to the goal state (8) is to traverse intermediate states 2–7, as indicated
by the arrow and highlighting. (Source: Based on K. Dunbar, “Problem Solving,” in W. Bechtel & G. Graham,
Eds., A Companion to Cognitive Science, pp. 289–298, London: Blackwell, 1998.)Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.