Title: Solve the Tower of Hanoi puzzle in Python

[Some of the output for solving the Tower of Hanoi puzzle in Python]

In the Tower of Hanoi puzzle, you have three pegs and a stack of disks of different sizes. Initially the disks are all on one peg and ordered by size so each disk sits on top of a larger disk. Your goal is to move the stack to another peg while obeying these rules:

You can only move one disk at a time.
In each move, you take the top disk off of one peg and move it onto another peg.
You can never place a disk on a smaller disk.

To see an animation that shows how the game works, see this GIF on Wikipedia.

The puzzle was described by French mathematician Édouard Lucas in 1883. According to a made-up legend, some priests at a temple have been moving a stack of 64 disks and when they finish the universe will come to an end. If they can move 1 disk per second, it will take 2⁶⁴ - 1 seconds or around 585 billion years to finish moving the disks.

This example shows how you can write a Python program to solve the Tower of Hanoi puzzle. Keep the number of disks small until you know how long it will take. Even if your computer can make 1 million moves per second, it would take around 584,542 years to move 64 disks.

Preparing Pegs

As you might guess because in a Python program, this example represents the disks and pegs with lists. Disks are represented by their widths.

The following code creates the pegs and disks.

def make_pegs(num_disks): '''Create the pegs and disks.''' # Make the peg stacks. return [ [i for i in range(num_disks, 0, -1)], [], [], ]

This code creates a list of three lists to represent the pegs. It uses a list comprehension to initialize the first peg with the values num_disks, num_disks - 1, ..., 1.

While the program runs, the disk numbers (which represent the disk sizes) will always be arranged so larger sizes are at the beginning of the peg lists.

Drawing Disks

One of the more prosaic but tricky pieces of the program is the code that displays the moves. The following print_disks method displays the state of the pegs before a given move.

def print_disks(move_num, pegs): '''Print the current arrangement.''' print(f'Move {move_num}:') gap = 2 num_pegs = len(pegs) num_disks = sum(len(peg) for peg in pegs) max_wid = 2 * num_disks # The width of the largest disk. for row in range(num_disks - 1, -1, -1): for peg_num, peg in enumerate(pegs): if row >= len(peg): # We're above the disks. Print blank space. print(f'{" " * max_wid}', end='') else: # Print #'s across the width of the current disk. num_spaces = max_wid - 2 * peg[row] num_spaces_before = num_spaces // 2 num_spaces_after = num_spaces - num_spaces_before print( f'{" " * num_spaces_before}' f'{"#" * (2 * peg[row])}' f'{" " * num_spaces_after}', end='') if peg_num == num_pegs - 1: print() else: print(f'{" " * gap}', end='') for peg_num, peg in enumerate(pegs): print(f'{"=" * max_wid}', end='') if peg_num == num_pegs - 1: print() else: print(f'{" " * gap}', end='') print()

This code prints two # characters for each unit of disk size. For example, disk 1 is shown as ##.

After setting a few variables, the code enters a for loop to display each possible row of disks starting at the top of the stacks. If there are num_disks disks, then a stack could be up to num_disks tall. The for loop makes row range from num_disks - 1 down to 0. Recall that the larger numbers are closer to the start of a peg's list, so the row number starts at the top of the peg with smaller disks and moves down to the larger disks.

Inside the loop, the code loops through the peg numbers.

For each peg, the function checks whether the row number is greater than or equal to the peg's length. For example, suppose we have 6 disks and we're displaying row 4. If a peg only has 3 disks, they are in rows 0, 1, and 2 so this peg has no disks in row 4.

If the peg has no disks in this row, the code prints spaces repeated max_wid times, essentially making a blank row.

If the peg does have disks in this row, the code subtracts the peg's current disk width from the width of the largest disk to see how many spaces it must print. It then prints half of those spaces, a number of # characters to represent the disk, and the other half of the spaces.

After it finishes printing this peg's disk or spaces, the code starts a new line if this is the last peg, or it prints some spaces to make a gap before the next peg.

After the outer loop finishes printing all of the disks, the code loops through the pegs again and prints a sequence of # characters to represent the pegs' bases.

Here's an example:

Move 27: ######## ## ###### ########## #### ========== ========== ==========

This example used 5 disks so the peg output is 5 disks tall. Because the pegs with the most disks hold 2 disks, the output has three blank rows above the first disks.

Algorithm Analysis

It would be tricky to figure out which disk to move next on any given turn. Fortunately, recursion provides a straightforward solution. Instead of directly figuring out which disk to move, the algorithm follows these steps to move the disks from peg A to peg B while using peg C as temporary storage:

Recursively move all disks except the bottom one from peg A to peg C.
Move the bottom disk from peg A to peg B.
Recursively move all of the disks from peg C to peg B.

Here's an example:

Start: ## #### ###### ######## ########## ========== ========== ========== Recursively move all except the bottom disk from peg A to peg C: ## #### ###### ########## ######## ========== ========== ========== Move the bottom disk from peg A to peg B: ## #### ###### ########## ######## ========== ========== ========== Recursively move all disks from peg C to peg B: ## #### ###### ######## ########## ========== ========== ==========

You don't really need to figure out the moves one at a time; the recursion does that automatically. You just need to know how to move a single disk.

Directing Disks

The following move_disks function uses the algorithm to move the disks from peg from_peg to peg to_peg using peg temp_peg as temporary storage.

def move_disks(move_num, pegs, from_peg, to_peg, temp_peg, num_disks): ''' Move {num_disks} disks from {from_peg} to {to_peg} using {temp_peg} for temporary storage. Return the number of the next move. ''' if num_disks > 1: # We have more than one disk to move. # Recursively move all but one disk to the other peg. move_num = move_disks(move_num, pegs, from_peg, temp_peg, to_peg, num_disks - 1) # Move the remaining disk. pegs[to_peg].append(pegs[from_peg].pop()) move_num += 1 # Print the new arrangement. print_disks(move_num, pegs) if num_disks > 1: # Recursively move the other disks back where they belong. move_num = move_disks(move_num, pegs, temp_peg, to_peg, from_peg, num_disks - 1) # Return the new value of move_num. return move_num

First, if the number of disks we must move is greater than 1, the function calls itself recursively to move all of the disks except the bottom one to temp_peg.

Next, the code moves the bottom disk from from_peg to to_peg. It increments move_num to indicate that it moved a disk and calls print_disks to display the current arrangement.

Then, if the number of disks we must move is greater than 1, the function calls itself recursively again to move all of the disks from temp_peg to to_peg.

Finally, the function returns move_num so the calling function knows how many moves were made in total.

Managing Main

Here's the main program.

num_disks = 5 pegs = make_pegs(num_disks) print_disks(0, pegs) move_disks(0, pegs, 0, 1, 2, num_disks)

The program sets num_disks and calls make_pegs to initialize the pegs. It calls print_disks to display the initial configuration.

Next, the program calls move_disks to move the disks from peg 0 to peg 1 using peg 2 as temporary storage. The move_disks function does the rest.

Conclusion

This solution to the Tower of Hanoi puzzle is a classic example of recursion. Instead of trying to figure out how to perform each move at a low level, the move_disks function performs one simple move, calls itself recursively to do most of the work, and then makes another simple move.

Download the example to experiment with it and to see additional details.