My favorite reality show to watch is Survivor and I’ve been a fan since the first season came out in 2000. It’s a show I keep up with and watch for nostalgia, background noise, or distraction. This last reason is why I found myself watching an old season of survivor last week after going by myself to see the horror movie Obsession. I was scared and figured rewatching an old season of survivor was what I needed to stop being afraid of the dark. The season I watched started off with a physical logic puzzle that goes by the name “Tower of Hanoi”. The game consists of five rings of increasing size and three wooden pegs as shown below in a SolidWorks mockup.

The goal of the game is to move all the rings from the left peg to the right peg. You can only move one ring at a time and a ring of larger size can never be placed on a ring of smaller size. A legal move in this puzzle can be seen below in Figure 2 where the smallest ring is placed on the far right peg.

An illegal move can be seen in Figure 3 where the second smallest ring is placed on the smallest ring. This is not allowed as the rings have to be placed in descending order. A ring is not allowed to be placed upon a smaller ring.

While watching the puzzle play out on my television I wondered how one could determine the optimal method for solving the puzzle and the minimum amount of moves needed depending on the number of rings one starts with.

I started looking into this question by solving the puzzle with one, two, three, and four rings. The solution steps I used for these are below. Obviously one ring was super easy.

For the first iterations with one, two, or three rings it is obvious where to put the smallest ring first. This is not the case for the puzzle with four rings. Above you can see in my solution I put the smallest ring at the adjacent peg and not the peg furthest away. I wondered what would happen if I changed this and tried it below in Figure 7. My attempt stopped when I would have had to retrace steps I took.

Looking at the solutions it is clear there is a pattern as to where the smallest ring has to be placed first. If the number of rings is odd the smallest ring is placed first on the peg that is the final destination. If the number of rings is even the ring is placed first on the adjacent free peg. This happens I believe due to how one can break down these problems.

Let’s assume the one ring system is an edge case and move on to multiple ring systems. For added clarification we will name the rings based on size so the smallest ring is R1, the second smallest is R2, and so forth. The pegs are numbered one to three from left to right. The steps for the solution for the two ring system are the following

1. Smallest (R1) to adjacent (P2)
2. Largest (R2) to destination (P3)
3. Smallest (R1) to destination (P3)

Now let’s look at the solution set for the three ring system below.

1. Smallest (R1) to destination (P3)
2. Middle (R2) to adjacent (P2)
3. Smallest (R1) to adjacent (P2)
4. Largest (R3) to destination (P3)
5. Smallest (R1) to start (P1)
6. Middle (R2) to destination (P3)
7. Smallest (R1) to destination (P3)

A pattern seemingly emerges in that to solve a system of N number of rings it requires you to first solve the system for N-1 rings and place them at the adjacent peg in order for the Nth ring to be freed and moved to the destination peg. Once this is completed one then uses the steps again for a N-1 ring system to place them at the destination peg. Below is an image that hopefully illustrates this. The destination peg and adjacent peg for a system of N number of rings is always P3 and P2 respectively; however, the destination of their N-1 solution sets are not the same as the system’s.

This pattern carries over no matter the number of rings. Let’s examine the steps needed to solve an N=5 system by working backwards.

When first looking at an N=5 system (Fig.5), it looks daunting and impossible to determine the correct first move. Working backwards helps as we know that the fifth ring needs to be free in order to be able to move to peg three (Step 1, Fig. 5). For R5 to be free and able to move to P3 there must be no rings above R5 on P1 and P3 must be empty as R5 is bigger than every other ring. Therefore rings one through four must be on P2 (Step 2, Fig. 5). Moving R1-R4 to P2 would first require R4 to be moved to P2 and for this to be possible R1-R3 would need to no longer be above R4 and be on P3 (Step 3, Fig. 5). Placing rings R1-R3 on P3 would first require R3 to be placed on P3 and for this to happen R1-R2 would have to be no longer be on P1 and they can’t be on P3 so they would need to be placed on P2 (Step 4, Fig. 5).

I struggled to find a way to graphically represent adjacent/destination pegs and how they are different depending on which N-n solution set being examined in an N ring system. However, I landed on this drawing (Fig 10) as I feel like it both represents this concept and the flow of moves.

Because the key to solving any N ring system to is continually solve N-n systems until you solve the N-1 system, move the Nth ring, and then solve the N-1 system again, the optimal moves for a N ring system is double the moves of a N-1 system plus one as shown in the below equation.

The number of moves needed for the N-1 system is found by using the below variant of the equation and so on for N-2, N-3, etc.

Let’s do some substitution with the M(N) equation and simplify.

Now let’s plug in the formula for M(N-2). Notice I am not writing out the solution of two to the second power nor adding two plus one above as we are trying to find a pattern.

The pattern here is the following equation and its simplification (I had to use PowerPoint to create an image of the equation as WordPress doesn’t seem to know how to handle more than one character in an exponent.).

The first equation in the above set of three equations shows the pattern we found by using substitution. The second equation is the result of when k = N. When this happens the first part of the equation disappears as there are no moves to be made when there are no rings. Eliminating the first part of the second equation gives us the third equation as we can substitute N for k.

Using the series equation above the optimal number of moves for an N ring system can be calculated! I want to find the closed form and thus had to go looking at series summation simplifications as I definitely do not know these by heart.

The formula for a geometric series and the sum of a geometric series appear to be what are needed here. These formulas is the following.

The first formula in the above image shows the geometric sequence and its summation notation. The series starts with i equaling 0 and the final term for i equaling G. The second equation above shows the closed form equation for the summation of such a series.

To find the closed form summation equation for our formula M(N) we must determine if our equation matches the pattern and conditions of the above equations and the corresponding values of a, r, and G. We can see that our formula, M(N), does indeed match the pattern and conditions as our first term is two to the zero power which simplifies to one. The value for a is one, the value for r is two, and the value for G is N-1. We then plug these values in to the equation for the close form geometric series summation equation and have the following result.

We can simplify this equation with the following steps.

The optimal number of moves to solve a Tower of Hanoi puzzle with N number of rings is two to the Nth power minus one.

Text Based Python Game

Moving past knowing the equation for the optimal number of moves to solve a Tower of Hanoi puzzle with N number of rings, I wondered if I was able to create a text based game for this puzzle using Python. I had been wanting to learn Python for some time and figured this could be a project I could use to kickstart this journey. I had had experience coding in the past with Matlab and C++ but never Python.

To keep things simple for myself I set about to keep this game text based rather than using any graphics and display the rings using simple lists. Lists in my opinion would be a viable substitute to any graphics as they could easily convey the order the rings were stacked, their size, and could be easily edited. In addition, by using lists I could give the user only access the the next item in the list and therefore the top ring otherwise if I went about this game a different way I could end up with an error being caused by the middle ring of a stack being selected. In my mind the game would ask the user for an input to determine which peg was to have its top ring moved, to where, and then follow through with this command.

I am used to matlab and C++ which are big on brackets. Adjusting to Python’s affinity to indents took some getting used to!

I utilized the textbooks I have bought on Python to learn how to manipulate lists, write while statements, and nest if statements. The result of my first draft that successfully ran can be seen below. I have added annotations to the code where needed to explain segment and line functions. These annotations come after the symbol ‘#’. In the program I used the word “tower” instead of “peg” to describe where the rings are placed. From here on out consider tower/peg interchangeable.

# Defining initial conditions
A = [5, 4, 3, 2, 1]
B = []
C = []
DisA = ['BOTTOM',5,4,3,2,1,'TOP']
DisB = ['BOTTOM','EMPTY','TOP']
DisC = ['BOTTOM','EMPTY','TOP']
# Display initial conditions and rules to game.
print("Tower A = ",DisA)
print("Tower B = ",DisB)
print("Tower C = ",DisC)
print("Note: The text 'BOTTOM' and 'TOP' are purely to indicate direction")
print("Lets play the game called The Tower of Hanoi")
print("The goal is to move all the rings from pole A to pole C")
print("You can only move one ring at a time")
print("A ring of larger size/number can never be placed on a ring of smaller size/number")
print("LETS BEGIN!")
while C != [5,4,3,2,1]:  
 #This above while statement says to continue to run as long as C is not equal to the list.   
    T0 = input("Which Tower Are You Removing A Ring From? ") #asking for starting tower
    T1 = input("Which Tower Is This Ring Being Placed On? ") #asking for destination tower
    if T0 == 'A': #If the starting tower prompt yielded the user typing "A"
       if len(A) > 0: #Making sure the tower isnt empty by seeing if its length is more than 0
           RING = A.pop() #Removes the last item in list A and assigns it to variable "RING"
           if T1 == 'A': #If destination tower is A
               A.append(RING) #Add the variable "RING" to the list A so that it is last.
               print("Just picking things up to put them down are we?") #Snark for humor
           elif T1 == 'B': #If destination tower is B
               B.append(RING) #Add the variable "RING" to the list B so that it is last.
           elif T1 == 'C': #If destination tower is C
               C.append(RING) #Add the variable "RING" to the list C so that it is last.
           else: #If there is any user input for destination that doesnt match A, B, or C.
               print("Invalid destination tower.")
       else: #If len(A) was not > 0
           print("Tower A is empty!.....Idiot") #Snark
       
    elif T0 == 'B':
       if len(B) > 0:
           RING = B.pop()
           if T1 == 'A':
               A.append(RING)
           elif T1 == 'B':
               B.append(RING)
               print("Just picking things up to put them down are we?")
           elif T1 == 'C':
               C.append(RING)
           else:
               print("Invalid destination tower. Try again.")
       else:
           print("Tower B is empty!.....Idiot")
    elif T0 == 'C':
       if len(C) > 0:
           RING = C.pop()
           if T1 == 'A':
               A.append(RING)
           elif T1 == 'B':
               B.append(RING)
           elif T1 == 'C':
               C.append(RING)
               print("Just picking things up to put them down are we?")
           else:
               print("Invalid destination tower.")
       else:
           print("Tower C is empty!.....Idiot")
    else: #If the user input for the starting tower was anything but A, B, or C. 
        print("Invalid tower to take a ring from. Try again.") 
#Adding labels at the begining and end of each list for the user to know orientation
    A.insert(0,'BOTTOM')
    A.append('TOP')
    B.insert(0,'BOTTOM')
    B.append('TOP')
    C.insert(0,'BOTTOM')
    C.append('TOP')
#Printing the current lists with labels to the user.
    print("The Tower A = ",A)
    print("The Tower B = ",B)
    print("The Tower C = ",C)
#Removing labels of orientation
    A.pop(0)
    A.pop()
    B.pop(0)
    B.pop()
    C.pop(0)
    C.pop()
print("CONGRATS ON WINNING") #Command to print to screen once while conditions arent met.

The way the above code functions can perhaps be more succinctly explained with a flowchart. The following flowchart is shown in Figure 11.

As far as first iterations go I was satisfied as most of the logic needed for the puzzle was coded into the game. There were two problems though. The first is the game did nothing to prevent a player from cheating and placing a ring of larger size on a smaller ring. Secondly, there was an error that occurred if the player typed a correct input tower but an incorrect output tower. If you follow the logic in Figure 11 you can see that the top ring is removed from the input tower before it’s determined whether the output tower is valid. This could work; however, once an output tower was deemed to be invalid the removed ring has to be placed back on the input tower and in my first iteration the ring is not replaced and is just lost in the ether once the while loop starts again from the top. Both of these problems needed to be patched with my second iteration. The result of improving upon my first iteration is shown below. Both problems have been fixed. The notations have been removed from the following code for sake of decluttering the text. Explanations with images are provided below the code for explanation of the changes.

A = [5, 4, 3, 2, 1]
B = []
C = []
DisA = ['BOTTOM',5,4,3,2,1,'TOP']
DisB = ['BOTTOM','EMPTY','TOP']
DisC = ['BOTTOM','EMPTY','TOP']
print("Tower A = ",DisA)
print("Tower B = ",DisB)
print("Tower C = ",DisC)
print("Note: The text 'BOTTOM' and 'TOP' are purely to indicate direction")
print("Let's play the game called The Tower of Hanoi")
print("The goal is to move all the rings from pole A to pole C")
print("You can only move one ring at a time")
print("A ring of larger size/number can never be placed on a ring of smaller size/number")
print("LET'S BEGIN!")
while C != [5,4,3,2,1]:
    
    T0 = input("Which Tower Are You Removing A Ring From? ")
    T1 = input("Which Tower Is This Ring Being Placed On? ")
    if T0 == 'A':
       if len(A) > 0:
           RING = A.pop()
           if T1 == 'A':
               A.append(RING)
               print("Just picking things up to put them down are we?")
           elif T1 == 'B':
               if len(B)==0:
                   B.append(RING)
               elif B[-1] > RING:
                    B.append(RING)
               else:
                    A.append(RING)
                    print('CHEATER! BE BETTER')
           elif T1 == 'C':
                if len(C)==0:
                   C.append(RING)
                elif C[-1] > RING:
                    C.append(RING)
                else:
                    A.append(RING)
                    print('CHEATER! BE BETTER')
           else:
               A.append(RING) 
               print("Invalid destination tower.")
       else:
           print("Tower A is empty!.....Idiot")
       
    elif T0 == 'B':
       if len(B) > 0:
           RING = B.pop()
           if T1 == 'A':
                if len(A)==0:
                    A.append(RING)
                elif A[-1] > RING:
                    A.append(RING)
                else:
                    B.append(RING)
                    print('CHEATER! BE BETTER')
           elif T1 == 'B':
               B.append(RING)
               print("Just picking things up to put them down are we?")
           elif T1 == 'C':
                if len(C)==0:
                    C.append(RING)
                elif C[-1] > RING:
                    C.append(RING)
                else:
                    B.append(RING)
                    print('CHEATER! BE BETTER')
           else:
               B.append(RING)
               print("Invalid destination tower. Try again.")
       else:
           print("Tower B is empty!.....Idiot")
    elif T0 == 'C':
       if len(C) > 0:
           RING = C.pop()
           if T1 == 'A':
                if len(A)==0:
                    A.append(RING)
                elif A[-1] > RING:
                    A.append(RING)
                else:
                    C.append(RING)
                    print('CHEATER! BE BETTER')
           elif T1 == 'B':
                if len(B)==0:
                    B.append(RING)
                elif B[-1] > RING:
                    B.append(RING)
                else:
                    C.append(RING)
                    print('CHEATER! BE BETTER')
           elif T1 == 'C':
               C.append(RING)
               print("Just picking things up to put them down are we?")
           else:
               C.append(RING)
               print("Invalid destination tower.")
       else:
           print("Tower C is empty!.....Idiot")
    else:
        print("Invalid tower to take a ring from. Try again.")
    A.insert(0,'BOTTOM')
    A.append('TOP')
    B.insert(0,'BOTTOM')
    B.append('TOP')
    C.insert(0,'BOTTOM')
    C.append('TOP')
    print("The Tower A = ",A)
    print("The Tower B = ",B)
    print("The Tower C = ",C)
    A.pop(0)
    A.pop()
    B.pop(0)
    B.pop()
    C.pop(0)
    C.pop()
print("CONGRATS ON WINNING")

An example of the changes found throughout my second iteration can be seen in Figure 12. Notation one (signified with a appropriately notated hexagon) shows the code checking if the destination tower is empty. If it is empty then the removed ring from tower A can be placed on it as there is no other ring size to check. Notation two shows the code checking the list B at the -1 spot which is the end of the list. I could accomplish this by saying B[4] if the B list was 5 items long as python starts counting at 0. However, since I do not know the size of B I can reference the end item in its list by B[-1]. In this case if B[-1] is greater than RING (the ring removed from tower A) the code places RING at the end of list B. Notations three shows the else statement for when B[-1] is less than RING. In these instances the code places the removed ring back on the tower from whence it came and prints words out to the player calling them a cheater and asking them to do better in this game and perhaps any future games they play. Notation four solves the issue when a ring is removed from a valid input tower but has an invalid output tower. This line of code has the removed ring replaces on its original tower and, like in the first iteration, tells the user the destination tower they typed was invalid. It should be noted that the changes seen in Figure 12 are found in other spots within the second iteration’s code and not just the snippet used for Figure 12.

An updated flowchart was created (Fig. 13).

Figure 13. Updated logic flowchart. New steps shown in purple.

The Tower of Hanoi was an interesting problem to tackle from a solution, optimization, and game design angle. I know, or am at least quite confident, my code in my second iteration is bulky and could be condensed into neater functions. I plan on revisiting this problem in the future to do just that once I stop seeing rings everywhere in my mind. Creating a program that can solve an N-ring Tower of Hanoi problem of any size and show all of its moves is also on my wish list of projects I intend to attempt as I gain proficiency in Python and examine the solution set patterns.

Please feel free to download my game and try your hand at solving this logic puzzle for yourself and see if you can complete it in the optimal number of moves. Or go watch a scary movie by yourself and find your own rabbit hole to dive into for distraction.