N-Queens
Places N queens on an N×N chessboard so no two queens threaten each other.
Moves a tower of disks from one peg to another using recursive strategy.
The Towers of Hanoi is a classic mathematical puzzle invented by French mathematician Edouard Lucas in 1883. The goal is to move a stack of disks of decreasing size from one peg to another, following strict rules about disk placement. Lucas marketed the puzzle under the pseudonym "Professor N. Claus (of Siam)" -- an anagram of "Lucas d'Amiens" -- accompanied by a legend about monks in a temple moving 64 golden disks, with the world ending upon completion. While the legend was a marketing invention, the mathematical beauty of the puzzle is genuine and profound.
Lucas was inspired by both recreational mathematics and number theory when he created the puzzle. The structure of the Towers of Hanoi mirrors properties of binary numbers, Gray codes, and Sierpinski's triangle -- connections that were discovered decades after the puzzle's invention. In computer science, it became the canonical example of recursion after appearing in early programming textbooks in the 1960s. The puzzle also has connections to the analysis of algorithms: determining the minimum number of moves is a classic application of recurrence relations.
Rules:
Recursive solution:
This elegant three-step recursion solves the puzzle optimally. The base case is trivial: moving a single disk requires one move directly from source to target. Each level of recursion reduces the problem size by one, building a solution from the bottom up.
| Metric | Value |
|---|---|
| Minimum moves | 2^n - 1 |
| Time | O(2^n) |
| Space | O(n) recursion depth |
For 4 disks, the minimum is 15 moves. For 10 disks, it is 1,023 moves. For the legendary 64 disks, it would take 18,446,744,073,709,551,615 moves -- at one move per second, roughly 585 billion years, far exceeding the age of the universe. The proof that 2^n - 1 is both necessary and sufficient follows from the recurrence T(n) = 2*T(n-1) + 1, with T(1) = 1.
The Towers of Hanoi has a remarkable connection to binary counting. Number the disks 0 through n-1 from smallest to largest. In the optimal solution, disk k moves on every 2^k-th step. The sequence of which disk moves at each step corresponds to the position of the least significant set bit in the step number's binary representation. For example, step 1 (binary 001) moves disk 0, step 2 (binary 010) moves disk 1, step 3 (binary 011) moves disk 0, and step 4 (binary 100) moves disk 2.
The puzzle also maps directly to a Sierpinski triangle when the state space is visualized as a graph. Each node represents a configuration of disks on pegs, and edges represent legal moves. For three pegs, this state graph is exactly the Sierpinski triangle -- a fractal with self-similar structure that mirrors the recursive nature of the solution. The puzzle's connection to Gray codes (binary sequences where consecutive values differ by exactly one bit) further enriches its mathematical significance.
The Frame-Stewart conjecture (1941) addresses the Towers of Hanoi with four or more pegs. With four pegs, the puzzle can be solved in significantly fewer moves, but proving the optimal number of moves remained an open problem for decades. The Reve's puzzle (four-peg variant) and extensions to arbitrary numbers of pegs continue to be active areas of mathematical research.
The Towers of Hanoi is the canonical example of recursion in computer science education. It demonstrates how a problem that seems complex can be broken down into smaller, self-similar subproblems. The same recursive decomposition pattern appears in divide-and-conquer algorithms, fractal generation, tree traversals, and recursive data structure operations. Understanding this puzzle provides a foundation for reasoning about exponential growth, recurrence relations, and the power of recursive thinking.