Towers of Hanoi Exercises

Part 1. Three Pegs on a Roundabout

Pegs on a Roundabout is a variation of the Towers of Hanoi puzzle where pegs are arranged on a circle. Disks may only move between adjacent pegs, and they may only move in one direction around the circle. In Three Pegs on a Roundabout, there are three pegs labeled 0, 1, and 2. As long as a larger disk does not appear above a smaller one, a disk may move from peg 0 to peg 1, from peg 1 to peg 2, or from peg 2 to peg 0. Disks may not move directly from peg 2 to peg 1, from peg 1 to peg 0, or from peg 0 to peg 2.

1. Create a program that satisfies the following requirements.
   1. The program should output text that either describes the program itself or describes how to solve Three Pegs on a Roundabout. When it describes how to solve the puzzle, the output should be a string of characters that begins with a left square bracket ([) followed by an even number of comma-separated integers (p_1f, p_1t, ..., p_mf, p_mt) followed by a right square bracket (]). The i^th pair of integers (p_if, p_it) should identify the peg from and the peg to which a disk should be moved during the i^th move of a sequence of moves that solves the puzzle.
   2. If one argument is passed to the program, and the argument is a non-negative integer, n, then the program’s output should describe how to move n disks from peg 0 to peg 1.
   3. If two arguments are passed to the program, and the first argument is a non-negative integer, n, and the second argument is a valid peg number, f, then the program’s output should describe how to move n disks from peg f to the next adjacent peg.
   4. If three arguments are passed to the program, and the first argument is a non-negative integer, n, and the second argument is a valid peg number, f, and the third argument is a value peg number, t, then the program’s output should describe how to move n disks from peg f to peg t.
   5. If the first argument passed to the program is not a non-negative integer, or if the second or third arguments are not valid peg numbers, then the program’s output should describe what the program does. The description produced should not explain how the program generates its output; it should only explain what output is produced, given any possible set of inputs, as well as how to interpret the output if doing so might be helpful to a user of the program.
2. What is the minimum number of moves, m_min, required to solve Three Pegs on a Roundabout when:
   1. the origin and destination pegs are adjacent to each other?
   2. there is a peg between the origin and destination pegs?
   Express your answers in terms of the variable n, where n is the number of disks to be moved.
3. Extend your program. If four arguments are passed to the program, and the first argument is a non-negative integer, n, and the second argument is a valid peg number, f, and the third argument is a value peg number, t, and the fourth argument is the lowercase letter m, then the program should output the integer that is the minimum number of moves required to solve the particular puzzle specified by the first three arguments.
4. Extend your program. If four arguments are passed to the program, and the first argument is a non-negative integer, n, and the second argument is a valid peg number, f, and the third argument is a value peg number, t, and the fourth argument is an integer between 1 and m_min inclusive, then the program should output a pair of comma-separated integers (p_if, p_it) specifying the i^th move in a sequence of moves that solves the specified puzzle in the minimum number of moves possible.
5. Write a program to test your program.
6. Study your program and try to improve it.
   1. What is the largest value of n for which your program can correctly determine m_min, the minimum number of moves required to move n disks?
   2. Try to enhance your program so that it correctly determines m_min for larger values of n. How much of an improvement were you able to make and what did you have to change?
7. Is there more than one way to solve Three Pegs on a Roundabout in the fewest number of moves?

Part 2. Ménage à Trois

Ménage à trois is a multi-player take on the Towers of Hanoi. This interesting variation involves six pegs and three sets of disks. Each set of disks is confined to a set of three pegs, and each set of three pegs has one peg in common with another set. The challenge is to move each set of disks to a different peg.

0. Coming soon!