A classic puzzle is called the Tower of Hanoi. To solve the puzzle, you must move all of the rings from the peg on the left to the peg on the right. Sound easy? The trick is that all of the pieces are different sizes, and you aren’t allowed to put a larger piece on top of a smaller piece. Just like with the Traveling Salesman Problem that you were introduced to in this unit, the Tower of Hanoi is the kind of problem that a computer is good at solving. An algorithm really helps! But the Tower of Hanoi is still fun to work out on your own.

For this lab, you will use a virtual Tower of Hanoi to solve the puzzle.

Step 1
Solve the puzzle at least three times. Start with only three discs. You must also solve the 4-disc puzzle, and then challenge yourself with any number of discs greater than 4. (Change the number of discs by clicking the arrows in the top left corner of the game.)

Screenshot each of your solutions, showing the completed puzzle and the number of moves it took you to reach that point. It is okay if your number of moves are above the minimum number of moves listed.

Step 2
After you have solved the Tower of Hanoi at least three times, write an algorithm with clear, numbered steps that would guide another player through the steps of solving the puzzle.

Here is a clue to get you started: The first step should be: move the smallest ring to the middle peg.

Step 3
After you write the algorithm, write a few sentences reflecting on your experience: What was tricky about writing the algorithm? Did you find that having a written algorithm made it easier to solve the puzzle? Why or why not?

Step 4
Do some online research and discover another famous algorithm or coding puzzle to share. Write a brief summary of the puzzle, as well as what you find interesting about it. Include the link to the source where you found the puzzle.

Submit your screenshots, algorithm, reflections, and research as one document.