Channels ▼
RSS

Parallel

Rebuilding the Tower of Hanoi


The Tower of Hanoi is a puzzle that consists of three pegs and a set of disks. Each disk has a different diameter and a hole in the middle so that the disk can fit onto any of the pegs. The initial puzzle setup has two of the pegs empty and all the disks on the third peg (source) in monotonically decreasing order of diameter from bottom to top, which forms a structure that is reminiscent of a tower. The goal of the puzzle is to move the tower from the source peg to a specified peg (destination) using the other peg to temporarily hold disks. The two rules of the Tower of Hanoi puzzle are that only one disk at a time can be moved from the top of a stack of disks on a peg to some other peg, and disks with larger diameter cannot be placed on top of smaller diameter disks.

French mathematician Edouard Lucas developed the puzzle in 1883. He also created the myth for his puzzle that claimed monks have been working non-stop on a 64-disk version from the beginning of time. Once they have solved this problem, the tower will crumble and the world will end. It's a good story and, I'm sure, it helped to promote the puzzle, but everyone knows that the world ends at 03:14:07 on Tuesday, January 19, 2038.

A programmed solution can be implemented using recursion in a most elegant way. (Again with the recursion? Just one more to finish up, I swear. I'll start my next post with something completely different.) Here's one way to code up a solution.

void tower(char source, char dest, char temp, int level)
{
  if (level > 0) {
    tower(source, temp, dest, level-1);
    printf("Move from %c to %c\n", source, dest);
    tower(temp, dest, source, level-1);
  }
  else
    printf("Move from %c to %c\n", source, dest);
}
. . .
  tower('A', ‘C', 'B', numDisks-1);
. . .

I've used single characters to denote the pegs ('A' is the initial source peg, 'C' is the final destination, and 'B' is the temporary peg). The recursion is halted when the level parameter reaches zero. This corresponds to the source peg having one disk remaining on it, so the code simply prints the move of a disk from the source to the destination peg without further recursive calls. As you can see, the purpose of the code is to print out the set of instructions that can be mechanically followed by someone trying to solve the puzzle in the fewest moves.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video