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 `'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: