onenoughtone

Sudoku Solver Pattern

What is Sudoku?

Sudoku is a 9×9 grid-based puzzle where the goal is to fill each cell with digits from 1 to 9 such that:

Each row contains all digits from 1 to 9 without repetition
Each column contains all digits from 1 to 9 without repetition
Each of the nine 3×3 subgrids contains all digits from 1 to 9 without repetition

Backtracking Approach

Sudoku is a perfect example of a constraint satisfaction problem that can be solved using backtracking:

Find an empty cell in the Sudoku grid
Try placing digits 1-9 in the empty cell
Check if the digit satisfies all Sudoku constraints
If valid, recursively try to fill the rest of the grid
If the recursive call fails, backtrack and try a different digit
If all digits have been tried and none work, backtrack to the previous cell

Implementation

Here's how we can implement the Sudoku solver using backtracking:

Time and Space Complexity

Time Complexity:

O(9^(n²)), where n is the size of the Sudoku grid (typically 9). In the worst case, we need to try all 9 digits for each of the n² cells.

Space Complexity:

O(n²) for the board representation, plus O(n²) for the recursion stack in the worst case.

Previous Next

Pattern 2: Sudoku Solver

Learn how to solve Sudoku puzzles using backtracking.

What is Sudoku?

Sudoku is a 9×9 grid-based puzzle where the goal is to fill each cell with digits from 1 to 9 such that:

Each row contains all digits from 1 to 9 without repetition
Each column contains all digits from 1 to 9 without repetition
Each of the nine 3×3 subgrids contains all digits from 1 to 9 without repetition

Example Sudoku Puzzle:

Why Backtracking?

Sudoku is a perfect candidate for backtracking because:

Multiple Constraints

Each cell must satisfy row, column, and box constraints simultaneously.

Incremental Filling

We can fill the grid one cell at a time, checking constraints as we go.

Early Pruning

We can quickly identify and abandon invalid paths without exploring all possibilities.

Guaranteed Solution

A properly designed Sudoku puzzle has exactly one solution, which backtracking can find.

Backtracking Approach

1Find Empty

Find an empty cell in the Sudoku grid.

2Try Digits

Try placing digits 1-9 in the empty cell.

3Check Valid

Check if the digit satisfies all Sudoku constraints.

4Recurse

If valid, recursively try to fill the rest of the grid.

5Backtrack

If the recursive call fails, backtrack and try a different digit.

6Complete

Continue until the entire grid is filled or no solution exists.

Implementation

Here's how we can implement the Sudoku solver using backtracking:

sudokuSolver.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
function solveSudoku(board) {
  // Try to solve the Sudoku puzzle
  solve(board);
  return board;
}
 
function solve(board) {
  // Find an empty cell
  const emptyCell = findEmptyCell(board);
  
  // If there are no empty cells, the puzzle is solved
  if (!emptyCell) {
    return true;
  }
  
  const [row, col] = emptyCell;
  
  // Try placing digits 1-9 in the empty cell
  for (let num = 1; num <= 9; num++) {
    // Check if it's valid to place the number
    if (isValid(board, row, col, num)) {
      // Place the number
      board[row][col] = num;
      
      // Recursively try to solve the rest of the puzzle
      if (solve(board)) {
        return true;
      }
      
      // If placing the number doesn't lead to a solution, backtrack
      board[row][col] = 0;
    }
  }
  
  // No solution found with the current configuration
  return false;
}
 
function findEmptyCell(board) {
  // Find the first empty cell (represented by 0)
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        return [row, col];
      }
    }
  }
  
  // No empty cells found
  return null;
}
 
function isValid(board, row, col, num) {
  // Check if the number already exists in the row
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) {
      return false;
    }
  }
  
  // Check if the number already exists in the column
  for (let y = 0; y < 9; y++) {
    if (board[y][col] === num) {
      return false;
    }
  }
  
  // Check if the number already exists in the 3x3 box
  const boxRow = Math.floor(row / 3) * 3;
  const boxCol = Math.floor(col / 3) * 3;
  
  for (let y = boxRow; y < boxRow + 3; y++) {
    for (let x = boxCol; x < boxCol + 3; x++) {
      if (board[y][x] === num) {
        return false;
      }
    }
  }
  
  // The number is valid to place
  return true;
}

Time and Space Complexity

Time Complexity

O(9^(n²)), where n is the size of the Sudoku grid (typically 9).

In the worst case, we need to try all 9 digits for each of the n² cells. However, in practice, the algorithm is much faster because of constraint propagation and early pruning.

Space Complexity

O(n²) for the board representation, plus O(n²) for the recursion stack.

We need an n×n grid to represent the Sudoku board, and the recursion stack can go up to depth n² in the worst case (if we fill all cells one by one).

Previous: N-Queens Pattern Next: Combination Sum Pattern

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Sudoku Solver Pattern

What is Sudoku?

Sudoku is a 9×9 grid-based puzzle where the goal is to fill each cell with digits from 1 to 9 such that:

Each row contains all digits from 1 to 9 without repetition
Each column contains all digits from 1 to 9 without repetition
Each of the nine 3×3 subgrids contains all digits from 1 to 9 without repetition

Backtracking Approach

Sudoku is a perfect example of a constraint satisfaction problem that can be solved using backtracking:

Find an empty cell in the Sudoku grid
Try placing digits 1-9 in the empty cell
Check if the digit satisfies all Sudoku constraints
If valid, recursively try to fill the rest of the grid
If the recursive call fails, backtrack and try a different digit
If all digits have been tried and none work, backtrack to the previous cell

Implementation

Here's how we can implement the Sudoku solver using backtracking:

Time and Space Complexity

Time Complexity:

O(9^(n²)), where n is the size of the Sudoku grid (typically 9). In the worst case, we need to try all 9 digits for each of the n² cells.

Space Complexity:

O(n²) for the board representation, plus O(n²) for the recursion stack in the worst case.

Previous Next

Pattern 2: Sudoku Solver

Learn how to solve Sudoku puzzles using backtracking.

What is Sudoku?

Sudoku is a 9×9 grid-based puzzle where the goal is to fill each cell with digits from 1 to 9 such that:

Each row contains all digits from 1 to 9 without repetition
Each column contains all digits from 1 to 9 without repetition
Each of the nine 3×3 subgrids contains all digits from 1 to 9 without repetition

Example Sudoku Puzzle:

Why Backtracking?

Sudoku is a perfect candidate for backtracking because:

Multiple Constraints

Each cell must satisfy row, column, and box constraints simultaneously.

Incremental Filling

We can fill the grid one cell at a time, checking constraints as we go.

Early Pruning

We can quickly identify and abandon invalid paths without exploring all possibilities.

Guaranteed Solution

A properly designed Sudoku puzzle has exactly one solution, which backtracking can find.

Backtracking Approach

1Find Empty

Find an empty cell in the Sudoku grid.

2Try Digits

Try placing digits 1-9 in the empty cell.

3Check Valid

Check if the digit satisfies all Sudoku constraints.

4Recurse

If valid, recursively try to fill the rest of the grid.

5Backtrack

If the recursive call fails, backtrack and try a different digit.

6Complete

Continue until the entire grid is filled or no solution exists.

Implementation

Here's how we can implement the Sudoku solver using backtracking:

sudokuSolver.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
function solveSudoku(board) {
  // Try to solve the Sudoku puzzle
  solve(board);
  return board;
}
 
function solve(board) {
  // Find an empty cell
  const emptyCell = findEmptyCell(board);
  
  // If there are no empty cells, the puzzle is solved
  if (!emptyCell) {
    return true;
  }
  
  const [row, col] = emptyCell;
  
  // Try placing digits 1-9 in the empty cell
  for (let num = 1; num <= 9; num++) {
    // Check if it's valid to place the number
    if (isValid(board, row, col, num)) {
      // Place the number
      board[row][col] = num;
      
      // Recursively try to solve the rest of the puzzle
      if (solve(board)) {
        return true;
      }
      
      // If placing the number doesn't lead to a solution, backtrack
      board[row][col] = 0;
    }
  }
  
  // No solution found with the current configuration
  return false;
}
 
function findEmptyCell(board) {
  // Find the first empty cell (represented by 0)
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        return [row, col];
      }
    }
  }
  
  // No empty cells found
  return null;
}
 
function isValid(board, row, col, num) {
  // Check if the number already exists in the row
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) {
      return false;
    }
  }
  
  // Check if the number already exists in the column
  for (let y = 0; y < 9; y++) {
    if (board[y][col] === num) {
      return false;
    }
  }
  
  // Check if the number already exists in the 3x3 box
  const boxRow = Math.floor(row / 3) * 3;
  const boxCol = Math.floor(col / 3) * 3;
  
  for (let y = boxRow; y < boxRow + 3; y++) {
    for (let x = boxCol; x < boxCol + 3; x++) {
      if (board[y][x] === num) {
        return false;
      }
    }
  }
  
  // The number is valid to place
  return true;
}

Time and Space Complexity

Time Complexity

O(9^(n²)), where n is the size of the Sudoku grid (typically 9).

In the worst case, we need to try all 9 digits for each of the n² cells. However, in practice, the algorithm is much faster because of constraint propagation and early pruning.

Space Complexity

O(n²) for the board representation, plus O(n²) for the recursion stack.

We need an n×n grid to represent the Sudoku board, and the recursion stack can go up to depth n² in the worst case (if we fill all cells one by one).

Previous: N-Queens Pattern Next: Combination Sum Pattern