The Tower of Hanoi

load program
load complete Delphi-7 project

The Towers of Hanoi

This is an old but still very nice logistic puzzle.
In this article I present a Delphi project that allows the search for solutions by the user as well as the computer.
For the computer search a recursive algorithm is used.

The Game.

Look at the following picture:
A pile of (6) stones must be moved one by one from position A to position B.
However, a stone is not allowed to rest on a smaller one.
Therefore a third pile (C) is needed.

For two stones the procedure is:
    1. move upper stone to pile C
    2. move next stone to pile B
    3. move stone at pile C to B
See picture:
Two stones need 3 moves.
How many moves do we need for 3 stones?
The tric is to move the two upper stones from pile A to C, using the above method.
Then move the third stone from A to B.
Then move to two stones from C to B.
We observe that this takes 3 + 1 + 3 = 7 moves.

In general:
To move n stones from A to B requires moving (n-1) stones from A to C,
one stone from A to B and finally (n-1) stones from C to B.

If n stones are moved in m moves, then (n+1) stones are moved in 2m+1 moves.
So, n stones need 2n -1 moves.

Proof:
Let's assume the above is true.
Then (n+1) stones would require 2n+1 – 1 moves.
But also we may write 2 . (2n -1) + 1 moves but this is equal to the above formula.
Since the formula is true for n=1 it is therefore true for n=2, so for n=3 etcetera.
Note: this type of mathematical proof is called “induction”.

The Algorithm

The power of computers is in the repetion of code.
There are several ways to accomplish repetition.
We know subroutine calls, implemented in Delphi as procedures and functions.

Also there are loops. The local variables of functions and procedures reside on the stack.
Each new call of a procedure therefore has it's own unique local variables.

Now, using functions (or procedures) there are two basic ways to repeat code
    1. by loops (iteration)
    2. by recursion
A general loop looks like this:
During initialization arrays may be cleared and variables set to a value (mostly zero)
The process modifies the variables.
The check tests the variables (or just one) and repeats the process
with the modified variables until the job is done.
In most cases, the process will increment one (control) variable
The test checks if this variable has reached a certain (end) value.

Recursion means, that a procedure (or function) calls itself.
This is confusing so for clearity we assume for a while that the same procedure is duplicated many times.
Then we get, calling procedure Proc with parameter a:
Remember, that the same procedure is pictured three times.
But the parameter a is different for each call to Proc(a).
Of course a test is needed to decide whether the procedure must call itself or run to completion.

Now back to the Towers of Hanoi.
We assign values 1,2,3 to piles A,B,C.
So if we move a stone from (1) to (2) the spare pile is 1 xor 2 = 3.
If we move from (2) to (3) the spare pile is 2 xor 3 = 1. Nice!

Say we must move stones from (1) to (2).
We build procedure SolvGame(...)

procedure solveGame(p1,p2,n : byte);
//move n stones from pile p1 to p2
var p3 : byte;
begin
 if resetFlag then exit;
//
 if (n = 1) then
  begin
   reportmove;
   movestone(p1,p2);        //1 stone to move
  end
  else
   begin
    p3 := p1 xor p2;        //more than 1 stone to move
    solveGame(p1,p3,n-1);
    solveGame(p1,p2,1);
    solveGame(p3,p2,n-1);
   end;
end;
This is all!

Notes:
resetFlag is set by pressing the reset button to end the search.
The actual reset has to wait until crane movement is finished.
Reportmove puts a message on the screen to show the progress.
p1,p2,p3 are the piles.

If we have to move 6 stones from pile 1 to pile 2 this single call does the job: SolveGame(1,2,6); Now one question remains: what does procedure movestone do?

The program

below is a reduced picture of the program at work.
There are two modes:
    play: the player searches for solutions by moving the stones. Solve : the computer searches for a solution
RESET forces the game to the start position with all stones on pile A.

Program structure

The project has 2 units and one form:
    - unit1 : game control, event handling
    - game-unit : game painting and crane movement procedures
    - form1 : paintbox to show game and buttons for control
All painting is done in a bitmap, which is then copied to the paintbox.

Most of the project consist of painting procedures.
The crane is added just for fun.
This crane hangs on a rail, the parts above and below the crane are painted separately.
The upper part only moves horizontally, the lower part is able to move in x and y directions.
The paint procedures have three levels. Only level 1 procedures are called directly by game control.
Level 1 procedures call level2, level 2 procedures call level 3 to do the job.

level 1 paint procedures/functions:

function LoadStone(p : byte) : boolean;
    takes the upper stone from pile p
    exit true if OK, false if no stone present
function unloadStone(p:byte) : boolean;
    drops the loaded stone on pile p
    exit true if OK, false if pile p holds a smaller stone
procedure movestone(p1,p2 : byte);
    calls loadstone( ) and Unloadstone( )
    only used by computer search

level 2 paint procedures/functions

procedure erasePile(p : byte);
procedure paintPile(p : byte);
    Erase/paint pile A,B,C (1,2,3) with all present stones
procedure moveCraneHor(pos : word);
procedure moveCraneDown(posY,clampPos : word);
procedure moveCraneUp;
    move crane to pixel position pos (or posY, vertically)
    clampPos is the horizontal position of the crane clamps, which must be adjusted to
    catch different stone sizes.

level 3 paint procedures/functions (some)

procedure paintCraneRail;
procedure paintcranewheels;
procedure paintWheelJoint;
procedure paintUpperCrane;
procedure paintlowerCrane;
procedure paintCraneLoad;
procedure paintstoneRect(r : Trect; stoneNr : byte);

There are some more functions/procedures to calculate pixel positions or rectangles.
Please refer to the source code for the details.

Used variables in the game_unit: 
var map : Tbitmap;
    game : array[1..3,1..maxheight] of byte;
    pheight : array[1..3] of byte;//number of stones of pile
    stonecount : byte;
    cranePosX : word;
    cranePosY : word;
    craneLoad : byte; //0:no load 1..6:loaded with stone ..
    cranePile : byte;
    clampBase : word;
Stones are identified by numbers 1 (smallest) to 6 (largest).
Game(2,1) = 5 means that pile 2 holds a stone of size 5 at position 1.

StoneCount is the number of stones in the game, changeable by an UPDOWN control on form1.

Figure below lists the stones on pile 1 at the start position:
This concludes the Tower of Hanoi project description.

Addition: Why I dont't like recursion.

The recursive search procedure explained in this article looks nice at first,
mainly because of it's small code size.
The first disadvantage is that it is hard to understand what is happening.
The second is that the search process is hard to manipulate.
The process cannot be stopped / restarted or taken over manually.
To end the computer search a tric was needed:
the resetRequest flag forces exits to end the search, which is not very elegant.
A better way is to build first an array with codes for crane movement
and later execute these codes in an iterative loop.
In this case the player keeps full control during the computer search
which may then be halted and continued.