You may be familiar with the Tower of Hanoi puzzle in which you start with eight discs stacked on one of three pegs, each disc smaller than the one below it. The other two pegs are empty. The goal of the puzzle is to move the entire stack of discs to a different peg, according to the following rules:
- Only one disc may be moved at a time, from the top position on one peg to the top position of a different peg.
- No disc may ever be placed on top of a smaller one.
For convenience, we number the discs from 1 to 8 in order from smallest to largest. In this variation, you start with discs 1, 3, 5, and 7 on the first peg, and discs 2, 4, 6, and 8 on the second peg, as shown in Figure 1. Your goal is to end up with all eight discs in order on the third peg, following both rules (a) and (b). What’s the fewest number of moves needed to accomplish this goal, and how do you do it? How do you know your solution is minimal?