How to Solve the Tower of Hanoi Puzzle Using Python?

The Tower of Hanoi is a classic puzzle that involves moving a stack of discs of different sizes from one peg to another, with the constraint that a larger disc cannot be placed on top of a smaller disc. Here’s how to solve the Tower of Hanoi puzzle using Python:

``````def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 1:
print("Move disk 1 from rod", from_rod, "to rod", to_rod)
return
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)

# Example usage:
tower_of_hanoi(3, 'A', 'C', 'B')``````

In this example, the `tower_of_hanoi()` function is defined recursively to solve the puzzle for a given number of discs `n` and starting and target pegs `from_rod` and `to_rod`. The `aux_rod` argument represents the auxiliary peg that is used to move the discs.

The base case of the recursion is when there is only one disc to move, in which case it is simply moved from `from_rod` to `to_rod`. For larger values of `n`, the function calls itself recursively twice, once to move the top `n-1` discs from `from_rod` to `aux_rod` using `to_rod` as the auxiliary peg, and again to move the bottom disc from `from_rod` to `to_rod`, using `aux_rod` as the auxiliary peg.

When the function is called with `tower_of_hanoi(3, 'A', 'C', 'B')` in the example, it solves the puzzle for 3 discs, starting from peg A and moving to peg C, using peg B as the auxiliary peg. The output shows the sequence of moves required to solve the puzzle:

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

Note that this function only prints out the sequence of moves required to solve the puzzle. If you want to track the state of the pegs at each step, you’ll need to modify the function to use a data structure to represent the state of the puzzle.