Stage 1 · Code
Backtracking
Sudoku Solver
Constraint propagation and backtracking for 9×9 Sudoku.
8 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Constraints
Sudoku: 9×9 grid. Each row, column, and 3×3 box must contain digits 1-9 exactly once. Empty cells marked '.'. Fill all empty cells to satisfy constraints.
Backtracking with Constraint Propagation
Track used digits in rows, cols, boxes with bitsets. Find empty cell, try valid digits (1-9 not in row/col/box). Recurse. Use MRV (minimum remaining values) heuristic: pick cell with fewest candidates.
Gosudoku-solver.go
75 linesLn 1, Col 1Go
Bitsets for O(1) constraint checks. MRV heuristic picks cell with fewest valid digits. Standard backtracking with constraint propagation.
Optimizations
- Bitsets: 9-bit ints for rows/cols/boxes. O(1) check/place/remove.
- MRV heuristic: Pick cell with fewest candidates first. Reduces branching dramatically.
- Forward checking: After placing, immediately update constraints.
- Naked singles: If cell has only 1 candidate, must place it.
- Hidden singles: If digit can only go in one cell in unit, place it.
- Bit operations:
&for check,|=for add,&^=for remove.x & -xfor lowest set bit.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.