Tower of Hanoi
Move three disks from peg A to peg C using peg B, moving one disk at a time and never placing a larger disk on a smaller one.
Course progress
Problem 32 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
disks = 3; source = A; spare = B; destination = C
Expected output
Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C
What is happening?
Move the top two disks aside, move disk 3 to C, then move the two smaller disks onto it. The recursive process takes seven legal moves.
Solution strategy
Build the right mental model
Move n−1 disks to the spare peg, move the largest disk to the destination, then move the n−1 disks onto it.
Core concepts
recursion · divide and conquer
Complexity
Time O(2ⁿ), call-stack space O(n).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for tower-of-hanoi
using System;
class Program
{
static void MoveDisks(int count, char source, char spare, char destination)
{
if (count == 0) return;
MoveDisks(count - 1, source, destination, spare);
Console.WriteLine("Move disk " + count + " from " + source + " to " + destination);
MoveDisks(count - 1, spare, source, destination);
}
static void Main()
{
MoveDisks(3, 'A', 'B', 'C');
}
}Knowledge check
Questions students often ask
What is the main idea behind tower of hanoi?
Move n−1 disks to the spare peg, move the largest disk to the destination, then move the n−1 disks onto it.
What is the time and space complexity of this solution?
Time O(2ⁿ), call-stack space O(n).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.