Tower of Hanoi

The robot which we are refering to here is the Hanoi-Solver from JP Brown.

We found this picture in a marvelous German book about puzzles "Schöne Spiele", Walter Sperling, Recklinghausen, 1954, p. 141

The author tells the story about Asian monks, occupied for thousands of years with the problem of the Tower of Hanoi. Generations ever since were busy at work to transfer wooden discs from one place to another respecting some rules :

The more discs there are, the more movements have to be done. Mathematicians have tried to find out the minimum of movements for a given set of discs. Computer scientists have developped many algorithms to solve the problem.

LEGO specialist J. BROWN proposes a remarkable robot-solution. With his program the robot may solve the problem for discs 1 through 5. The program was written in nqc (firmware 2.0) and uses a non-recursive algorithm.

(photo: copyright JP Brown)

We tried to design a ROBOLAB-program for it. As such a program must handle variables, ROBOLAB is perhaps not the best choice. But with the creating sub.vis feature, those programs are better readable than text-orientated ones.

First we chose to program the Tower of Hanoi in Delphi to illustrate the power - and the limitations - of RECURSIVE PROGRAMS. This means that the main algorithm is caracterised by a procedure that calls itself top solve the given problem. DOWNLOAD TOWER OF HANOI

procedure TForm1.Button1Click(Sender: TObject);
        procedure move(source,destn,spare,n:integer);
             if n>1 then move(source,spare,destn,n-1); //The procedure calls itself !!
             richedit1.lines.add(inttostr(richedit1.lines.count)+'. Moving from '+
                                              inttostr(source)+ ' to '+inttostr(destn));
             if n>1 then move(spare,destn,source,n-1); //The procedure calls itself !!
begin //Main program part
      richedit1.Lines.add(edit1.text+' discs');

If you download this program, try different number of discs, but be aware: if you don't have a CRAY- supercomputer, do not try more than 20 discs !! For a Pentium III at 1GHz this will take several hours of computations. The power of recursive algorithms is the extreme shortness of program-code. The limitation is the blowing-up of memory-use and computer-time.

More information about the Tower of Hanoi problem and its solutions.


and two special sub.vis :


You may be disappointed that the program does not have any own Tower of Hanoi - algorithm. In fact our program may solve the two, three and four discs problem with different variable-values. But the movement-commands have to be stored. The RCX does not solve the problem itself, it only executes the movements.


RetourMain Page