The Towers of HanoiThis 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:
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:
2. move next stone to pile B
3. move stone at pile C to B
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.
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.
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 AlgorithmThe 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
2. by recursion
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:
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!
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 programbelow is a reduced picture of the program at work.
Program structureThe project has 2 units and one form:
- game-unit : game painting and crane movement procedures
- form1 : paintbox to show game and buttons for control
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;
exit true if OK, false if no stone present
exit true if OK, false if pile p holds a smaller stone
only used by computer search
level 2 paint procedures/functionsprocedure erasePile(p : byte);
procedure paintPile(p : byte);
procedure moveCraneDown(posY,clampPos : word);
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 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:
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.