Towers of Hanoi is a classic puzzle and is often used to illustrate the idea of recursion. Here you are challenged to find solutions to some variations, after first explaining the original version.

Joe Celko is best known as the database expert who writes  books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.

This puzzle is one of the Sharpen Your Coding Skills series which introduces Melvin and Bugsy and the rest of the programming staff at International Storm Door and Software write beautiful code in whatever programming  language they have to hand.

“Bugsy, is that a Towers of Hanoi puzzle?” asked Melvin Frammis. Bugsy Cottman, a junior programmer at International Storm Door & Software, looked up from his lunch, and said “Yep, I was looking for my old Rubik's Cube and I found this.” 

Jane Smith from Marketing sat down at the company lunch table, pulled her sandwich from a brown paper bag and picked up the toy. It was a board with three pegs in a row, and stack of disks on one of the end pegs. The disks had a hole in their center like a Chinese coin and they got smaller toward the top of the peg.

“It's a classic puzzle”, said Melvin Frammis. “The goal is to move all the disks from the left side to the right side..” Before he could finish, Jane spun the base of the puzzle and announced, “Done! That is too easy!”

“No, Jane, we have some rules. First, you have to move the disks from peg to peg and leave the base where it is ...” , continued Melvin. Jane grabbed the stack of disks and put them on the final peg. Ignoring this, Bugsy turned the puzzle back to its original position, “... and you can move only one disk at a time, with the restriction that the disks on any peg cannot sit on a smaller disk.”

“This puzzle was popular for teaching recursion in computer science classes when I was in school”, said Melvin. “Me, too", added Bugsy. “What's recursion?” asked Jane. 

“Recursion is a programming and mathematical technique where you solve a problem by reducing it down to smaller and smaller versions of itself, like Matryoshka dolls.” 

“I don't know her; what department does May Troyski work in?” said Jane between bites of her sandwich. “No, Matryoshkas are those Russian nested dolls that are identical and get smaller as you unnest them until you get to the last tiny doll.” 

“I have seen those dolls at a toy store, but I don't get it,” replied Jane. Melvin took the disks off the peg, held up the smallest one and then put it on the first peg. “This is the case for one disk; and yes it is easy,” said Melvin. He then put two disks on the first peg; “This is for two disks; top disk goes to the middle peg, the bottom disk goes to the end, and finally we put the smallest disk on the top of the destination stack. Now, Jane, you try it for three disks.”

Animated GIF solution for four disks by André Karwath

Jane gulped her sandwich down and started moving the disks. Unfortunately, her first move was to put the smallest disk on the middle peg and she had to make a lot of extra moves to recover. “Try again,” said Bugsy, resetting the disks. This time she got it.

“Do you see the pattern? You move the biggest disk to the destination peg and forget about it; it is out of the game. That leaves you with a stack of (n-1) disks. You then do the same thing to get the biggest remaining disk to the destination. Watch.” said Bugsy. He put the original stack back in place and quickly shuffled the disks into place.

“Wow!" said Melvin, “that was fast! I am surprised.”

“Nah!”  said Bugsy, “Once you see the pattern it solves itself. There is no challenge after that. I wish I could remember the code for it.”

Melvin grabbed a paper napkin and wrote a quick block of pseudo-code:

CREATE PROCEDURE Hanoi(
  IN n INTEGER,
  IN start PEG,
  IN work PEG, IN finish PEG)
 IF n = 1
  THEN CALL Move (start, finish)
  ELSE BEGIN
   CALL Hanoi (n-1, start, final, work);
   CALL Move (start, final);
   CALL Hanoi (n-1, work, start, final);
 END;
 CALL Hanoi (n, left, middle, right);
END;

“I think that is right, but you can code it up in your favorite language”, said Melvin. “But why not try to mutate it a little bit and see if it gets more interesting? Here is a list I came up with while Jane was working on it.” Melvin paused, “Where is Jane anyway?”

“She said something about 'Nerds' and walked off while you were writing that list. Show me the list, I'll see what I can do.”

Dear Reader, if you want to try it, here are Melvin's Mutants:

The Barber Pole:

As you can see from the picture of Bugsy's copy of the puzzle, the disk are in two alternative colors. Add a new rule that a disk cannot be moved to a peg with the same color as the disk. This will solve itself, but you might want to figure out why. As a hint, think of the pegs as being in a circle and look at the direction they move.

The Crippled Mutant:

The disk can be moved only one peg to the left or right. This fellow is subject to the same analysis as the original puzzle, but with a different outcome. First you move (n-1) to the right peg, move the largest disk to the middle peg since you cannot hop him directly to his destination. Now the (n-1) stack has to go to the middle peg, to the left peg so the biggest disk can go to the right. This is going to take a lot more moves than the basic puzzle.

The Centipede:

Unless you have only one disk, you need at least three pegs. But what if you had more pegs? Obviously at the extreme, if you have (n) pegs and (n) disk, you put one disk on each peg and just re-stack them. Or you can simply ignore the extra peg and use the original solution. The traditional 4-peg single stack puzzle is the Reve’s Puzzle and it came from Henry Dudeney's classic book, “Canterbury Puzzles”, which has been reprinted by several publishers. There is no proof of minimality, so see what you can do.

The Patriot:

A surprisingly hard version is to color the disks red, white and blue in that order from bottom to top. Just like the two-color version, no disks of the same color can sit on each other. Try this one with 3, 4, 5 and 6 disks to get feel for it.

The Crowd:

Multiple pegs and multiple colored stacks! Start with four pegs, numbered from 0 to 3. A stack of (n) white disks, stack 0, is initially on peg 0, and a stack of (n) black disks, stack 1, is initially on peg 2. The destination pegs for the white stack and the black stack are pegs 2 and 0,respectively. In other words, the goal is to interchange the two stacks, using pegs 1 and 3 as temporary holding pegs.

One obvious algorithm is to use the standard tower algorithm to move the white stack from peg 0 to peg 1, using 3 as the temporary peg; then moving the black stack from peg 2 to peg 0, again using 3 as the temporary peg; and finally moving the white stack from peg 2 to peg 3, once more using 3 as the temporary peg. This takes 3(2ⁿ−1) moves. Try to do better.

Notes:

The Tower of Hanoi puzzle was invented by Edouard Lucas in 1883. The minimum number of moves for the basic puzzle is (2ⁿ − 1). You can cheat and Google up solutions,but try to do it yourself first.

Picture-Hanging Puzzles

Recursion

Other Articles In Sharpen Your Coding Skills 

If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in Joe Celko's  series of Sharpen Your Coding Skills and they have posed us further challenges ever since:

Programmer Puzzle - Hermit Boxes

Jigsaw Puzzles and The MacMahon Squares

Vertex Coverings And The Cool Kids Problem

The Best Sub-Array Problem

Self-Descriptive Arrays

Taxicab Geometry Puzzle

Merkles and Social Engineering

Three Warehouses Puzzle

The Post Production Problem

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info