13.1. The Tower of Hanoi¶
The Tower of Hanoi puzzle uses a stack of disks of different sizes. The disks have holes in their centers, so you can place them over one of three poles (Figure 14-1). To solve the puzzle, the player must move the stack of disks to one of the other poles. There are three restrictions:
The player can move only one disk at a time.
The player can only move disks to and from the top of a tower.
The player can never place a larger disk on top of a smaller disk.
Figure 14-1: A physical Tower of Hanoi puzzle set
Solving this puzzle is a common computer science problem used for teaching recursive algorithms. Our program won’t solve this puzzle; rather, it will present the puzzle to a human player to solve. You’ll find more informa- tion about the Tower of Hanoi at https://en.wikipedia.org/wiki/Tower_of_Hanoi. ## The Output The Tower of Hanoi program displays the towers as ASCII art by using text characters to represent the disks. It might look primitive compared to mod- ern apps, but this approach keeps the implementation simple, because we only need print() and input() calls to interact with the user. When you run the program, the output will look something like the following. The text the player enters is in bold.
For n disks, it takes a minimum of 2 n – 1 moves to solve the Tower of Hanoi. So this five-disk tower requires 31 steps: AC, AB, CB, AC, BA, BC, AC, AB, CB, CA, BA, CB, AC, AB, CB, AC, BA, BC, AC, BA, CB, CA, BA, BC, AC, AB, CB, AC, BA, BC, and finally AC. If you want a greater chal- lenge to solve on your own, you can increase the TOTAL_DISKS variable in the program from 5 to 6 .
13.1.1. The Source Code¶
Open a new file in your editor or IDE, and enter the following code. Save it as towerofhanoi.py.
>>> # """THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com A stack-moving puzzle game."""
>>> import copy
>>> import sys
>>> TOTAL_DISKS = 5
>>> # More disks means a more difficult puzzle.
>>> # Start with all disks on tower A:
>>> SOLVED_TOWER = list(range(TOTAL_DISKS, 0, -1))
>>> def main():
>>> # """Runs a single game of The Tower of Hanoi."""
>>> print(
>>> """THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
>>> Move the tower of disks, one disk at a time, to another tower. Larger
>>> disks cannot rest on top of a smaller disk.
>>> More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
>>> """
>>> )
>>> # """The towers dictionary has keys "A", "B", and "C" and values
>>> # that are lists representing a tower of disks. The list contains
>>> # integers representing disks of different sizes, and the start of
>>> # the list is the bottom of the tower. For a game with 5 disks,
>>> # the list [5, 4, 3, 2, 1] represents a completed tower. The blank
>>> # list [] represents a tower of no disks. The list [1, 3] has a
>>> # larger disk on top of a smaller disk and is an invalid
>>> # configuration. The list [3, 1] is allowed since smaller disks
>>> # can go on top of larger ones."""
>>> towers = {"A": copy.copy(SOLVED_TOWER), "B": [], "C": []}
>>> while True: # Run a single turn on each iteration of this loop.
>>> # Display the towers and disks:
>>> displayTowers(towers)
>>> # Ask the user for a move:
>>> fromTower, toTower = getPlayerMove(towers)
>>> # Move the top disk from fromTower to toTower:
>>> disk = towers[fromTower].pop()
>>> towers[toTower].append(disk)
>>> # Check if the user has solved the puzzle:
>>> if SOLVED_TOWER in (towers["B"], towers["C"]):
>>> displayTowers(towers) # Display the towers one last time.
>>> print("You have solved the puzzle! Well done!")
>>> sys.exit()
>>> def getPlayerMove(towers):
>>> # """Asks the player for a move. Returns (fromTower, toTower)."""
>>> while True: # Keep asking player until they enter a valid move.
>>> print('Enter the letters of "from" and "to" towers, or QUIT.')
>>> print("(e.g., AB to moves a disk from tower A to tower B.)")
>>> print()
>>> response = input("> ").upper().strip()
>>> if response == "QUIT":
>>> print("Thanks for playing!")
>>> sys.exit()
>>> # Make sure the user entered valid tower letters:
>>> if response not in ("AB", "AC", "BA", "BC", "CA", "CB"):
>>> print("Enter one of AB, AC, BA, BC, CA, or CB.")
>>> continue # Ask player again for their move.
>>> # Use more descriptive variable names:
>>> fromTower, toTower = response[0], response[1]
>>> if len(towers[fromTower]) == 0:
>>> # The "from" tower cannot be an empty tower:
>>> print("You selected a tower with no disks.")
>>> continue # Ask player again for their move.
>>> elif len(towers[toTower]) == 0:
>>> # Any disk can be moved onto an empty "to" tower:
>>> return fromTower, toTower
>>> elif towers[toTower][-1] < towers[fromTower][-1]:
>>> print("Can't put larger disks on top of smaller ones.")
>>> continue # Ask player again for their move.
>>> else:
>>> # This is a valid move, so return the selected towers:
>>> return fromTower, toTower
>>> def displayTowers(towers):
>>> # """Display the three towers with their disks."""
>>> # Display the three towers:
>>> for level in range(TOTAL_DISKS, -1, -1):
>>> for tower in (towers["A"], towers["B"], towers["C"]):
>>> if level >= len(tower):
>>> displayDisk(0) # Display the bare pole with no disk.
>>> else:
>>> displayDisk(tower[level]) # Display the disk.
>>> print()
>>> # Display the tower labels A, B, and C:
>>> emptySpace = " " * (TOTAL_DISKS)
>>> print("{0} A{0}{0} B{0}{0} C\n".format(emptySpace))
>>> def displayDisk(width):
>>> # """Display a disk of the given width. A width of 0 means no disk."""
>>> emptySpace = " " * (TOTAL_DISKS - width)
>>> if width == 0:
>>> # Display a pole segment without a disk:
>>> print(f"{emptySpace}||{emptySpace}", end="")
>>> else:
>>> # Display the disk:
>>> disk = "@" * width
>>> numLabel = str(width).rjust(2, "_")
>>> print(f"{emptySpace}{disk}{numLabel}{disk}{emptySpace}", end="")
>>> # If this program was run (instead of imported), run the game:
>>> if __name__ == "__main__":
>>> main()
THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Move the tower of disks, one disk at a time, to another tower. Larger
disks cannot rest on top of a smaller disk.
More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
|| || ||
@_1@ || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || ||
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> AC
|| || ||
|| || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || @_1@
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> AC
Can't put larger disks on top of smaller ones.
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> to
Enter one of AB, AC, BA, BC, CA, or CB.
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> CA
|| || ||
@_1@ || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || ||
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> QUIT
Thanks for playing!
An exception has occurred, use %tb to see the full traceback.
SystemExit
Run this program and play a few games to get an idea of what this pro- gram does before reading the explanation of the source code. To check for typos, copy and paste it to the online diff tool at https://inventwithpython.com/ beyond/diff/. ## Writing the Code Let’s take a closer look at the source code to see how it follows the best prac- tices and patterns described in this book.
We’ll begin at the top of the program:
>>> """THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
>>> A stack-moving puzzle game."""
'THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.comnA stack-moving puzzle game.'
The program starts with a multiline comment that serves as a docstring for the towerofhanoi module. The built-in help() function will use this infor- mation to describe the module:
>>> import towerofhanoi
>>> help(towerofhanoi)
Help on module towerofhanoi:
NAME
towerofhanoi
DESCRIPTION
THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
A stack-moving puzzle game.
252
Chapter 14FUNCTIONS
displayDisk(width)
Display a single disk of the given width.
--snip--
You can add more words, even paragraphs of information, to the mod- ule’s docstring if you need to. I’ve written only a small amount here because the program is so simple.
After the module docstring are the import statements:
import copy import sys
Black formats these as separate statements rather than a single one, such as import copy, sys . This makes the addition or removal of imported modules easier to see in version control systems, such as Git, that track changes programmers make.
Next, we define the constants this program will need:
>>> TOTAL_DISKS = 5
>>> # More disks means a more difficult puzzle.
>>> # Start with all disks on tower A:
>>> SOLVED_TOWER = list(range(TOTAL_DISKS, 0, -1))
We define these near the top of the file to group them together and make them global variables. We’ve written their names in capitalized snake_case to mark them as constants.
The TOTAL_DISKS constant indicates how many disks the puzzle has. The SOLVED_TOWER variable is an example of a list that contains a solved tower: it contains every disk with the largest at the bottom and the smallest at the top. We generate this value from the TOTAL_DISKS value, and for five disks it’s [5, 4, 3, 2, 1] .
Notice that there are no type hints in this file. The reason is that we can infer the types of all variables, parameters, and return values from the code. For example, we’ve assigned the TOTAL_DISKS constant the integer value 5 . From this, type checkers, such as Mypy, would infer that TOTAL_DISKS should contain integers only.
We define a main() function, which the program calls near the bottom of the file:
>>> def main():
>>> # """Runs a single game of The Tower of Hanoi."""
>>> print(
>>> """THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
>>> Move the tower of disks, one disk at a time, to another tower. Larger
>>> disks cannot rest on top of a smaller disk.
>>> More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
>>> """
>>> )
Functions can have docstrings, too. Notice the docstring for main() below the def statement. You can view this docstring by running import towerofhanoi and help(towerofhanoi.main) from the interactive shell.
Next, we write a comment that extensively describes the data structure we use to represent the tower, because it forms the core of how this pro- gram works:
>>> """The towers dictionary has keys "A", "B", and "C" and values
>>> that are lists representing a tower of disks. The list contains
>>> integers representing disks of different sizes, and the start of
>>> the list is the bottom of the tower. For a game with 5 disks,
>>> the list [5, 4, 3, 2, 1] represents a completed tower. The blank
>>> list [] represents a tower of no disks. The list [1, 3] has a
>>> larger disk on top of a smaller disk and is an invalid
>>> configuration. The list [3, 1] is allowed since smaller disks
>>> can go on top of larger ones."""
>>> towers = {"A": copy.copy(SOLVED_TOWER), "B": [], "C": []}
We use the SOLVED_TOWER list as a stack, one of the simplest data structures in software development. A stack is an ordered list of values altered only through adding (also called pushing) or removing (also called popping) val- ues from the top of the stack. This data structure perfectly represents the tower in our program. We can turn a Python list into a stack if we use the append() method for pushing and the pop() method for popping, and avoid altering the list in any other way. We’ll treat the end of the list as the top of the stack.
Each integer in the towers list represents a single disk of a certain size. For example, in a game with five disks, the list [5, 4, 3, 2, 1] would repre- sent a full stack of disks from the largest ( 5 ) at the bottom to the smallest( 1 ) at the top.
Notice that our comment also provides examples of a valid and invalid tower stack.
Inside the main() function, we write an infinite loop that runs a single turn of our puzzle game:
>>> while True: # Run a single turn on each iteration of this loop.
>>> # Display the towers and disks:
>>> displayTowers(towers)
>>> # Ask the user for a move:
>>> fromTower, toTower = getPlayerMove(towers)
>>> # Move the top disk from fromTower to toTower:
>>> disk = towers[fromTower].pop()
>>> towers[toTower].append(disk)
|| || ||
@_1@ || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || ||
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> QUIT
Thanks for playing!
An exception has occurred, use %tb to see the full traceback.
SystemExit
In a single turn, the player views the current state of the towers and enters a move. The program then updates the towers data structure. We’ve hid the details of these tasks in the displayTowers() and getPlayerMove() func- tions. These descriptive function names allow the main() function to provide a general overview of what the program does.
The next lines check whether the player has solved the puzzle by com- paring the complete tower in SOLVED_TOWER to towers[“B”] and towers[“C”] :
>>> # Check if the user has solved the puzzle:
>>> if SOLVED_TOWER in (towers["B"], towers["C"]):
>>> displayTowers(towers) # Display the towers one last time.
>>> print("You have solved the puzzle! Well done!")
>>> sys.exit()
We don’t compare it to towers[“A”] , because that pole begins with an already complete tower; a player needs to form the tower on the B or C poles to solve the puzzle. Note that we reuse SOLVED_TOWER to make the starting tow- ers and check whether the player solved the puzzle. Because SOLVED_TOWER is a constant, we can trust that it will always have the value we assigned to it at the beginning of the source code.
The condition we use is equivalent to but shorter than SOLVED_TOWER == towers[“B”] or SOLVED_TOWER == towers[“C”] , a Python idiom we covered in Chapter 6. If this condition is True , the player has solved the puzzle, and we end the program. Otherwise, we loop back for another turn.
The getPlayerMove() function asks the player for a disk move and vali- dates the move against the game rules:
>>> def getPlayerMove(towers):
>>> # """Asks the player for a move. Returns (fromTower, toTower)."""
>>> while True: # Keep asking player until they enter a valid move.
>>> print('Enter the letters of "from" and "to" towers, or QUIT.')
>>> print("(e.g., AB to moves a disk from tower A to tower B.)")
>>> print()
>>> response = input("> ").upper().strip()
We start an infinite loop that continues looping until either a return state- ment causes the execution to leave the loop and function or a sys.exit() call terminates the program. The first part of the loop asks the player to enter a move by specifying from and to towers.
Notice the input(“>”).upper().strip() instruction that receives key- board input from the player. The input(“>”) call accepts text input from the player by presenting a > prompt. This symbol indicates that the player should enter something. If the program didn’t present a prompt, the player might momentarily think the program had frozen.
We call the upper() method on the string returned from input() so it returns an uppercase form of the string. This allows the player to enter either uppercase or lowercase tower labels, such as ‘a’ or ‘A’ for tower A. In turn, the uppercase string’s strip() method is called, returning a string without any whitespace on either side in case the user accidentally added a space when entering their move. This user friendliness makes our program slightly easier for players to use.
Still in the getPlayerMove() function, we check the input the user enters:
>>> response = "QUIT"
>>> if response == "QUIT":
>>> print("Thanks for playing!")
>>> sys.exit()
>>> # Make sure the user entered valid tower letters:
>>> if response not in ("AB", "AC", "BA", "BC", "CA", "CB"):
>>> print("Enter one of AB, AC, BA, BC, CA, or CB.")
>>> continue # Ask player again for their move.
Thanks for playing!
An exception has occurred, use %tb to see the full traceback.
SystemExit
If the user enters ‘QUIT’ (in any case, or even with spaces at the begin- ning or end of the string, due to the calls to upper() and strip() ), the program terminates. We could have made getPlayerMove() return ‘QUIT’ to indicate to the caller that it should call sys.exit() , rather than have getPlayerMove() call sys.exit() . But this would complicate the return value of getPlayerMove() : it would return either a tuple of two strings (for the player’s move) or a single ‘QUIT’ string. A function that returns values of a single data type is easier to understand than a function that can return values of many possible types. I discussed this in “Return Values Should Always Have the Same Data Type” on page 177.
Between the three towers, only six to-from tower combinations are possible. Despite the fact that we hardcoded all six values in the condition that checks the move, the code is much easier to read than something like len(response) != 2 or response[0] not in ‘ABC’ or response[1] not in ‘ABC’ or response[0] == response[1] . Given these circumstances, the hardcoding approach is the most straightforward.
Generally, it’s considered bad practice to hardcode values such as “AB” , “AC” , and other values as magic values, which are valid only as long as the program has three poles. But although we might want to adjust the number of disks by changing the TOTAL_DISKS constant, it’s highly unlikely that we’ll add more poles to the game. Writing out every possible pole move on this line is fine.
We create two new variables, fromTower and toTower , as descriptive names for the data. They don’t serve a functional purpose, but they make the code easier to read than response[0] and response[1] :
>>> # Use more descriptive variable names:
>>> fromTower, toTower = response[0], response[1]
Next, we check whether or not the selected towers constitute a legal move:
if len(towers[fromTower]) == 0: # The "from" tower cannot be an empty tower:
print("You selected a tower with no disks.") continue # Ask player again for their move.
elif len(towers[toTower]) == 0: # Any disk can be moved onto an empty "to" tower:
return fromTower, toTower
- elif towers[toTower][-1] < towers[fromTower][-1]:
print("Can't put larger disks on top of smaller ones.") continue # Ask player again for their move.
If not, a continue statement causes the execution to move back to the beginning of the loop, which asks the player to enter their move again. Note that we check whether toTower is empty; if it is, we return fromTower, toTower to emphasize that the move was valid, because you can always put a disk on an empty pole. These first two conditions ensure that by the time the third condition is checked, towers[toTower] and towers[fromTower] won’t be empty or cause an IndexError . We’ve ordered these conditions in such a way to prevent IndexError or additional checking.
It’s important that your programs handle any invalid input from the user or potential error cases. Users might not know what to enter, or they might make typos. Similarly, files could unexpectedly go missing, or data- bases could crash. Your programs need to be resilient to the exceptional cases; otherwise, they’ll crash unexpectedly or cause subtle bugs later on. If none of the previous conditions are True , getPlayerMove() returns fromTower, toTower :
else: # This is a valid move, so return the selected towers: return fromTower, toTower
In Python, return statements always return a single value. Although this return statement looks like it returns two values, Python actually returns a single tuple of two values, which is equivalent to return (fromTower, toTower) . Python programmers often omit the parentheses in this context. The paren- theses don’t define a tuple as much as the commas do.
Notice that the program calls the getPlayerMove() function only once from the main() function. The function doesn’t save us from duplicate code, which is the most common purpose for using one. There’s no reason we couldn’t put all the code in getPlayerMove() in the main() function. But we can also use functions as a way to organize code into separate units, which is how we’re using getPlayerMove() . Doing so prevents the main() function from becoming too long and unwieldy.
The displayTowers() function displays the disks on towers A, B, and C in the towers argument:
>>> def displayTowers(towers):
>>> # """Display the three towers with their disks."""
>>> # Display the three towers:
>>> for level in range(TOTAL_DISKS, -1, -1):
>>> for tower in (towers["A"], towers["B"], towers["C"]):
>>> if level >= len(tower):
>>> displayDisk(0) # Display the bare pole with no disk.
>>> else:
>>> displayDisk(tower[level]) # Display the disk.
>>> print()
It relies on the displayDisk() function, which we’ll cover next, to display each disk in the tower. The for level loop checks every possible disk for a tower, and the for tower loop checks towers A, B, and C.
The displayTowers() function calls displayDisk() to display each disk at a specific width, or if 0 is passed, the pole with no disk:
>>> # Display the tower labels A, B, and C:
>>> emptySpace = ' ' * (TOTAL_DISKS)
>>> print('{0} A{0}{0} B{0}{0} C\n'.format(emptySpace))
A B C
We display the A, B, and C labels onscreen. The player needs this infor- mation to distinguish between the towers and to reinforce that the towers are labeled A, B, and C rather than 1, 2, and 3 or Left, Middle, and Right. I chose not to use 1, 2, and 3 for the tower labels to prevent players from con- fusing these numbers with the numbers used for the disks’ sizes.
We set the emptySpace variable to the number of spaces to place in between each label, which in turn is based on TOTAL_DISKS , because the more disks in the game, the wider apart the poles are. Rather than use an f-string, as in print(f’{emptySpace} A{emptySpace}{emptySpace} B{emptySpace}{emptySpace} C:raw-latex:n’) , we use the format() string method. This allows us to use the same emptySpace argument wherever {0} appears in the associated string, producing shorter and more readable code than the f-string version.
The displayDisk() function displays a single disk along with its width. If no disk is present, it displays just the pole:
>>> def displayDisk(width):
>>> # """Display a disk of the given width. A width of 0 means no disk."""
>>> emptySpace = ' ' * (TOTAL_DISKS - width)
>>> if width == 0:
>>> # Display a pole segment without a disk:
>>> print(f'{emptySpace}||{emptySpace}', end='')
>>> else:
>>> # Display the disk:
>>> disk = '@' * width
>>> numLabel = str(width).rjust(2, '_')
>>> print(f"{emptySpace}{disk}{numLabel}{disk}{emptySpace}", end='')
We represent a disk using a leading empty space, a number of @ char- acters equal to the disk width, two characters for the width (including an underscore if the width is a single digit), another series of @ characters, and then the trailing empty space. To display just the empty pole, all we need are the leading empty space, two pipe characters, and trailing empty space. As a result, we’ll need six calls to displayDisk() with six different arguments for width to display the following tower:
||
@_1@
@@_2@@
@@@_3@@@
@@@@_4@@@@
@@@@@_5@@@@@
Notice how the displayTowers() and displayDisk() functions split the responsibility of displaying the towers. Although displayTowers() decides how to interpret the data structures that represent each tower, it relies on displayDisk() to actually display each disk of the tower. Breaking your pro- gram into smaller functions like this makes each part easier to test. If the program displays the disks incorrectly, the problem is likely in displayDisk() . If the disks appear in the wrong order, the problem is likely in displayTowers() . Either way, the section of code you’ll have to debug will be much smaller.
To call the main() function, we use a common Python idiom:
# If this program was run (instead of imported), run the game: if __name__ == '__main__':
main()
Python automatically sets the __name__ variable to ’__main__’ if a player runs the towerofhanoi.py program directly. But if someone imports the pro- gram as a module using import towerofhanoi , then __namewould be set to ‘towerofhanoi’ . The if __name == ’__main__’: line will call the main() func- tion if someone runs our program, starting a game of Tower of Hanoi. But if we simply want to import the program as a module so we could, say, call the individual functions in it for unit testing, this condition will be False and main() won’t be called.