The Towers of Hanoi Problem

You have a number of rings stacked in order from largest (on the bottom) to smallest (on the top). Your goal is to move them to a second pole without ever placing a larger ring onto a smaller. You have a third pole to use as necessary. How do you do it?

The solution length increases exponentially with the number of rings. Consider the case of three rings. First you would move the top ring to pole B and the second ring to pole C. You would then place the smallest ring also on pole C. Continuing, you would move the largest ring to the empty pole B, the smallest to pole A, and the middle ring onto pole B. Finally, you would place the smallest onto the largest and middle-sized rings now on pole B. Whew!

Imagine how difficult it would be to perform the move with 10 rings, or even five. Thankfully, a computer program can help.

I--for no good reason--ran one (originally from my C Programming textbook) and produced the solution for 23 rings. Indeed, it is enormous! There are 8,388,607 separate steps. The instructions fill a file larger than 300 MB!

The program took 27.900 sec to run on an iMac G3 333 MHz system, running OS 10.1.4. The program was compiled with gcc (-O3 optimization). Timing was done with the standard bash 'time' command.

G'zipping the initial file (solution-23.txt; 301989852 bytes), over-gzipping, and gzipping again, with strengths 7, 7, and 9, respectively, resulted in a compression of 99.0%, 99.2%, and 79.3%. User time was 51.840 sec.

Output (modified--see note below) is saved in solution-23.gz3 (2348 bytes).

Ungzipping all that took 31.759 sec, producing the original file contents. Obviously, the algorithmic structure of the data is highly compressible.

(And that's an understatement!)

Amazingly enough, my rr program is able to repeat all this data in only 0.030 sec. That's 10066328400 bytes/sec, or over 10,000 MB per second!

Files: hanoi-towers.tar.gz (3056 bytes)

Note that the C program is modified to produce simpler instructions, e.g. "A to B" (meaning move top ring from pole A to pole B). The rest of this document has referred to measurements based on output given as "Move top disk from pole [] to pole []."

Joseph K. Myers