There is a catch, of course. Only one disk can be moved from one peg to another at a time and, although the spare peg can indeed be used as a temporary stopping place, no disk must ever be placed on top of a disk smaller than itself. Different attempts at the game can be compared and assigned scores in the obvious way: the fewer the moves, the better.
It is possible to solve this problem by semi-systematic experimentation, i.e. by trial and error. A more efficient technique can be found, however, by analysing and decomposing the task. To achieve this, it is useful to adopt another general-purpose strategy - focus first on the simplest situations. Now, the Hanoi game would be extremely simple (pointlessly so as a real game) if we chose to play with only one disk. To succeed, we would need to do no more than move that disk from its start peg to the target peg. And on the face of it, a two-disk game offers scarcely more of a challenge. But the solution of the two-disk game holds within it the germ of the technique required to solve all other cases. What are the steps involved? With two disks, the procedure reduces to the following sub-tasks:
Step 2 is the simple one-disk game, moving the bottom disk to the target B,
and step 3 is another small game moving (the same top) three disks from source peg C to target peg B leaving peg A spare.
If you now say: O.K
But how do you play the game with three disks?, the answer is essentially
the same. In steps 1 and
3 you play a game with two disks and in step 2 you play the one-disk game with
the bottom of the three disks . And to play a game with two disks? As you
know, you need in step 1 to play a one-disk game with the top disk (to get it out
of the way), you then play a one-disk game with the bottom disk - step 2 - to
put it on the target, and you lastly play another one-disk game - step 3 - with
the original top disk to get it back again from the spare to the target peg.
Playing the game, in other words,
always involves playing a smaller version of the game until you can make the
one and only real move - shifting one disk from the source to the target peg.
There is, of course, another possible game situation which we have so far not considered because we are sensible humans. How do you play Hanoi with no disks? Forced to reply we would no doubt say that you do nothing, or to put it slightly differently, you stop as soon as you start. Bearing that in mind, we should perhaps extend the set of component steps. (Let us ignore the possibility that an even crazier user might try to play with a negative number of disks!) Suppose also, just for convenience, we refer to playing the game as to hanoi. We now end up with the following set of action modules:
to hanoi :disks :source :target :spare if empty? :disks [stop] hanoi bf :disks :source :spare :target move first :disks :source :target hanoi bf :disks :spare :target :source end
The input :disks expects a list of disk
names - for example, [disk1 disk2 disk3] or [red orange
yellow green blue indigo violet]. The first of this list will be
the bottom disk and the last will be the top. The inputs :source :target
each expect a single (different) peg name, e.g "peg1,
"green.peg. Since the source, target
and spare pegs are identified in the order of the last three
inputs, the line:
hanoi bf :disks :source :spare :target
has the effect of calling up a new version of hanoi with the current spare peg designated as target (input 3) and the current target peg as spare (input 4).
To develop this primitive system so that it displays (e.g. for a real player) the series of moves required to play the game successfully with any number of disks, we merely have to define the auxiliary procedure move.
to move :disk :source :target (pr "move :disk "from :source "to :target) end
What is most striking about the definition of the procedure hanoi is its apparent circularity. It seems as if, to know how to hanoi, you need to know how to hanoi. The definition turns back on itself uncomfortably. But not forever. In the last resort, when there are no disks left on top of the one we really want to move, the instructions are direct enough. And what is perhaps as great a surprise is the extreme simplicity of the move operation itself. A procedure such as hanoi, with self-reference built into its definition is known as recursive. One of the most powerful features of Logo is its ability to handle recursive procedures.