Tower of Hanoi Puzzle

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.)

The Program in Action

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--

How It Works

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.

Download Source Code

  1. """The Tower of Hanoi, by Al Sweigart [email protected]
  2. A stack-moving puzzle game.
  3. View this code at https://nostarch.com/big-book-small-python-projects
  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()

Exploring the Program

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?