AntInLoop

Sudoku Solver (Constraint Backtracking)

The Sudoku Solver fills a 9x9 grid using backtracking with O(1) bitmask tracking for rows, columns, and 3x3 boxes plus Minimum Remaining Values (MRV) pruning.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Sudoku Solver (Constraint Backtracking)

Solving a $9 \times 9$ Sudoku is the classic Constraint Satisfaction Problem (CSP). Tracking used digits 1..9 per row, column, and $3 \times 3$ box with 9-bit integer bitmasks makes validity checks $O(1)$, and picking the empty cell with the fewest legal candidates (MRV heuristic) solves even the hardest 17-clue puzzles in microseconds!

At a Glance

| Property | Value |

| :--- | :---: |

| Box Index Formula | box = (r / 3) * 3 + (c / 3) |

| Constraint Check | O(1) via used = rowMask[r] | colMask[c] | boxMask[box] |

| Best Pruning Heuristic | MRV (pick the empty cell with minimum popcount(candidates)) |

---

Practice Problems

Hard

1. Bitmask + MRV Sudoku Solver (LeetCode 37)

Solve a $9 \times 9$ Sudoku board in-place using bitmasks and Minimum Remaining Values cell selection.

Approach: Precompute rowM[9], colM[9], boxM[9] and the list of empty cells. At each step, swap the empty cell with the fewest legal digits (__builtin_popcount) to the front, try each valid bit, and backtrack on dead ends.

<details>

<summary>Show C++ Solution</summary>

#include <array>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

bool solveSudoku(std::vector<std::string>& board) {
    std::array<int, 9> rowM{}, colM{}, boxM{};
    std::vector<std::pair<int, int>> empties;
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            if (board[r][c] == '.') empties.push_back({r, c});
            else {
                int bit = 1 << (board[r][c] - '1');
                rowM[r] |= bit; colM[c] |= bit; boxM[(r / 3) * 3 + c / 3] |= bit;
            }
        }
    }

    auto dfs = [&](auto& self, size_t idx) -> bool {
        if (idx == empties.size()) return true;
        // MRV: pick cell with fewest valid digits
        size_t bestIdx = idx;
        int bestCand = 0, bestCnt = 10;
        for (size_t i = idx; i < empties.size(); ++i) {
            auto [r, c] = empties[i];
            int cand = ((1 << 9) - 1) & ~(rowM[r] | colM[c] | boxM[(r / 3) * 3 + c / 3]);
            int cnt = __builtin_popcount(cand);
            if (cnt == 0) return false;
            if (cnt < bestCnt) { bestCnt = cnt; bestCand = cand; bestIdx = i; if (cnt == 1) break; }
        }
        std::swap(empties[idx], empties[bestIdx]);
        auto [r, c] = empties[idx];
        int b = (r / 3) * 3 + c / 3;

        for (int mask = bestCand; mask; mask &= mask - 1) {
            int bit = mask & -mask;
            int d = __builtin_ctz(bit);
            board[r][c] = static_cast<char>('1' + d);
            rowM[r] |= bit; colM[c] |= bit; boxM[b] |= bit;
            if (self(self, idx + 1)) return true;
            rowM[r] ^= bit; colM[c] ^= bit; boxM[b] ^= bit;
            board[r][c] = '.';
        }
        std::swap(empties[idx], empties[bestIdx]);
        return false;
    };
    return dfs(dfs, 0);
}

int main() {
    std::vector<std::string> board = {
        "53..7....", "6..195...", ".98....6.",
        "8...6...3", "4..8.3..1", "7...2...6",
        ".6....28.", "...419..5", "....8..79"
    };
    std::cout << std::boolalpha << solveSudoku(board) << " | row0=" << board[0] << "\n";
    return 0;
}

</details>

---

Related Algorithms

  • N-Queens Problem — bitmask backtracking on an $N \times N$ board.
  • Bitmasking — bit operations powering $O(1)$ constraint checks.