Classic logic puzzles are small versions of real algorithm patterns: river crossing is breadth-first search over states, Tower of Hanoi is recursion, N-Queens is backtracking, Monty Hall is probability you can check by simulation, and the Josephus problem is a recurrence with modular arithmetic. Below, each puzzle comes with the idea that solves it and Python code that has been run, followed by a general method for attacking a puzzle you have not seen.
Are puzzles still asked in interviews?
Pure brainteasers (“how many golf balls fit in a bus?”) have mostly gone out of fashion in software interviews, and several large companies have said publicly that they stopped using them. What remains common are problems that look like puzzles but are algorithm questions in disguise: state search, recursion, backtracking, counting. Learning the puzzles below is useful mainly because they teach those patterns in a form you can reason about on paper.
1. River crossing: search over states
The puzzle. A farmer must carry a fox, a chicken and a sack of grain across a river. The boat holds the farmer and one item. Left alone, the fox eats the chicken and the chicken eats the grain.
The idea. Describe the world as a state: which bank each of the farmer, fox, chicken and grain is on. A move flips the farmer and optionally one item that is on the same bank. Some states are illegal (fox and chicken alone together). Breadth-first search from the start state finds the shortest sequence of moves, and keeping a “previous state” map lets you read the answer back.
from collections import deque
# state = (farmer, fox, chicken, grain); 0 = start bank, 1 = far bank
def safe(s):
f, fox, ch, gr = s
if fox == ch != f: return False # fox alone with chicken
if ch == gr != f: return False # chicken alone with grain
return True
def river():
names = ["fox", "chicken", "grain"]
start, goal = (0, 0, 0, 0), (1, 1, 1, 1)
prev, q = {start: None}, deque([start])
while q:
s = q.popleft()
if s == goal:
break
for i in [None, 1, 2, 3]: # carry nothing, or one item
if i is not None and s[i] != s[0]:
continue # item is on the other bank
n = list(s)
n[0] ^= 1
if i is not None:
n[i] ^= 1
n = tuple(n)
if n not in prev and safe(n):
prev[n] = (s, i)
q.append(n)
steps, s = [], goal
while prev[s]:
p, i = prev[s]
steps.append(("take " + names[i - 1]) if i else "go alone")
s = p
return steps[::-1]
print(river())
# ['take chicken', 'go alone', 'take fox', 'take chicken', 'take grain', 'go alone', 'take chicken']That is seven crossings, and BFS guarantees none is shorter. (Swapping “take fox” and “take grain” gives a second valid answer; BFS returns one of them.) The same pattern solves sliding-tile puzzles, word ladders and “minimum moves” problems: define the state, generate legal neighbors, avoid revisiting states. Try it in our BFS min-distance lesson.
2. Tower of Hanoi: recursion
The puzzle. Move a stack of n disks from one rod to another, one disk at a time, never placing a larger disk on a smaller one, using a third rod as a helper.
The idea. To move n disks, move the top n-1 disks out of the way onto the helper rod, move the largest disk, then move the n-1 disks on top of it. The base case is zero disks: do nothing. The number of moves is 2n – 1, so the running time is exponential and unavoidable; no algorithm can do fewer moves.
def hanoi(n, source, target, helper, moves):
if n == 0:
return
hanoi(n - 1, source, helper, target, moves)
moves.append((source, target))
hanoi(n - 1, helper, target, source, moves)
moves = []
hanoi(3, "A", "C", "B", moves)
print(len(moves), moves)
# 7 [('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]The lesson is how to trust recursion: assume the function already works for n-1, and only describe how n relies on it. Practice that skill with the recursion lesson.
3. N-Queens: backtracking
The puzzle. Place n queens on an n-by-n board so that none attack another. The eight-queens case has 92 solutions.
The idea. Place one queen per row. For each row, try each column that is not attacked, recurse to the next row, and undo the placement if it leads nowhere. Attacks are cheap to check with three sets: used columns, used “\” diagonals (row – col is constant) and used “/” diagonals (row + col is constant).
def queens(n):
cols, d1, d2 = set(), set(), set()
def place(row):
if row == n:
return 1
total = 0
for c in range(n):
if c in cols or row - c in d1 or row + c in d2:
continue
cols.add(c); d1.add(row - c); d2.add(row + c)
total += place(row + 1)
cols.remove(c); d1.remove(row - c); d2.remove(row + c)
return total
return place(0)
print([queens(n) for n in range(1, 9)])
# [1, 0, 0, 2, 10, 4, 40, 92]The counts for n = 1 to 8 match the known values (1, 0, 0, 2, 10, 4, 40, 92). Backtracking is the same skeleton for Sudoku, generating permutations and subsets, and parentheses generation. The skeleton is: choose, explore, un-choose. See the N Queens lesson.
4. Monty Hall: check your intuition with a simulation
The puzzle. Behind one of three doors is a car, behind the others goats. You pick a door. The host, who knows where the car is, opens a different door showing a goat and offers you a switch. Should you switch?
The answer. Yes. Your first pick is right with probability 1/3. If it was wrong (probability 2/3), the host’s forced choice leaves the car behind the only other closed door, so switching wins 2/3 of the time. When intuition and math disagree, simulate:
import random
def monty(switch, trials=100000, seed=1):
rnd = random.Random(seed)
wins = 0
for _ in range(trials):
car, pick = rnd.randrange(3), rnd.randrange(3)
opened = next(d for d in range(3) if d != pick and d != car)
if switch:
pick = next(d for d in range(3) if d != pick and d != opened)
wins += pick == car
return wins / trials
print(monty(False), monty(True))
# 0.3328 0.6672The simulation prints about 1/3 for staying and 2/3 for switching (the exact numbers depend on the random seed). The important assumption is that the host always opens a goat door on purpose. If he opened a random door and happened to show a goat, switching would give no advantage, which is a good follow-up to mention.
5. The Josephus problem: find the recurrence
The puzzle. n people stand in a circle. Starting at person 1, count k people and eliminate the k-th, then continue counting from the next person. Who is the last survivor?
The idea. Simulating with a list works and costs O(n*k) or O(n^2) depending on the removal method. A better view: let J(i) be the survivor’s 0-based position in a circle of size i. After the first elimination there are i-1 people, and positions shift by k, so J(i) = (J(i-1) + k) mod i, with J(1) = 0. That gives an O(n) loop with O(1) space.
def josephus(n, k):
pos = 0 # survivor index for a circle of 1
for size in range(2, n + 1):
pos = (pos + k) % size
return pos + 1 # convert to 1-based
def brute(n, k): # simulation, to cross-check
people, i = list(range(1, n + 1)), 0
while len(people) > 1:
i = (i + k - 1) % len(people)
people.pop(i)
return people[0]
print(josephus(7, 3), josephus(41, 3))
# 4 31
print(all(brute(n, k) == josephus(n, k) for n in range(1, 40) for k in range(1, 8)))
# TrueThe brute-force version is worth keeping as a test oracle: compare the clever solution against the simple one on small inputs. That habit catches off-by-one errors in interviews and in real code.
A method for any puzzle
- Restate the rules and check them against a tiny example.
- Write down the state. What is the smallest set of facts that fully describes the situation (bank positions, rods, columns used)?
- Solve small cases by hand (n = 1, 2, 3) and look for a pattern or a recursion.
- Pick the pattern: shortest sequence of moves means BFS; “all valid arrangements” means backtracking; “solve the same problem on a smaller input” means recursion or dynamic programming; “which is more likely” means simulate, then prove.
- Write a slow, obviously correct version first, then optimize and compare the two.
- State the complexity and the edge cases (n = 0, k = 1, impossible instances).
Where to go next
If puzzles are your route into interview preparation, move on quickly to the problem types they feed: BFS and DFS on graphs, recursion, backtracking, and dynamic programming. Our post on recursion exercises is a good next step, and AlgoCademy has guided lessons on each of these topics.
