Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
This is Towers of Hanoi with FOUR pegs, asking for the minimum number of legal moves to gather all disks onto the first peg from an arbitrary start. Because there's no neat closed form for 4 pegs, model each configuration as a node: encode the whole tower as a base-4 number (2 bits per disk = which of the 4 pegs it sits on). Run BFS from the start state to the all-on-peg-1 goal — BFS over an unweighted state graph gives the minimum move count directly. With n ≤ 10 disks there are at most 4¹⁰ ≈ 1.05M states, each with ≤ 12 candidate moves, so plain BFS is fast. O(4ⁿ · pegs²) time and O(4ⁿ) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that 4-peg Hanoi has no clean formula and reframe 'minimum moves' as BFS shortest path over an encoded state space, with a correct legal-move generator and a visited set.
Where candidates slip
Reaching for a closed-form Frame–Stewart-style formula (it doesn't apply to an arbitrary start), using DFS (won't give the minimum), or omitting the visited set so the search cycles.
How to stand out
Derive the 2-bits-per-disk encoding, explain why the top disk is the smallest, generate moves correctly, and mention bidirectional BFS or A* with an admissible heuristic to shrink the explored frontier.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each node is an encoded tower state; edges are legal single-disk moves of cost 1.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Unbounded DFS Over Move Sequences
1Hint 1Explore hintHide hint
From a configuration, enumerate every legal move and recurse on the resulting configuration, tracking the move count.
2Hint 2Explore hintHide hint
Without remembering visited configurations you can move a disk back and forth forever — the search may never terminate.
3Hint 3Explore hintHide hint
Even bounding the depth (iterative deepening) explores an exponential tree because the same configuration is reached along many paths.
A · Core idea
The literal interpretation: try moves recursively and keep the best total found.
Why it's broken as written. Moves are reversible — you can shift a disk to another peg and immediately shift it back — so a depth-first walk can loop indefinitely. Even if you cap the depth (iterative deepening DFS), the configuration graph has many paths into the same node, so you re-explore states exponentially.
Why DFS can't give the minimum cheaply. DFS dives down one branch fully before trying others, so the first time it reaches the goal need not be via the fewest moves. You'd have to explore all paths up to the optimal depth and take the minimum — exactly the exponential blow-up.
What the failure teaches. Two fixes are needed: (1) never re-expand a configuration (a visited set), and (2) explore in order of increasing move count so the first time you touch the goal is optimal. Doing both is breadth-first search — the next approach.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 1, posts = [2]Interactive diagram
Cycles without a visited set
state {1:peg2}A disk can bounce between pegs, so DFS loops forever.
1 (only found reliably once visited tracking + BFS ordering are added)C · Code with teaching comments
Reference implementation preview// Illustrative only — needs a visited set and BFS ordering to be correct/terminating. int best = Integer.MAX_VALUE; void dfs(int[] pos, int moves) { if (isGoal(pos)) { best = Math.min(best, moves); return; }Explore the full codeHide the full code
D · Why it works and complexityexponential / non-terminating without bounds timeO(depth) spaceOpen the invariant and proofExplore the proofHide the proof
Reversible moves turn naive DFS into an infinite walk, and DFS's depth-first order breaks the 'first hit is optimal' property. Recognising both flaws points straight at BFS with a visited set as the right tool.
Complexityexponential / non-terminating without bounds time, O(depth) space — Each state has up to 12 move candidates; a depth-d DFS explores up to 12^d sequences, and without a visited set it revisits configurations endlessly, so it neither terminates reliably nor guarantees the minimum.
E · Edge cases and pitfalls3No visited set → infinite cycling on reversible moves.Explore edge casesHide edge cases
Pitfalls
- No visited set → infinite cycling on reversible moves.
- Assuming the first goal hit by DFS is optimal — it isn't.
- Hoping a closed-form formula exists for 4 pegs from an arbitrary start — it doesn't.
Approach 2 of 3 · Optimal
BFS Over Base-4 Encoded States (Optimal)
1Hint 1Explore hintHide hint
Encode the configuration: 2 bits per disk hold its peg (0–3). The whole state is one integer in [0, 4ⁿ).
2Hint 2Explore hintHide hint
To generate moves, find each peg's top disk (its smallest disk), then try dropping it on any peg that's empty or has a larger top.
3Hint 3Explore hintHide hint
BFS from the start integer; the first time you dequeue the goal (all disks on peg 1, encoded 0) its distance is the minimum move count.
A · Core idea
Model configurations as graph nodes and run breadth-first search.
Encoding. Disk i's peg is stored in bits 2i..2i+1 of an integer state. With n ≤ 10, state fits in 20 bits; the full state space is [0, 4ⁿ). The goal — every disk on peg 1 — encodes as 0 (peg index 0).
Finding tops. The movable disk on a peg is its smallest disk. Scan disks from largest to smallest, recording each disk's peg; the last write per peg leaves the smallest disk index, i.e. that peg's top. A peg with no disk has no top.
Generating moves. For each peg from with top disk d, and each other peg to: the move is legal if to is empty or its top disk is larger than d (a larger disk index). Apply it by rewriting d's two bits to to, producing the neighbour state.
Why BFS is exactly right. Every move costs 1, so the graph is unweighted; BFS visits states in non-decreasing distance order, guaranteeing the first time the goal is reached uses the fewest moves. A dist array doubles as the visited set: only relax a neighbour whose distance is still unset.
Cost. Each of the ≤ 4ⁿ states is expanded once with O(n) work to find tops and ≤ 12 neighbours, so the search is linear in the state-space size — about 12 million elementary steps at n = 10, which is fast.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 2, posts = [2, 3]Array state
dist 0
start state 9
2C · Code with teaching comments
D · Why it works and complexityO(4ⁿ · pegs²) timeO(4ⁿ) spaceOpen the invariant and proofExplore the proofHide the proof
The entire problem reduces to two design choices: a compact, collision-free state encoding (2 bits per disk) and a correct legal-move generator (top = smallest, destination must be larger or empty). Once those are right, BFS is boilerplate and the minimum is whatever distance the goal gets.
ComplexityO(4ⁿ · pegs²) time, O(4ⁿ) space — At most 4ⁿ states; each is expanded once and generates ≤ 4·3 = 12 moves, each found in O(n) (scanning disks for tops). So time is O(4ⁿ · n) (≈ O(4ⁿ · pegs²) treating peg work as constant), and the distance array is O(4ⁿ) space.
E · Edge cases and pitfalls8n = 2, posts = [1, 1] — Start already equals the goal (state 0) → dequeued first, returns 0.Explore edge casesHide edge cases
Edge cases handled
n = 2, posts = [1, 1]Start already equals the goal (state 0) → dequeued first, returns 0.n = 1, posts = [4]One disk on peg 4; a single move reaches peg 1 → 1.all disks on peg 2Must relocate the whole stack to peg 1 using the spare pegs; BFS finds the optimal 4-peg sequence.n = 10≈1.05M states; flat int dist array (~4 MB) and BFS finish quickly.
Pitfalls
- Treating the top as the largest disk — it's the smallest.
- Allowing a move onto a smaller disk — must be empty or larger.
- Using DFS or forgetting the dist/visited guard — wrong answer or non-termination.
- Off-by-one on peg labels — input pegs are 1–4, internal encoding uses 0–3.
Approach 3 of 3
Bidirectional BFS
1Hint 1Explore hintHide hint
Run two BFS frontiers simultaneously — one from the start, one from the goal — and stop when they touch.
2Hint 2Explore hintHide hint
Moves are reversible, so the goal-side search uses the same move generator; the meeting distance is the sum of the two depths.
3Hint 3Explore hintHide hint
Always expand the smaller frontier next to keep both shallow; the explored region is roughly two radius-(d/2) balls instead of one radius-d ball.
A · Core idea
Plain BFS already fits in memory for n ≤ 10, but bidirectional BFS dramatically shrinks the explored frontier when the optimal depth is large.
Idea. Because every move is reversible, a path from start to goal is also a path from goal to start. So grow two BFS frontiers — distF from the start and distB from the goal — alternating, always expanding whichever frontier currently has fewer nodes. The moment a state has been reached from both sides, the answer is distF[state] + distB[state]; take the minimum over all such meeting states discovered at the touching layer.
Why it's faster. A single BFS to depth d touches on the order of b^d states. Two searches to depth d/2 each touch b^(d/2), and 2·b^(d/2) ≪ b^d. For deep optimal solutions this is the difference between exploring most of the million states and exploring a small fraction.
Caveats. It's more code (two visited maps, careful meeting check) and the same worst-case memory. Reach for it only when the unidirectional frontier is genuinely large; for small n the plain BFS is cleaner and plenty fast.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 2, posts = [2, 3] (optimal distance 2)Interactive diagram
Two frontiers meeting
fwd layer 1Forward and backward searches each go ~half the depth and meet in the middle.
2C · Code with teaching comments
Reference implementation previewpublic int genaBidirectional(int n, int[] posts) { int start = 0; for (int i = 0; i < n; i++) start |= (posts[i] - 1) << (2 * i); final int GOAL = 0; if (start == GOAL) return 0;Explore the full codeHide the full code
D · Why it works and complexityO(4^(n/2) · pegs²) typical timeO(4ⁿ) spaceOpen the invariant and proofExplore the proofHide the proof
Reversibility is the enabler: it lets the goal-side search reuse the exact move generator, so meeting in the middle converts one deep search into two shallow ones — an exponential cut in explored states for deep instances.
ComplexityO(4^(n/2) · pegs²) typical time, O(4ⁿ) space — If the optimal distance is d, unidirectional BFS explores ~b^d states; meeting in the middle explores ~2·b^(d/2), an exponential reduction in the explored frontier (b = branching factor).
E · Edge cases and pitfalls6start == goal — Handled up front → returns 0 before any expansion.Explore edge casesHide edge cases
Edge cases handled
start == goalHandled up front → returns 0 before any expansion.shallow optimum (1–2 moves)Frontiers meet almost immediately; little benefit over plain BFS.deep optimumExplores far fewer states than unidirectional BFS — the intended win.
Pitfalls
- Checking the meeting condition only when *dequeuing* rather than when first relaxing — can miss the earliest meet; test right after setting self[next].
- Forgetting moves are reversible and writing a separate backward generator — unnecessary here.
- Not expanding the smaller frontier — loses the balancing that makes it fast.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int gena(int n, int[] posts) { int start = 0; for (int i = 0; i < n; i++) start |= (posts[i] - 1) << (2 * i); int total = 1 << (2 * n); int[] dist = new int[total];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Top disk taken as the largest
Only the smallest disk on a peg is on top and movable. Treating the largest as the top generates illegal moves and corrupts the search.
Explore the code comparisonHide the code comparison
Top disk taken as the largest
Only the smallest disk on a peg is on top and movable. Treating the largest as the top generates illegal moves and corrupts the search.
Don't write this
for (int d = 0; d < n; d++) top[(state >> (2*d)) & 3] = d; // smallest overwritten → top becomes LARGESTWrite this instead
for (int d = n - 1; d >= 0; d--) top[(state >> (2*d)) & 3] = d; // smallest disk ends as top2Placing a disk on a smaller one
A move is legal only onto an empty peg or a larger disk. Dropping a bigger disk onto a smaller one violates Hanoi rules and yields impossible configurations.
Explore the code comparisonHide the code comparison
Placing a disk on a smaller one
A move is legal only onto an empty peg or a larger disk. Dropping a bigger disk onto a smaller one violates Hanoi rules and yields impossible configurations.
Don't write this
if to != frm: # forgot the size check
nxt = move(state, d, to)Write this instead
if to != frm and (top[to] == -1 or top[to] > d):
nxt = move(state, d, to)3DFS instead of BFS
DFS explores depth-first, so the first time it reaches the goal is not necessarily via the fewest moves; you'd have to exhaust all paths. BFS visits by increasing distance, making the first goal hit optimal.
Explore the code comparisonHide the code comparison
DFS instead of BFS
DFS explores depth-first, so the first time it reaches the goal is not necessarily via the fewest moves; you'd have to exhaust all paths. BFS visits by increasing distance, making the first goal hit optimal.
Don't write this
stack = [start] # LIFO → depth-first, no shortest guarantee
while stack:
s = stack.pop()Write this instead
q = deque([start]) # FIFO → breadth-first, shortest path
while q:
s = q.popleft()Revise
Carry the pattern into the interview
Pattern to remember
Shortest path in an implicit state graph → BFS over encoded configurations
Code pattern to memorize
encode: state = Σ peg[disk] · 4^disk (2 bits per disk)
BFS:
dist[start] = 0
for each state, for each peg `from` with a top disk d:
for each peg `to` ≠ from:
if `to` empty OR top(to) is a LARGER disk:
relax move to the new state
answer = dist[goal] # goal = all disks on peg 1 → encoded 0Rules to remember
- 1The top disk of a peg is its smallest disk; only the top may move.
- 2A move is legal only onto an empty peg or onto a larger disk — never a smaller one.
- 3Encode the configuration as 2 bits per disk (peg 0–3); the full state is a single integer in [0, 4ⁿ).
- 4Use BFS, not DFS — BFS on an unweighted graph yields the minimum number of moves; DFS does not.
- 5Mark states visited (dist array) so you never re-expand — without it the search cycles forever (move a disk back and forth).
Use this pattern when
- Minimum moves / steps between configurations under discrete legal transitions
- State space is finite and modest enough to enumerate (here ≤ 4¹⁰)
- Each configuration encodes compactly into an integer or tuple
- Transitions are reversible and unweighted → shortest path = fewest moves
Choose another pattern when
- Classic 3-peg Hanoi from one peg to another → closed form 2ⁿ − 1, no search needed
- State space explodes beyond memory (huge n, many pegs) → IDA*/meet-in-the-middle, not plain BFS
- Moves have varying costs → Dijkstra, not BFS
- You only need feasibility, not the minimum → DFS/union-find may suffice
Interview takeaway
When a puzzle asks for the fewest moves and the configurations are enumerable, treat each configuration as a graph node and BFS. The whole craft is a compact state encoding (base-4 integer here) plus a correct legal-move generator — the shortest-path machinery is standard.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternMinimum-moves puzzles over enumerable configurations are shortest-path problems: encode each configuration as an integer, generate legal transitions, and BFS from start to goal. Bidirectional BFS or A* with an admissible heuristic trims the frontier when the optimal depth is large. Same template as Sliding Puzzle and Open the Lock.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Classic 3-Peg Tower of HanoiComing soonFrom one peg to another with 3 pegs → closed form 2ⁿ − 1, no search.
- Sliding PuzzleComing soonSame BFS-over-encoded-states template — the board encodes as a small integer/string.
- Open the LockComing soonBFS shortest path over 4-digit states; bidirectional BFS is the classic optimisation.
- Frame–Stewart 4-Peg HanoiOptimal all-on-one-peg → another-peg counts come from the Frame–Stewart recurrence; arbitrary starts still need search.