03. Sudoku Solver
Write a program to solve a Sudoku puzzle by filling empty cells ('.'). A valid solution must satisfy the constraint that digits '1'-'9' appear once per row, column, and $3 \times 3$ sub-box.
How It Works & Algorithmic Design
Solves using Bitmask State Constraint Backtracking:
- Constraint Hash/Bitmasks: Track digits used in
rows[r],cols[c], andboxes[boxIdx]. - Cell Processing: Find next empty cell
(r, c):- Try placing digits $d \in [1, 9]$:
- Check if bit for $d$ is clear in row, col, and box bitmasks.
- Toggle bit mask, update board cell
board[r][c] = d. - Recurse to next empty cell.
- If recursion succeeds, return
true. - Backtrack: un-toggle bit mask, reset cell to
'.'.
- Try placing digits $d \in [1, 9]$:
Why This Approach Works Best
Bitwise checks make validation $O(1)$, rapidly terminating invalid grid paths.
Example Walkthrough
Input:
9x9 grid with '.' empty cellsUnsolved Sudoku matrix.
Validation:
Each 1-9 digit appears once in every row, column, and 3x3 block.Standard rules.
Output:
Fully filled valid 9x9 boardIn-place board mutation.
Answer: Sudoku Solver implementation
function solveSudoku(board) {
const rows = new Array(9).fill(0);
const cols = new Array(9).fill(0);
const boxes = new Array(9).fill(0);
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] !== '.') {
const val = Number(board[r][c]);
const mask = 1 << val;
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
rows[r] |= mask; cols[c] |= mask; boxes[b] |= mask;
}
}
}
function solve(r, c) {
if (r === 9) return true;
if (c === 9) return solve(r + 1, 0);
if (board[r][c] !== '.') return solve(r, c + 1);
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let val = 1; val <= 9; val++) {
const mask = 1 << val;
if (!(rows[r] & mask) && !(cols[c] & mask) && !(boxes[b] & mask)) {
rows[r] |= mask; cols[c] |= mask; boxes[b] |= mask;
board[r][c] = String(val);
if (solve(r, c + 1)) return true;
rows[r] &= ~mask; cols[c] &= ~mask; boxes[b] &= ~mask;
board[r][c] = '.';
}
}
return false;
}
solve(0, 0);
}💡 Backtrack across empty cells while tracking digit constraints using bitmasks.
Key Takeaways
- Box index calculated via
(r / 3) * 3 + (c / 3). - Bitwise masks make $O(1)$ digit availability checks.
- Modifies board array directly in-place.