Towers Of Hanoi Mutants |

Written by Joe Celko |

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.
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.
“
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.
Melvin grabbed a paper napkin and wrote a quick block of pseudo-code:
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 ## Notes:The Tower of Hanoi puzzle was invented by Edouard Lucas in 1883. The minimum number of moves for the basic puzzle is (2 ## Related Articles
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 Merkles and Social Engineering 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
or email your comment to: comments@i-programmer.info |