Information Technology Reference
In-Depth Information
Figure 9.1.
The three-coins problem at the outset
H
H
T
scope gets larger, first in terms of how the thinking should proceed and then in terms
of how the knowledge itself should be represented.
9.1 Planning problems
Once it is determined how to represent knowledge about the states of the world and
how they change as the result of actions, the planning will always be the same.
9.1.1 A first example: The three coins
Consider this very simple puzzle:
Imagine coins arranged with heads and tails as shown in figure 9.1. Make them
all the same (that is, either all heads or all tails) using exactly three moves. A
move here means turning over one of the coins (so that a head becomes a tail, or
a tail becomes a head).
This is not a very hard problem, and a moment's thought will reveal many possible
ways of solving it:
Flip the middle coin, then flip the right one, then flip the middle one again.
Flip the left coin twice, then flip the right one.
Flip the right coin three times. . . .
In all cases, a solution will end up with three heads, and here is why. After one move,
there will be an even number of tails; after two moves, an odd number of tails; after
three moves, an even number of tails; and if all three coins are to be the same, that
even number must be zero. Furthermore, all the solutions involve either moving the
right coin three times, or moving it once and moving one of the other coins twice.
