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); begin 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 !! end; begin //Main program part richedit1.clear; richedit1.Lines.add(edit1.text+' discs'); move(1,3,2,strToint(edit1.text)); end; |
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.
Our ROBOLAB-functions: DOWNLOAD ALL THE FILES
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.
Notes:
Starting at variable 4 we set the variables for the movements:
- set 0,4,2,18 which means set variable 4 to constant value 18
- 18 is the hexadecimal 0x12 - you recognize move 1 to 2
- to extract the starting (grab) place we divide 18 by 16 e.a. 1
- to explain the extraction of the ending point (drop), we must have a look at the binary representation of 18 which is b0001 0010 . We mask the high-byte by operating the bitwise AND-function with the number b0000 1111. Thus we obtain b0000 0010 which is the value 2