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.<\/p>\n
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.<\/p>\n
The puzzle.<\/strong> 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.<\/p>\n The idea.<\/strong> 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.<\/p>\n 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<\/a>.<\/p>\n The puzzle.<\/strong> 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.<\/p>\n The idea.<\/strong> 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<\/sup> – 1, so the running time is exponential and unavoidable; no algorithm can do fewer moves.<\/p>\n 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<\/a>.<\/p>\n The puzzle.<\/strong> Place n queens on an n-by-n board so that none attack another. The eight-queens case has 92 solutions.<\/p>\n The idea.<\/strong> 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).<\/p>\n 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<\/a>.<\/p>\n The puzzle.<\/strong> 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?<\/p>\n The answer.<\/strong> 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:<\/p>\n The 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.<\/p>\n The puzzle.<\/strong> 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?<\/p>\n The idea.<\/strong> 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.<\/p>\n The 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.<\/p>\n 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<\/a> is a good next step, and AlgoCademy<\/a> has guided lessons on each of these topics.<\/p>\n","protected":false},"excerpt":{"rendered":" Five classic logic puzzles (river crossing, Tower of Hanoi, N-Queens, Monty Hall, Josephus) with the algorithm behind each and tested Python solutions.<\/p>\n","protected":false},"author":1,"featured_media":4496,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4497","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4497"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4497"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4497\/revisions"}],"predecessor-version":[{"id":8723,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4497\/revisions\/8723"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4496"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4497"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4497"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4497"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}from collections import deque\n\n# state = (farmer, fox, chicken, grain); 0 = start bank, 1 = far bank\ndef safe(s):\n f, fox, ch, gr = s\n if fox == ch != f: return False # fox alone with chicken\n if ch == gr != f: return False # chicken alone with grain\n return True\n\ndef river():\n names = [\"fox\", \"chicken\", \"grain\"]\n start, goal = (0, 0, 0, 0), (1, 1, 1, 1)\n prev, q = {start: None}, deque([start])\n while q:\n s = q.popleft()\n if s == goal:\n break\n for i in [None, 1, 2, 3]: # carry nothing, or one item\n if i is not None and s[i] != s[0]:\n continue # item is on the other bank\n n = list(s)\n n[0] ^= 1\n if i is not None:\n n[i] ^= 1\n n = tuple(n)\n if n not in prev and safe(n):\n prev[n] = (s, i)\n q.append(n)\n steps, s = [], goal\n while prev[s]:\n p, i = prev[s]\n steps.append((\"take \" + names[i - 1]) if i else \"go alone\")\n s = p\n return steps[::-1]\n\nprint(river())\n# ['take chicken', 'go alone', 'take fox', 'take chicken', 'take grain', 'go alone', 'take chicken']<\/code><\/pre>\n2. Tower of Hanoi: recursion<\/h2>\n
def hanoi(n, source, target, helper, moves):\n if n == 0:\n return\n hanoi(n - 1, source, helper, target, moves)\n moves.append((source, target))\n hanoi(n - 1, helper, target, source, moves)\n\nmoves = []\nhanoi(3, \"A\", \"C\", \"B\", moves)\nprint(len(moves), moves)\n# 7 [('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]<\/code><\/pre>\n3. N-Queens: backtracking<\/h2>\n
def queens(n):\n cols, d1, d2 = set(), set(), set()\n\n def place(row):\n if row == n:\n return 1\n total = 0\n for c in range(n):\n if c in cols or row - c in d1 or row + c in d2:\n continue\n cols.add(c); d1.add(row - c); d2.add(row + c)\n total += place(row + 1)\n cols.remove(c); d1.remove(row - c); d2.remove(row + c)\n return total\n\n return place(0)\n\nprint([queens(n) for n in range(1, 9)])\n# [1, 0, 0, 2, 10, 4, 40, 92]<\/code><\/pre>\n4. Monty Hall: check your intuition with a simulation<\/h2>\n
import random\n\ndef monty(switch, trials=100000, seed=1):\n rnd = random.Random(seed)\n wins = 0\n for _ in range(trials):\n car, pick = rnd.randrange(3), rnd.randrange(3)\n opened = next(d for d in range(3) if d != pick and d != car)\n if switch:\n pick = next(d for d in range(3) if d != pick and d != opened)\n wins += pick == car\n return wins \/ trials\n\nprint(monty(False), monty(True))\n# 0.3328 0.6672<\/code><\/pre>\n5. The Josephus problem: find the recurrence<\/h2>\n
def josephus(n, k):\n pos = 0 # survivor index for a circle of 1\n for size in range(2, n + 1):\n pos = (pos + k) % size\n return pos + 1 # convert to 1-based\n\ndef brute(n, k): # simulation, to cross-check\n people, i = list(range(1, n + 1)), 0\n while len(people) > 1:\n i = (i + k - 1) % len(people)\n people.pop(i)\n return people[0]\n\nprint(josephus(7, 3), josephus(41, 3))\n# 4 31\nprint(all(brute(n, k) == josephus(n, k) for n in range(1, 40) for k in range(1, 8)))\n# True<\/code><\/pre>\nA method for any puzzle<\/h2>\n
\n
Where to go next<\/h2>\n