Tower of Hanoi

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is given by the formula:

M = 2^n - 1

where n is the number of disks.

Algorithm

The Tower of Hanoi puzzle can be solved using a recursive algorithm. The algorithm works by breaking the problem down into smaller subproblems.

The basic idea is to move all but the largest disk from the source rod to an intermediate rod. This leaves the largest disk on the source rod. We can then move the largest disk to the destination rod. Finally, we can move the disks from the intermediate rod to the destination rod.

The following is a recursive algorithm for solving the Tower of Hanoi puzzle:

def hanoi(n, source, intermediate, destination):
  """
  Move n disks from the source rod to the destination rod, using the intermediate rod.

  Args:
    n: The number of disks to move.
    source: The rod to move the disks from.
    intermediate: The intermediate rod.
    destination: The rod to move the disks to.
  """

  if n == 1:
    # Base case: Move the only disk from the source rod to the destination rod.
    print(f"Move disk 1 from {source} to {destination}")
    return

  # Recursive case: Move n-1 disks from the source rod to the intermediate rod.
  hanoi(n-1, source, destination, intermediate)

  # Move the largest disk from the source rod to the destination rod.
  print(f"Move disk {n} from {source} to {destination}")

  # Move n-1 disks from the intermediate rod to the destination rod.
  hanoi(n-1, intermediate, source, destination)

Example

The following is an example of how to use the hanoi() function to solve the Tower of Hanoi puzzle with 3 disks:

hanoi(3, "A", "B", "C")

This will print the following output:

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

This output shows the steps required to move the 3 disks from rod A to rod B.