Print every move that solves the Tower of Hanoi for n disks, moving them from peg A to peg C with B as the spare. Use the recursive plan from the lesson.
What to build
The list of moves that solves the puzzle.
Requirements
- Read
n. - Print each move, using the recursive plan from the lesson.
Input
One whole number n from 1 to 10.
Output
One line per move: Move disk K from X to Y.
Constraints
n is from 1 to 10.
Example
Input:
1
Output:
Move disk 1 from A to C
Why it works
To move the largest disk, all the others must be out of the way, which gives two smaller versions of the same problem around one move.
Examples
Example 1 · Input
1
Expected output
Move disk 1 from A to C
Example 2 · Input
2
Expected output
Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Move n - 1 disks to the spare peg, move disk n, then move the n - 1 disks on top of it.
Hint 2
The base case is n == 0: nothing to move.
Solution
Show one correct solution (try it yourself first)
def hanoi(n, start, end, spare):
if n == 0:
return
hanoi(n - 1, start, spare, end)
print("Move disk", n, "from", start, "to", end)
hanoi(n - 1, spare, end, start)
hanoi(int(input()), "A", "C", "B")