Towers of Hanoi

From Wikipedia:

The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
• No disk may be placed on top of a disk that is smaller than it.

Use this template to write a recursive solution to the Towers of Hanoi problem.

#!/usr/bin/env python3

"""
towers1.py
This program uses recursion to display a solution to the Towers of Hanoi
problem. 
"""

def move(height, source, intermediate, destination):
    """Determines the next move that should be made to move a disk."""
    
    # Base case goes here
    
    if  # base case happens:
        # print instruction on what to do            
           
    else:
        # This is where the magic happens. If we haven't yet gotten
        # to a height of 1--if we're starting with 4 disks, say--
        # we'll first move the 3 disks to the intermediate location,
        # using destination as an intermediate.
        
        
        # Once we've completed that, let's move the one remaining over.
        # Print the instruction on what to do.
        
        
        # Now move the remaining disks over using the source tower as
        # an intermediate!
        
        



def main():
    print("Solving the 'Towers of Hanoi' problem")
    height = 3
    move(height, "A", "B", "C")
    print("Solution completed")

if __name__ == "__main__":
    main()

Extension

Create a more graphical version of the three towers, with each tower's disks represented as number in a list.

Tower A might begin as a = [4, 3, 2, 1]
Tower B would initially have no disks: b = []
Tower C as well: c = []

To move a disk, remove it from a source tower...

disk = a.pop()

... and put it on top of a destination tower:

c.append(disk)

An outline of one possible solution is given in this template:

#!/usr/bin/env python3

"""
towers2.py
This program uses recursion to display a solution to the Towers of Hanoi
problem.

In this version, we'll display disk values on the screen so that we have
a crude graphical representation of the status of the towers as we go.
"""

from os import system
from time import sleep

def display():
    """Displays the current state of all three lists.
    """
    system("clear")
    """Displays the state of the global lists a, b, c."""
    print("A | ",a)
    print("B | ",b)
    print("C | ",c)
    print()
    sleep(0.3)

def move(depth, source, intermediate, destination):
    """Determines the next move that should be made to move a disk."""
    if depth == 1:      # if just one disk left, move it!
        # Instead of printing "move a disk," we're going to 
        # move an item from the source list to the destination list
        print("move a disk from",source,"to",destination)
        
        display()           # show updated state
    
    else:
        # This is where the magic happens. If we haven't yet gotten
        # to a height of 1--if we're starting with 4 disks, say--
        # we'll first move the 3 disks to the intermediate location,
        # using destination as an intermediate.
        
        
        # Once we've completed that, let's move the one remaining over:
        # print("move a disk from",source,"to",destination)
        
        
        
        # Now move the remaining disks over using the source tower as
        # an intermediate!
        



def main():
    print("Solving the 'Towers of Hanoi' problem using lists to maintain")
    print("the state of the disks on the towers.")
    HEIGHT = 3
    # Declaring a, b, and c as global variables 
    global a, b, c 
    # Initialize all three towers as lists, with A containing the initial
    # disks, and B and C empty
    
    
    
    display()
    move(HEIGHT, a, b, c) 
    print("Solution completed")

if __name__ == "__main__":
    main()