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 methods.__non-recursive__

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
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 ~~ is true for all
disks smaller than the required one.`MOD` 2^DiskNum=0

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: