The recursive solution of the Towers of Hanoi is famous; here you solve the puzzle with three stacks and a loop. Disks 1 (smallest) to n start on peg A and must end on peg C.
The iterative rule: number the moves 1, 2, 3, …, 2ⁿ − 1 and, for an odd n,
- move 1, 4, 7, … : the legal move between A and C;
- move 2, 5, 8, … : the legal move between A and B;
- move 3, 6, 9, … : the legal move between B and C.
For an even n, exchange the roles of B and C. Between two pegs exactly one move is legal: the smaller top disk goes onto the other peg (or onto the empty one).
Write HanoiStacks: read n; print every move when n ≤ 4; then always print the number of moves and the three pegs, top first. For the input
3
the program prints
Move 1: disk 1 from A to C
Move 2: disk 2 from A to B
Move 3: disk 1 from C to B
Move 4: disk 3 from A to C
Move 5: disk 1 from B to A
Move 6: disk 2 from B to C
Move 7: disk 1 from A to C
Moves: 7
Peg A (top first): []
Peg B (top first): []
Peg C (top first): [1, 2, 3]