Sudoku Solver Visualization for Coding Interviews

Backtracking with constraint propagation — watch it backtrack.

Concept

A Sudoku solver is the friendly face of constraint satisfaction: fill a 9x9 grid with digits 1-9 such that every row, column, and 3x3 box contains all nine digits without repetition. The elegance of backtracking makes it approachable, while the performance differences between a naive approach and a constraint-propagation solver can be several orders of magnitude. Real-world solvers combine DFS backtracking with heuristics like MRV (minimum remaining values — pick the empty cell with the fewest candidates first) and AC-3 style constraint propagation. For interviews and puzzle apps the straightforward 'try each digit 1-9 and recurse' solver using bitmask-based conflict tracking is fast enough — most newspaper Sudokus solve in well under a millisecond. The same ideas generalize to Kakuro, Killer Sudoku, and scheduling with unary domain constraints.

How it works

Backtracking fills empty cells one at a time. Find the next empty cell (convention: scan row-major). For each candidate digit 1-9, check that it does not appear in the same row, column, or 3x3 box. If valid, place it and recurse; if the recursive call succeeds (found a complete solution), propagate success. If it fails, unplace the digit and try the next one. If no digit works, return failure and let the caller backtrack. Naively checking conflicts scans 27 cells per placement (O(n) per cell, 81 cells, lots of redundant work). A much faster version maintains three bitmasks per row, column, and box — each a 9-bit integer where bit d is set if digit d+1 is already used. Placement becomes an O(1) update: check (rowMask[r] | colMask[c] | boxMask[b]) has bit d unset, then set the bit; backtracking clears the bit. With this structure plus MRV cell ordering, even the notorious 'hardest Sudoku' from Arto Inkala solves in milliseconds. The algorithm is complete — if a solution exists it will be found, and if the puzzle is unsolvable it will report failure after exhausting the tree.

Implementation

public final class SudokuSolver {
    private SudokuSolver() {}

    public static boolean solveSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxes = new int[9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') {
                    int d = board[r][c] - '1';
                    int bit = 1 << d;
                    rows[r] |= bit;
                    cols[c] |= bit;
                    boxes[(r / 3) * 3 + c / 3] |= bit;
                }
            }
        }
        return backtrack(board, 0, rows, cols, boxes);
    }

    private static boolean backtrack(char[][] board, int pos, int[] rows, int[] cols, int[] boxes) {
        if (pos == 81) return true;
        int r = pos / 9, c = pos % 9;
        if (board[r][c] != '.') return backtrack(board, pos + 1, rows, cols, boxes);
        int b = (r / 3) * 3 + c / 3;
        int used = rows[r] | cols[c] | boxes[b];
        int available = (~used) & 0x1FF;
        while (available != 0) {
            int bit = available & -available;
            available ^= bit;
            int d = Integer.numberOfTrailingZeros(bit);
            board[r][c] = (char) ('1' + d);
            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
            if (backtrack(board, pos + 1, rows, cols, boxes)) return true;
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
        }
        board[r][c] = '.';
        return false;
    }

    public static boolean isValid(char[][] board) {
        int[] rows = new int[9], cols = new int[9], boxes = new int[9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int d = board[r][c] - '1';
                if (d < 0 || d >= 9) return false;
                int bit = 1 << d;
                int b = (r / 3) * 3 + c / 3;
                if (((rows[r] | cols[c] | boxes[b]) & bit) != 0) return false;
                rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
            }
        }
        return true;
    }
}

Complexity

• Time: Exponential in worst case; fast in practice
• Space: O(1) extra (81 cells + 27 masks)

Common pitfalls

• Storing candidates as a set of Integer objects instead of a bitmask — dramatically slower due to boxing.
• Scanning rows/cols/boxes on every placement instead of updating bitmasks.
• Forgetting to restore board[r][c] = '.' on backtrack — subsequent branches see stale placements.
• Using char arithmetic wrong — board[r][c] - '0' instead of board[r][c] - '1' produces off-by-one.
• Treating the puzzle as having a unique solution without checking — some puzzles are ambiguous.

Key design decisions & trade-offs

• Row-major vs MRV cell selection — Chosen: MRV for hard puzzles. Pick the cell with the fewest candidates next; prunes the tree aggressively.
• Bitmask vs boolean arrays — Chosen: Bitmask always. 9 bits in an int; conflict checks and enumeration via bit tricks are O(1).
• Pure DFS vs DFS + constraint propagation — Chosen: DFS + propagation for solver competitions. AC-3 naked pairs / hidden singles reduce branching; overkill for newspaper puzzles.

Practice problems

• Sudoku Solver

Interview follow-ups

• Add MRV cell selection and benchmark on the 'AI Escargot' hard puzzle.
• Implement naked-singles and hidden-singles constraint propagation.
• Extend to a Sudoku generator that produces puzzles with a unique solution.
• Generalize to 16x16 Sudoku using 16-bit masks.

Why it matters

Sudoku Solver is a core part of the Greedy & Backtracking toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related

• N-Queens
• DFS
• Bit Manipulation