Skip to content
LeetCode 37 Sudoku: From Brute Force to Millisecond Solving with Bitmask & MRV
Fundamentals 32 min read

LeetCode 37 Sudoku: From Brute Force to Millisecond Solving with Bitmask & MRV

This article walks through solving LeetCode 37 Sudoku using backtracking with three optimization tiers: brute-force validation, boolean state arrays for O(1) constraint checks, and bitmask combined with MRV heuristic achieving 1-3ms runtime, plus 10 common interview follow-up questions and a pitfall checklist.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

Understand the Problem Essence

LeetCode 37 asks to solve a 9×9 Sudoku puzzle. The rules are three constraints: each row, column, and 3×3 box must contain digits 1-9 exactly once. This is a classic Constraint Satisfaction Problem (CSP). The standard solution is backtracking = DFS + undo choice. The board has 81 fixed cells; brute-force search space is up to 9^81, so we must validate as we go and backtrack on conflict.

Interview opening (memorize): "Sudoku requires no duplicates in rows, columns, and 3×3 boxes. I need to fill all empty cells under these constraints — a typical CSP. Fixed 9×9 board, DFS backtracking fits: go deeper if valid, undo and try next digit on dead end. Unique solution guaranteed, so we can return immediately upon finding one."

Key details: unique solution guarantees early exit; unlike N-Queens (single-layer recursion), Sudoku uses two-dimensional recursion (every cell tries digits); LeetCode 36 only validates a board, while 37 must construct a solution — constraint-checking logic is reusable.

Two Critical Implementation Details

2.1 Box Index Formula

Cell (i, j) belongs to box boxId = (i / 3) * 3 + j / 3. Integer division floors automatically. Common bug: writing i/3 + j/3 (missing *3) causing overlapping box indices and silent validation failure.

2.2 Backtracking Decision Tree

Each empty cell is a tree node with up to 9 branches (digits 1-9). Legal branches recurse deeper; illegal ones are pruned. If all 9 fail, return to parent and try next digit. Two fatal mistakes: ① Recursive function must return boolean . Returning true on success propagates upward, short-circuiting remaining branches — this "find-and-stop" pruning is the most frequent error. ② Undo must mirror do exactly. Shared state across branches means forgetting to revert corrupts sibling branches. Always pair do/undo in a single helper (e.g., mark(i, j, d, on)).

Bronze: Brute-Force Validation (Correctness First)

Double loop finds empty cell, tries 1-9, each time scans row, column, box (27 cells) via isValid. Single loop handles all three checks: for i=0..8, check column board[i][col], row board[row][i], box via boxRow = row/3*3 + i/3, boxCol = col/3*3 + i%3. Two return positions matter: loops finish → board full → return true; cell tries all 9 digits → return false to trigger backtrack. Works but interviewer will ask: "Can we avoid scanning 27 cells every time?"

Silver: Boolean State Arrays — O(1) Validation

Maintain three boolean[9][10] arrays: rows, cols, boxes. Pre-fill with given digits. Validation becomes rows[i][d] || cols[j][d] || boxes[boxId][d] — O(1). Encapsulate set/clear in mark(i, j, d, on) for symmetry. Flatten 81 cells into single index k ( i=k/9, j=k%9), recursion advances k+1, termination at k==81. Alternative: pre-collect empty cells into list, recurse by list index — foundation for MRV later. Speed jumps to ~10ms.

Gold: Bitmask + MRV — Millisecond Level

5.1 One int Holds 9 Digits

Digits 1-9 map to bits 0-8. row[0] = 0b001010011 means digits 1,2,5,7 used. 27 int s replace 243 booleans, cache-friendly. Operations become single CPU instructions:

Check used: used & (1<<d) Mark used: used |= (1<<d) Unmark: used ^= (1<<d) (XOR restores exactly, symmetric with mark)

All candidates: ~(row|col|box) & 0x1FF (mask must be 0x1FF to clear high bits from Java's 32-bit ~)

Count candidates: Integer.bitCount(mask) Iterate candidates:

for (int mask=cand; mask!=0; mask &= mask-1) { int bit = mask & -mask; int num = Integer.numberOfTrailingZeros(bit); }

5.2 MRV (Minimum Remaining Values) Heuristic

At each recursion level, scan remaining empty cells, pick the one with fewest candidates ( Integer.bitCount(cand)). If any cell has 0 candidates → dead end → immediate return false. Swap chosen cell to current position via Collections.swap (O(1), no extra space), swap back on backtrack . MRV only changes search order, not space — completeness preserved. Overhead of scanning is outweighed by massive branch reduction on hard puzzles (10-100x speedup).

5.3 Complete Gold Implementation

class Solution {
    private int[] row = new int[9], col = new int[9], box = new int[9];
    private List<int[]> blanks = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int i=0;i<9;i++)
            for (int j=0;j<9;j++) {
                if (board[i][j]=='.') blanks.add(new int[]{i,j});
                else {
                    int bit = 1 << (board[i][j]-'1');
                    row[i] |= bit; col[j] |= bit; box[(i/3)*3+j/3] |= bit;
                }
            }
        backtrack(board, 0);
    }

    private boolean backtrack(char[][] board, int pos) {
        if (pos == blanks.size()) return true;
        int best = pos, minCnt = 10, bestMask = 0;
        for (int k=pos; k<blanks.size(); k++) {
            int[] p = blanks.get(k);
            int mask = candidates(p[0], p[1]);
            int cnt = Integer.bitCount(mask);
            if (cnt < minCnt) { minCnt=cnt; best=k; bestMask=mask; if (cnt<=1) break; }
        }
        if (minCnt == 0) return false;
        Collections.swap(blanks, pos, best);
        int[] p = blanks.get(pos);
        int i=p[0], j=p[1], b=(i/3)*3+j/3;
        for (int mask=bestMask; mask!=0; mask &= mask-1) {
            int bit = mask & -mask;
            int num = Integer.numberOfTrailingZeros(bit);
            board[i][j] = (char)('1'+num);
            row[i] |= bit; col[j] |= bit; box[b] |= bit;
            if (backtrack(board, pos+1)) return true;
            row[i] ^= bit; col[j] ^= bit; box[b] ^= bit;
        }
        board[i][j] = '.';
        Collections.swap(blanks, pos, best);
        return false;
    }

    private int candidates(int i, int j) {
        return ~(row[i] | col[j] | box[(i/3)*3+j/3]) & 0x1FF;
    }
}

5.4 Alternative: Bits Mean "Available"

Initialize rows/cols/boxes with all 9 bits set (0x1FF). Placing digit d flips bit via XOR: rows[i] ^= 1<<d. Candidates become intersection: rows[i] & cols[j] & boxes[b] — no complement needed. XOR twice restores automatically. Both styles equivalent; pick one and stay consistent.

Three Versions Compared

Validation: Bronze O(27) scan each time; Silver O(1) array access; Gold O(1) bit ops

Candidate Enum: Bronze loop 1-9; Silver loop 1-9; Gold lowbit only legal

Search Order: Bronze row-major; Silver row-major; Gold MRV (tightest first)

State Overhead: Bronze none; Silver 270 booleans; Gold 27 ints

Measured Time (9×9): Bronze 50-200ms; Silver ~10ms; Gold 1-3ms

Code Complexity: Bronze low; Silver low; Gold medium

Interview Impact: Bronze pass; Silver solid; Gold bonus

Optimization essence: fixed 81 cells, theoretical upper bound unchanged — we only "chop the tree": O(1) cuts constants, MRV cuts branching factor, dead-cell pruning cuts dead subtrees early. In exponential search, reducing the base changes everything.

10 Real-World Pitfalls

Slow validation — O(27) per check → State arrays / bitmask → O(1)

Wrong box index — i/3+j/3 overlaps boxes → (i/3)*3+j/3, draw 3×3 box map

Search explosion — Worst 9^m → TLE → Pre-prune + dead-cell + MRV

Forget undo — State pollution, wrong answers → Pair do/undo in single mark / flip Don't stop after solution — Timeout → boolean return or done flag, short-circuit

Complement without mask — Ghost candidates, OOB → ~used & 0x1FF always

Char-digit conversion off-by-one — '0'+d vs '1'+d mixup → Bitmask version: consistently '1'+d (bit0=digit1)

Index out of bounds — i,j exceed board → While-skip or pre-collect blanks list

MRV scan overhead — Extra full scan per level → Worth it on hard puzzles; degrade to fixed order on easy

Extend to 16×16 — int 32 bits insufficient → Use long or BitSet, framework unchanged

10 High-Frequency Interview Follow-Ups

Time/space complexity? Worst-case O(9^m) but board fixed → O(1) constant upper bound; actual depends on pruning. Space: O(m) recursion stack (max 81) + O(1) state arrays.

Why not BFS? Tree-shaped space suits DFS: one board state throughout. BFS would queue every intermediate board → memory explosion.

Backtracking vs recursion? Backtracking is a recursion pattern: choose → recurse → unchoose. Recursion provides descent; backtracking provides trial-and-error.

Why bitwise, not boolean array or HashSet? Boolean array needs 3 addressings + 9-loop for candidates; HashSet has hashing/boxing overhead. Bitmask = CPU instruction level, merges constraints with single |.

Why XOR for undo? Bit guaranteed 0 before set (constraints ensure), | sets, ^ restores exactly — O(1), branchless, bug-free, symmetric.

Does MRV miss solutions? No. Only reorders search, same space, completeness unchanged.

Other methods? Exact Cover + Algorithm X / Dancing Links (DLX) — elegant but complex, building toroidal lists overhead not worth it in interviews. Mentioning "I know DLX but backtracking+bitmask+MRV has best ROI" scores points.

All solutions / verify uniqueness? Remove early return: on solution, deep-copy board to results, continue backtracking. Must copy — later undos would corrupt saved answer. Uniqueness check: if second solution found, not unique.

Stack overflow? Max depth 81 << default stack, safe. For larger boards, convert to explicit stack iteration.

Multi-thread speedup? Theoretically: split root's 9 branches across threads, use AtomicBoolean or CompletableFuture.anyOf to short-circuit. But tiny problem size → thread overhead may exceed gain. "Theoretically feasible, practically situational" shows engineering mindset.

Practical Interview Tips

Explain approach before coding. Walk through backtracking frame, three constraints handling, backtrack mechanism — get nod before typing.

Write basic version first, then optimize. Produce correct boolean-array version, then proactively say "can optimize with bitmask and MRV" — layered thinking beats showboating.

boolean return is the #1 trap. void returns keep searching after solution → timeout.

Obsess over indices and conversions. i/3, j/3 for box; num+'0', c-'1' — one char off = WA.

Show synthesis at close. Note: Sudoku, N-Queens, permutations, subsets all share "choose → recurse → unchoose"; only pruning differs.

One-liner: Sudoku = backtracking foundation + bitwise acceleration + MRV pruning. Backtracking ensures correct state transitions; bitwise and MRV ensure speed — former is passing grade, latter is distance to offer.

Mnemonic: Backtracking is the skeleton, pruning the soul, bitwise the accelerator, MRV the finishing touch. This problem tests not just DFS, but whether you can turn "one more loop" into "one more instruction" and slim the search tree before it grows.

Master Sudoku and N-Queens, permutations, combinations, subsets all click — same three moves: choose → recurse → unchoose , rest is pruning.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Interview PreparationbacktrackingAlgorithm OptimizationSudoku solverbitmaskconstraint satisfactionLeetCode 37MRV
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.