Skip to main content
MSH Logo

Sudoku Algorithms Explained

Published on

Interactive Demo

Explore how Sudoku algorithms work step by step:

Step 1: The Empty Grid
Sudoku is played on a 9x9 grid divided into nine 3x3 boxes. Each cell will contain a number from 1 to 9.

The 9x9 grid is divided into nine 3x3 boxes. Every cell will contain a number from 1 to 9.

The Three Constraints

Every valid Sudoku must satisfy:

  1. Row: Each row contains 1-9 exactly once
  2. Column: Each column contains 1-9 exactly once
  3. Box: Each 3×3 box contains 1-9 exactly once

Core Algorithms

Constraint Validation

Check if placing a number is valid:

1const isValid = (grid: Grid, row: number, col: number, num: number): boolean => {
2  // Check row
3  if (grid[row].some(cell => cell.value === num)) return false;
4
5  // Check column
6  if (grid.some(r => r[col].value === num)) return false;
7
8  // Check 3x3 box
9  const boxRow = Math.floor(row / 3) * 3;
10  const boxCol = Math.floor(col / 3) * 3;
11  for (let r = boxRow; r < boxRow + 3; r++) {
12    for (let c = boxCol; c < boxCol + 3; c++) {
13      if (grid[r][c].value === num) return false;
14    }
15  }
16
17  return true;
18};

Backtracking Solver

The core solving algorithm - try each number, backtrack on failure:

1const solve = (grid: Grid): boolean => {
2  const empty = findEmptyCell(grid);
3  if (!empty) return true; // Solved!
4
5  const { row, col } = empty;
6
7  for (let num = 1; num <= 9; num++) {
8    if (isValid(grid, row, col, num)) {
9      grid[row][col].value = num;
10
11      if (solve(grid)) return true;
12
13      grid[row][col].value = null; // Backtrack
14    }
15  }
16
17  return false;
18};

Puzzle Generation

  1. Generate a complete solution using randomized backtracking
  2. Remove cells while ensuring unique solution remains
1const generatePuzzle = (cellsToRemove: number): Grid => {
2  const grid = createEmptyGrid();
3  fillWithRandomSolution(grid);
4
5  const positions = shuffle(getAllPositions());
6  let removed = 0;
7
8  for (const { row, col } of positions) {
9    if (removed >= cellsToRemove) break;
10
11    const backup = grid[row][col].value;
12    grid[row][col].value = null;
13
14    if (!hasUniqueSolution(grid)) {
15      grid[row][col].value = backup; // Restore - removing creates ambiguity
16    } else {
17      removed++;
18    }
19  }
20
21  return grid;
22};

Candidate Calculation

Find possible numbers for a cell by eliminating used values:

1const getCandidates = (grid: Grid, row: number, col: number): number[] => {
2  const used = new Set<number>();
3
4  // Collect from row, column, and box
5  grid[row].forEach(c => c.value && used.add(c.value));
6  grid.forEach(r => r[col].value && used.add(r[col].value));
7
8  // Check 3x3 box
9  const boxRow = Math.floor(row / 3) * 3;
10  const boxCol = Math.floor(col / 3) * 3;
11  for (let r = boxRow; r < boxRow + 3; r++) {
12    for (let c = boxCol; c < boxCol + 3; c++) {
13      if (grid[r][c].value) used.add(grid[r][c].value);
14    }
15  }
16
17  return [1,2,3,4,5,6,7,8,9].filter(n => !used.has(n));
18};

Complexity

AlgorithmTimeNote
ValidationO(n)n = 9
BacktrackingO(9^m)m = empty cells
GenerationO(9^n)n = grid size

Try It

Play the game: Sudoku

References

GET IN TOUCH

Let's work together

I build fast, accessible, and delightful digital experiences for the web.
Whether you have a project in mind or just want to connect, I'd love to hear from you.

or reach out directly at hello@mohammadshehadeh.com