Towers of Hanoi

The Towers of Hanoi puzzle was invented by French mathematician Edouard Lucas in 1883. It proved very popular at the time. Puzzles were made in a range of materials to suit rich and poor and the game was sold with the story that monks in Vietnam were playing the game and the completion of the puzzle would signal the end of the world. The number of rings in this game was put at 64, which makes for a very long game (see below). Today it is sold as a child's toy and can sometimes be seen in game shows with giant rings on a beach.

The puzzle is simple: three pegs with a number of rings of different sizes stacked on top of each other, ordered by size with the smallest at the top. The rings must be moved from the first peg to the last using the middle one as an intermediate step. Only one ring at a time can be moved and at no point should a larger ring be placed on top of a smaller one.

There are plenty of web sites on this puzzle, just enter 'towers hanoi' into a search engine.

The solution lends itself particularly well to a recursive algorithm as that is how the puzzle is best solved. Taking a fairly simple situation of just three rings on peg 1 we should proceed as follows:

move top ring from peg 1 to peg 3
move next ring from peg 1 to peg 2
move ring from peg 3 to peg 2 (on top of second ring)
move third ring from peg 1 to peg 3
move ring from peg 2 to peg 1
move ring from peg 2 to peg 3
move ring from peg 1 to peg 3
done!

The number of instructions increases rapidly as more pegs are added to the puzzle. The relationship between rings and the number of instructions is as follows:

The number of instructions can be expressed as: 2 ^ Rings - 1. Thus for 10 rings the number of instructions will be 1023 (2^10-1) while for 64 rings the number of instructions is 2^64 - 1, which is a very large number, large enough to give us plenty of time before the monks in Vietnam complete their game and bring the world to an end.

The solution comes about by describing the problem as:

movetower (3, 1, 3)

where the first 3 is the number of rings, 1 is the starting or 'from' peg and 3 is the finishing or 'to' peg. This general instruction is equivalent to this sequence of subtasks:

movetower (2, 1, 2)
move a ring from peg 1 to peg 3
movetower (2, 2, 3)

The task movetower (2, 1, 2) can in turn be broken down into:

movetower (1, 1, 3)
move a ring from peg 1 to peg 2
movetower (1, 3, 2)

We need to add the using peg to the parameter list.

One way to develop an algorithm for a program is to carry out the operation in analogue form, write down the steps required to solve the puzzle and then see if there is some kind of pattern in the results. If we do this properly we should end up, for a puzzle with three rings, with the following:

• 1 > 3
• 1 > 2
• 3 > 2
• 1 > 3
• 2 > 1
• 2 > 3
• 1 > 3

Seeing the pattern here is a tough call so we will look up the solution in a book:

if height > 0 then
 begin
  movetower (height - 1, frompeg, usingpeg, topeg);
  movering (frompeg, topeg);
  movetower (height-1, usingpeg, topeg, frompeg);
 end;

We can now try a dry run of these procedure calls and trace what happens to the rings. This is an equally tough call, mainly because the order of the parameters changes between the two recursive calls, but here is a possible dry run:

level 1:   movetower (3, 1, 2, 3) //from; using; to;
 level 2:   movetower (2, 1, 3, 2)
  level 3:   movetower (1, 1, 2, 3) //n=0;
               movedisk (1, 3) //from; to;
               movetower* (1, 2, 3, 1) //using; to; from; n=0;
 level 2:   movedisk (1, 2)
              movetower* (2, 3, 1, 2)
  level 3:    movetower (1, 3, 1, 2) //n=0;
                movedisk (3, 2)
                movetower (1, 2, 1, 3) //n=0;
 level 1:   movedisk (1,3)
              movetower* (3, 2, 3, 1)
  level 2:    movetower* (2, 2, 1, 3)
   level 3:    movetower (1, 2, 3, 1) //n=0;
                 movedisk (2, 1)
                 movetower* (1, 3, 1, 2) //n=0;
  level 2:    movedisk (2, 3)
                   movetower* (2, 2, 3, 1)
   level 3:    movetower (1, 1, 2, 3) //n=0;
                     movedisk(1,3)
                     movetower* (1, 2, 3, 1) //n=0;

Note that the move actions have been placed in bold to confirm the sequence seen earlier.

We probably cannot work out the code for ourselves but we should have some insight into how it works. (This style of problem is similar to what you might encounter in the BIO and the international BIO; it is what top programmers, such as those working on games, should be able to produce.)

procedure TForm1.Button1Click(Sender: TObject);
var n:integer;

 procedure movetower(height, fromneedle, toneedle, usingneedle:integer);

  procedure movering (takeoff, puton:integer);
  var textline:string;
  begin
   textline:=inttostr(takeoff) + ' > ' + inttostr(puton);
   listbox1.Items.Add(textline);
  end;

 begin //movetower
 if height > 0 then
 begin
  movetower (height - 1, frompeg, usingpeg, topeg);
  movering (frompeg, topeg);
  movetower (height-1, usingpeg, topeg, frompeg);
 end;

end;

begin //Button1Click
 listbox1.clear;
 n:=spinedit1.Value;
 movetower(n,1,3,2);
end;

Here we place the procedures for processing the moves between towers inside a standard Delphi ButtonClick procedure. The code section of Button1Click contains three instructions: clear the listbox, set the number of towers in the game from the spinedit control and call the main procedure movetower. The parameters 1, 3 and 2 denote: 'move from tower 1 to tower 3 using tower 2'.

Back