Algorithmic Puzzles

Named puzzles and recreational problems, grouped by the technique that solves them. Each linked page has the full treatment; this is the index and the “what technique does this need” map.

Problems, not algorithms

These are questions whose answers happen to be famous — distinct from the named algorithms, which are methods. The full set lives in Classical Problems.

Recreational classics

Puzzle	Technique
Tower of Hanoi	recursion; $2^n-1$ moves; the $i$-th move is disk $\mathrm{ctz}(i)$
Josephus problem	recurrence, or bit rotation for $k=2$
N-Queens	backtracking with bitmasks
Knight’s tour	backtracking + Warnsdorff’s rule
8- / 15-puzzle	A*, bidirectional BFS; a parity invariant decides solvability
Water jug	BFS on states; solvable iff $\gcd \mid$ target
Wolf, goat and cabbage	BFS on a small state space
Bridge and torch	greedy / small DP
Lights Out	${\mathbb{F}}_2$ Gaussian elimination
Sudoku	Dancing Links / exact cover
Magic square, Latin square	direct construction; see Classic Constructions
Pancake sorting	greedy; $\le \frac{18}{11}n$ flips
Peg solitaire	an invariant (a colouring argument)
Königsberg bridges	Eulerian path conditions

Probability puzzles

Puzzle	Answer
Monty Hall	switching wins with probability $2/3$
Birthday paradox	23 people for 50%
Coupon collector	$n{H}_n\approx n\ln n$
100 prisoners and the boxes	cycle-following gives $\approx 31\%$
Secretary problem	reject the first $n/e$, then take the best so far
Poisoned wine	binary encoding: $\lceil {\log }_{2}n\rceil$ testers

The 100 prisoners result is the most surprising: a strategy raising the success probability from $2^{-100}$ to $31\%$, using nothing but the cycle structure of a random permutation.

Number puzzles

Puzzle	Technique
Trailing zeroes of $n!$	Legendre: $\sum \lfloor n/5^i\rfloor$
Derangements	$D_n=n!\sum (-1{)}^k/k!$
The Catalan family	brackets, triangulations, BSTs — all $C_n$
Chicken McNugget / Frobenius	$ab-a-b$ for coprime $a,b$
Staircase counting	Fibonacci
Digit sums, repunits, palindromic numbers	digit DP

Trailing zeroes — the derivation

$10=2\times 5$, and $n!$ always has more factors of 2 than of 5, so the count is $v_5(n!)$:

$\lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{25}\rfloor +\lfloor \frac{n}{125}\rfloor +\dots$

long long trailingZeroes(long long n) {
    long long c = 0;
    for (long long p = 5; p <= n; p *= 5) c += n / p;
    return c;
}

$O({\log }_{5}n)$. In base $b$, factor $b=\prod q_i^{a_i}$ and take ${\min }_i\lfloor v_{q_i}(n!)/a_i\rfloor$.

Array and sequence classics

Puzzle	Technique
Maximum subarray	Kadane
Trapping rain water	two pointers, or monotonic stack
Largest rectangle in a histogram	monotonic stack
Majority element	Boyer-Moore voting
Dutch national flag	three-way partition
Celebrity problem	$O(n)$ elimination
Gas station / circular tour	greedy with a running deficit
Stock buy and sell	greedy or DP by transaction count
Next greater element	monotonic stack

Optimisation classics

Problem	Status
Egg dropping	DP; a binomial closed form exists
Knapsack	DP; NP-hard
Coin change	DP; greedy fails in general
Rod cutting	unbounded knapsack
Assignment	Hungarian, $O(n^3)$
Stable marriage	Gale-Shapley, $O(n^2)$
TSP	NP-hard; Held-Karp for $n\le 20$
Subset sum / partition	NP-hard; pseudo-polynomial DP

See also: Classical Problems · Problem Pattern Recognition · Named Algorithms