Sudoku Algorithm and Problem
Sudoku is the perfect backtracking problem. You have a 9x9 grid. Fill every cell with 1-9. No repeats in any row, column, or 3x3 box.
16 Mar 2024
Sudoku is the perfect backtracking problem. You have a 9x9 grid. Fill every cell with 1-9. No repeats in any row, column, or 3x3 box.
The rules are tight. The search space is enormous. Brute-forcing all combinations would take forever. But backtracking makes it manageable.
How Backtracking Solves It
Find an empty cell. Try 1. Check if it's valid. If yes, move on to the next empty cell. If you hit a dead end — no number works — undo the last choice and try the next number.
Think of it like navigating a maze. Every wrong turn gets reversed. You only keep moves that lead forward.
The Grid
const grid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
];Zeros represent empty cells.
The Solver
function isValid(grid, row, col, num) {
for (let i = 0; i < 9; i++) {
if (grid[row][i] === num) return false;
if (grid[i][col] === num) return false;
}
const boxRow = Math.floor(row / 3) * 3;
const boxCol = Math.floor(col / 3) * 3;
for (let r = boxRow; r < boxRow + 3; r++) {
for (let c = boxCol; c < boxCol + 3; c++) {
if (grid[r][c] === num) return false;
}
}
return true;
}
function solve(grid) {
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (grid[row][col] === 0) {
for (let num = 1; num <= 9; num++) {
if (isValid(grid, row, col, num)) {
grid[row][col] = num;
if (solve(grid)) return true;
grid[row][col] = 0; // backtrack
}
}
return false; // no valid number found
}
}
}
return true; // all cells filled
}
solve(grid);
console.log(grid);Complexity
- Time: O(9^m) where m is the number of empty cells. Worst case is exponential, but constraint checking prunes most branches early.
- Space: O(m) for the recursion stack.
The Trade-off
This brute-force-with-pruning approach is simple and correct. It solves any valid Sudoku. But for competitive programming or very sparse grids, you'd want constraint propagation (like Knuth's Algorithm X) to cut the search space dramatically.
For learning backtracking? Sudoku is hard to beat as an example.