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.