Tower of Hanoi
Algorithm · Core
Step through it: Divide & Conquer pattern
Step 1 of 6
Goal: sort [6, 3, 8, 2]. Big problems are hard and tiny ones are easy. Split in half until every piece is a single number (already sorted), then join the pieces back together in order.
Step 2 of 6
Split into [6, 3] and [8, 2].
Step 3 of 6
Split again until each piece is one number. One number is always sorted.
Step 4 of 6
Join neighbours in order: [6, 3] becomes [3, 6] and [8, 2] becomes [2, 8].
Step 5 of 6
Join the two sorted halves by repeatedly taking the smaller front number: 2, 3, 6, 8. There are about log n levels of splitting and each level handles every number once, so n log n. Solving halves and combining the answers is divide and conquer.
Step 6 of 6
Your turn.
The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No disk may be placed on top of a smaller disk.
Animation of an iterative algorithm solving 6-disk problem
With 3 disks, the puzzle can be solved in 7 moves. The minimal
number of moves required to solve a Tower of Hanoi puzzle
is 2^n − 1, where n is the number of disks.
Code
import Stack from '../../../data-structures/stack/Stack';
/**
* @param {number} numberOfDiscs
* @param {Stack} fromPole
* @param {Stack} withPole
* @param {Stack} toPole
* @param {function(disc: number, fromPole: number[], toPole: number[])} moveCallback
*/
function hanoiTowerRecursive({
numberOfDiscs,
fromPole,
withPole,
toPole,
moveCallback,
}) {
if (numberOfDiscs === 1) {
// Base case with just one disc.
moveCallback(fromPole.peek(), fromPole.toArray(), toPole.toArray());
const disc = fromPole.pop();
toPole.push(disc);
} else {
// In case if there are more discs then move them recursively.
// Expose the bottom disc on fromPole stack.
hanoiTowerRecursive({
numberOfDiscs: numberOfDiscs - 1,
fromPole,
withPole: toPole,
toPole: withPole,
moveCallback,
});
// Move the disc that was exposed to its final destination.
hanoiTowerRecursive({
numberOfDiscs: 1,
fromPole,
withPole,
toPole,
moveCallback,
});
// Move temporary tower from auxiliary pole to its final destination.
hanoiTowerRecursive({
numberOfDiscs: numberOfDiscs - 1,
fromPole: withPole,
withPole: fromPole,
toPole,
moveCallback,
});
}
}
/**
* @param {number} numberOfDiscs
* @param {function(disc: number, fromPole: number[], toPole: number[])} moveCallback
* @param {Stack} [fromPole]
* @param {Stack} [withPole]
* @param {Stack} [toPole]
*/
export default function hanoiTower({
numberOfDiscs,
moveCallback,
fromPole = new Stack(),
withPole = new Stack(),
toPole = new Stack(),
}) {
// Each of three poles of Tower of Hanoi puzzle is represented as a stack
// that might contain elements (discs). Each disc is represented as a number.
// Larger discs have bigger number equivalent.
// Let's create the discs and put them to the fromPole.
for (let discSize = numberOfDiscs; discSize > 0; discSize -= 1) {
fromPole.push(discSize);
}
hanoiTowerRecursive({
numberOfDiscs,
fromPole,
withPole,
toPole,
moveCallback,
});
}References
Practice
Divide & Conquer
- Majority ElementEasy
- Convert Sorted Array to Binary Search TreeEasy
- Pow(x, n)Medium
- Sort ListMedium
- Maximum SubarrayMedium
- Different Ways to Add ParenthesesMedium
- Construct Quad TreeMedium
- Kth Largest Element in an ArrayMedium
- Merge k Sorted ListsHard
- Reverse PairsHard
- The Skyline ProblemHard
- Median of Two Sorted ArraysHard
Spotted a mistake or something unclear? Report it on GitHub.