Nonogram Solver
Solve a nonogram by constraint satisfaction over row clues, backtracking with propagation, with a bug → feature → scale arc.
Problem
A nonogram puzzle: rows and columns have clues — numbers describing consecutive filled runs. The starter code has a bug.
Phase 1 — Fix the bug
parseClues("3,1") works, but edge inputs break: a clue of "0" (empty row) and sequences like "1,0,1" are misread. Parse run-length clues exactly.
Phase 2 — Feature
Implement solve(): determine the filled cells such that every row and column matches its clues. Apply row/column constraint propagation first — for each row, compute which cells are forced — then backtrack over the remaining ambiguity.
Phase 3 — Scale
Solve larger grids. Pure backtracking over every cell explodes; propagation and good variable ordering are the difference.
What interviewers watch
Exact clue parsing, propagation that actually prunes before search (not brute force), and a clean choose-constrain-undo loop. This is the hardest structured problem for a reason.