Towers of Hanoi - Part 1
The Towers of Hanoi is a classic puzzle with 3 pegs and multiple disks of different sizes. The goal of the puzzle is to move all the disks from the first peg to the the third peg according to the following rules:
- Only one disk can be moved at a time.
- You can only move the top disc in a stack.
- No disk may be placed on top of a smaller disk.
Try out the game below with 3 disks:
Finding an Algorithm
Once you've solved the puzzle with 3 disks, try again with 4 disks or 5 disks. Can you figure out a general strategy, or algorithm, for solving this puzzle with any number of disks?
To reach a general solution, first break down the problem into its simplest form. We'll start with only one disk and work our way up.
Case 1: What do you do when there's just one disk on a starting peg and you need to get it to the goal peg?
Answer: Move the disk to the goal peg.
That wasn't very difficult, but it's the fundamental step. Now for Case 2.
Now that you have the Algorithm for 2 disks, write a program to solve moving 2 disks from one peg to another.
Above, you moved disks from Peg 1 to Peg 3, but in this challenge, you need to move 2 disks from any starting peg to any goal peg.
You will be given two numbers (from 1 to 3) as input - the starting peg, and the goal peg. Write a function that calculates how to move 2 disks from the starting peg to the goal peg. Print out the steps.
Print the peg to move from, an arrow "->", and the peg to move to. For example, to move from peg 1 to peg 3, print "1->3".
Print all the steps for a given case on its own line. Print a newline after each case.
Alternatively, you can try out Learneroo before signing up.