(close)

Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

Prev: Tic-Tac-Toe | Next: Trick Questions
Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

Tower of Hanoi

The Tower of Hanoi is a stack-moving puzzle game that features three poles on which you can stack various-sized disks. The object of the game is to move one tower of disks to another pole. However, only one disk can be moved at a time, and larger disks cannot be placed on top of smaller ones. Figuring out a certain pattern will help you solve this puzzle. Can you discover it? (Hint: Try setting the `TOTAL_DISKS`

variable to `3`

or `4`

to solve an easier version first.)

When you run *towerofhanoi.py*, the output will look like this:

```
The Tower of Hanoi, by Al Sweigart [email protected]
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.)
>
```**ab**
|| || ||
|| || ||
@@_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.)
`--snip--`

The data structure that represents a tower is a list of integers. Each integer is the size of the disk. The first integer in the list represents the bottom disk, and the last integer represents the top disk. For example, `[5, 4, 2]`

would represent the following tower:

```
||
||
@@_2@@
@@@@_4@@@@
@@@@@_5@@@@@
```

Pythonâ€™s `append()`

and `pop()`

list methods can add and remove values from the end of the list, respectively. Just as `someList[0]`

and `someList[1]`

allow us to access the first and second values in a list, Python lets us use negative indexes to access values from the end of the list using expressions like `someList[-1]`

and `someList[-2]`

, which access the last and second-to-last values in a list, respectively. This is useful for finding the disk currently at the top of the tower.

```
1. """The Tower of Hanoi, by Al Sweigart [email protected]
2. A stack-moving puzzle game.
3. This code is available at https://nostarch.com/big-book-small-python-programming
4. Tags: short, game, puzzle"""
5.
6. import copy
7. import sys
8.
9. TOTAL_DISKS = 5 # More disks means a more difficult puzzle.
10.
11. # Start with all disks on tower A:
12. COMPLETE_TOWER = list(range(TOTAL_DISKS, 0, -1))
13.
14.
15. def main():
16. print("""The Tower of Hanoi, by Al Sweigart [email protected]
17.
18. Move the tower of disks, one disk at a time, to another tower. Larger
19. disks cannot rest on top of a smaller disk.
20.
21. More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
22. """
23. )
24.
25. # Set up the towers. The end of the list is the top of the tower.
26. towers = {'A': copy.copy(COMPLETE_TOWER), 'B': [], 'C': []}
27.
28. while True: # Run a single turn.
29. # Display the towers and disks:
30. displayTowers(towers)
31.
32. # Ask the user for a move:
33. fromTower, toTower = askForPlayerMove(towers)
34.
35. # Move the top disk from fromTower to toTower:
36. disk = towers[fromTower].pop()
37. towers[toTower].append(disk)
38.
39. # Check if the user has solved the puzzle:
40. if COMPLETE_TOWER in (towers['B'], towers['C']):
41. displayTowers(towers) # Display the towers one last time.
42. print('You have solved the puzzle! Well done!')
43. sys.exit()
44.
45.
46. def askForPlayerMove(towers):
47. """Asks the player for a move. Returns (fromTower, toTower)."""
48.
49. while True: # Keep asking player until they enter a valid move.
50. print('Enter the letters of "from" and "to" towers, or QUIT.')
51. print('(e.g. AB to moves a disk from tower A to tower B.)')
52. response = input('> ').upper().strip()
53.
54. if response == 'QUIT':
55. print('Thanks for playing!')
56. sys.exit()
57.
58. # Make sure the user entered valid tower letters:
59. if response not in ('AB', 'AC', 'BA', 'BC', 'CA', 'CB'):
60. print('Enter one of AB, AC, BA, BC, CA, or CB.')
61. continue # Ask player again for their move.
62.
63. # Syntactic sugar - Use more descriptive variable names:
64. fromTower, toTower = response[0], response[1]
65.
66. if len(towers[fromTower]) == 0:
67. # The "from" tower cannot be an empty tower:
68. print('You selected a tower with no disks.')
69. continue # Ask player again for their move.
70. elif len(towers[toTower]) == 0:
71. # Any disk can be moved onto an empty "to" tower:
72. return fromTower, toTower
73. elif towers[toTower][-1] < towers[fromTower][-1]:
74. print('Can\'t put larger disks on top of smaller ones.')
75. continue # Ask player again for their move.
76. else:
77. # This is a valid move, so return the selected towers:
78. return fromTower, toTower
79.
80.
81. def displayTowers(towers):
82. """Display the current state."""
83.
84. # Display the three towers:
85. for level in range(TOTAL_DISKS, -1, -1):
86. for tower in (towers['A'], towers['B'], towers['C']):
87. if level >= len(tower):
88. displayDisk(0) # Display the bare pole with no disk.
89. else:
90. displayDisk(tower[level]) # Display the disk.
91. print()
92.
93. # Display the tower labels A, B, and C.
94. emptySpace = ' ' * (TOTAL_DISKS)
95. print('{0} A{0}{0} B{0}{0} C\n'.format(emptySpace))
96.
97.
98. def displayDisk(width):
99. """Display a disk of the given width. A width of 0 means no disk."""
100. emptySpace = ' ' * (TOTAL_DISKS - width)
101.
102. if width == 0:
103. # Display a pole segment without a disk:
104. print(emptySpace + '||' + emptySpace, end='')
105. else:
106. # Display the disk:
107. disk = '@' * width
108. numLabel = str(width).rjust(2, '_')
109. print(emptySpace + disk + numLabel + disk + emptySpace, end='')
110.
111.
112. # If the program is run (instead of imported), run the game:
113. if __name__ == '__main__':
114. main()
```

Try to find the answers to the following questions. Experiment with some modifications to the code and rerun the program to see what effect the changes have.

- What happens if you delete or comment out lines 73, 74, and 75?
- What happens if you change
`emptySpace = ' ' * (TOTAL_DISKS - width)`

on line 100 to`emptySpace = ' '`

? - What happens if you change
`width == 0`

on line 102 to`width != 0`

?