The Tower of Hanoi Revisited Yet Again

Yes, I know.  A gazillion web pages and other articles have been published on the so-called Tower of Hanoi (or Towers of Hanoi) puzzle.  The game has become so well-known that it has earned its own acronym: TOH.

Many recreational-math types are searching for the fastest algorithm or for ways to solve complex versions of the puzzle; it also is extensively utilized as an instructional study of recursive programming.  My focus is on the details of some non-recursive methods.

Although I do not purport to have the programming skills of many professionals, I nevertheless am amazed at the lengths to which some of these alleged experts will go to distort facts or make up stuff in order to slant readers' viewpoints in favor of their own pet topics.

Some examples of published falsehoods:

• Recursion is faster than iterative methods.
• Iterative code for TOH is quite difficult to understand.
• Iterative techniques for TOH require a lot more code.

In fact, many gurus have conducted timing tests showing that well-written iterative methods are faster than equivalent recursive techniques — and not just regarding this game.  Other knowledgeable folk are fully well aware that not only are many iterative methods available for solving TOH, but that the code can be quite straightforward in design — at least, for the standard 3-peg version of the puzzle.

Having no wish to duplicate the content of other sites, I nevertheless would share a couple of ideas that I have not seen published elsewhere.  Construction of a concise algorithm requires only an application of a few simple mathematical relationships inherent to TOH:

• In a stack of even size, the odd-numbered discs move "toward" the destination, while the even-numbered discs move "away" from it.  For a stack of odd size, the opposite is true. 
• Disc1 (the smallest) moves every 2nd time, Disc2 every 4th time, Disc3 every 8th time, etc.
• Disc1 moves on, and only on, the odd-numbered moves.
• On even-numbered iterations, only one move is possible. 

Here are two workable plans:

On odd-numbered iterations:
    Move Disc1 one peg in the appropriate direction.
On even iterations:
    Plan A: calculate 'whose' turn it is, and transfer that disc.
    Plan B: locate the smaller remaining disc, and move it.

As I have listed these procedures in Basic, there should be no difficulty in deciphering the code.  To that end, the three pegs (towers) are numbered 0,1,2.  A disk movement of +1 indicates the next higher-numbered peg (#2 cycles to #0).  The following integer-class constants and variables are utilized:

TotDiscs 'total discs in play MaxMove 'highest-numbered move of a minimal solution D1P 'current position of Disc1 D1incr 'Disc1 movement = +1 if TotDiscs is even,  -1 if TotDiscs is odd PG() '2-element array identifies the pegs not holding Disc1 FromPeg, ToPeg 'source and destination of a move N, D 'utility

PLAN A:  calculate the disk number on even-numbered moves.

TotDiscs=12 'set to desired game size MaxMove = 2^TotDiscs -1 'moves required for minimal solution D1incr = TotDiscs MOD 2 +1 '1 for even stack, 2 for odd stack FOR Move = 1 TO MaxMove IF Move MOD 2 THEN 'is odd-numbered move FromPeg = D1P 'location of disc1 ToPeg = (D1P + D1incr) MOD 3 'destination of disc1 D1P = ToPeg ELSE 'is even-numbered move PG(0) = (D1P + 1) MOD 3 'identify pegs not holding disc1 PG(1) = (D1P + 2) MOD 3 ' D=0: DO 'determine disc# to move  {1} INCR D: UNTIL Move MOD 2^D ' N = 1-((TotDiscs + D) MOD 2) 'determine disc parity  {2} FromPeg = PG(N) ToPeg = PG(1-N) END IF ' (Output FromPeg & ToPeg info here) NEXT Move

{1} One feature of the disc-rotation rules is that on each move, the identity Move MOD 2^DiskNum=0 is true for all disks smaller than the required one.

Example: For Move #8:

8 MOD 2^1=0
8 MOD 2^2=0
8 MOD 2^3=0
8 MOD 2^4=8

Therefore, it is time to move Disc #4.
Actually, the only information needed is whether the disk number is even or odd.

{2} Say that Disc1 has just been moved to Peg0; the next move will involve Peg1 and Peg2.  Say that TotDiscs is even, and Disc4 has been selected.  By rule, this disc's rotation is +2; therefore, it can only move from Peg2 to Peg1.  It is unnecessary actually to detect Disk4 sitting atop Peg2.  It must be there; otherwise, no valid move would be possible according to the TOH "axioms."

Using this method, the only location that needs to be tracked is for Disc1.

PLAN B:  track the locations of all disks, and select moves accordingly.  This method employs a bit-array for each peg, each bit flagging a specific disc.  The bits are allocated in 'backwards' order — that is, the highest-order bit corresponds to the smallest disk.  This setup enables an algorithm that has no internal loops at all!

One new integer-class variable is needed here:

PegBits() '3-element bit array of discs for each peg

The Code:

TotDiscs=12 'set to desired game size MaxMove = 2^TotDiscs -1 'moves required for minimal solution D1incr = TotDiscs MOD 2 +1 '1 for even stack, 2 for odd stack FOR N = 1 TO TotDiscs 'assign all discs to peg0 BIT SET PegBits(0), TotDiscs-N+1 NEXT N FOR Move = 1 TO MaxMove IF Move MOD 2 THEN 'is odd-numbered move FromPeg = D1P 'location of disc1 ToPeg = (D1P + D1incr) MOD 3 'destination of disc1 D1P = ToPeg ELSE 'is even-numbered move PG(0) = (D1P + 1) MOD 3 'identify pegs not holding disc1 PG(1) = (D1P + 2) MOD 3 ' N= PegBits(pg(0)) > PegBits(pg(1) 'N=true if smallest disc is pg(0)  {3} FromPeg = PG(1+N) ToPeg = PG(1-FromPeg) BIT SET PegBits(ToPeg), TotDiscs+1-Disk 'add disc to peg BIT RESET PegBits(FromPeg), TotDiscs+1-Disk 'delete disc from peg END IF ' (Output FromPeg & ToPeg info here) NEXT Move

{3} This is why the smallest disks are represented by the highest-order bits.  A comparison of two Peg values immediately shows which has the smaller disk!  A reverse ordering of the bits would necessitate some sort of loop structure to accomplish the same goal.

Perhaps the efficiency of these algorithms could be improved; perhaps you could design your own.  Meanwhile, you might like to try your luck on my 12-disc version of the game, by clicking on this graphic: