Solving 𝑁 × 𝑁 Sudoku with Backtracking

UPDATE

• 24/9/2024 - Added best case and average case time complexity

Introduction

I recently had a chance to tinker with some aspect of sudoku that I hadn’t done before; aspects such as creating and solving a sudoku puzzle programmatically. This blog encompasses the latter part - solving a sudoku programmatically. More specifically, the blog is going to focus on time complexity of the solver’s algorithm and and provide empirical measurements of the time required for various grid sizes.

What is Sudoku?

According to Wikipedia,

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid contains all of the digits from 1 to 9.

As mentioned, classically, the game of sudoku involves a square grid of 9×9 size. But it can be extended to larger board sizes of 16×16 or even up to 25×25 sized boards.

// A typical sudoku puzzle
+-------+-------+-------+
| . 8 . | . 7 . | . . 3 |
| . . . | . . . | . 8 9 |
| . . . | 6 . . | . 1 . |
+-------+-------+-------+
| . . . | . . . | . 7 . |
| . . . | . . 5 | . . 6 |
| 9 7 . | 8 6 . | . . 2 |
+-------+-------+-------+
| 3 . 6 | 1 5 . | 9 . . |
| 5 . . | . . 6 | . . . |
| . . . | . 4 7 | . . . |
+-------+-------+-------+

Algorithm for Solving Sudoku

The algorithm uses a backtracking approach for solving a sudoku puzzle. Backtracking is a method used to solve problems by trying out different solutions step by step. If it finds that a particular choice doesn't work, it goes back and tries a different option. For Sudoku, this means filling in one cell at a time and checking if each number is valid before moving on to the next cell. If a choice leads to a dead end, it "backs up" to try another number.

const solve = (board: Board) => {
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 0) {
        for (let num = 1; num < board.length + 1; num++) {
          if (isValid(board, i, j, num)) {
            board[i][j] = num;
            if (solve(board)) return true;
            else board[i][j] = 0;
          }
        }
        return false;
      }
    }
  }
  return true;
};

/**
 * Checks if the current number placement satifies all sudoku rules
 */
const isValid = (board: Board, row: number, col: number, num: number) => {
  for (let i = 0; i < board.length; i++) {
    if (board[row][i] === num) return false;
    if (board[i][col] === num) return false;
  }

  const subgridSize = Math.sqrt(board.length);
  const rowStart = row - Math.trunc(row % subgridSize);
  const colStart = col - Math.trunc(col % subgridSize);

  for (let i = 0; i < subgridSize; i++) {
    for (let j = 0; j < subgridSize; j++) {
      if (board[rowStart + i][colStart + j] === num) return false;
    }
  }

  return true;
};

Here’s a simple breakdown of how the solver works:

1. Loop Through the Board: The function starts by checking every cell in the Sudoku board using two nested loops. The outer loop iterates through each row, and the inner loop iterates through each column. That means the board is looped over from left to right and top to bottom.

2. Find an Empty Cell: If it encounters an empty cell, it will try to fill it with numbers from 1 to 𝑁 (where 𝑁 is the size of the board).

3. Check Validity: For each number, it calls the isValid function to check if placing that number in the current cell is allowed according to Sudoku rules.

4. Recursive Call: If the number is valid, it places the number in the cell and recursively calls solve with the newly filled board to try to fill the next cell. If the recursive call returns true, it means the puzzle is solved.

5. Backtrack if Necessary: If placing the number doesn’t lead to a solution (the recursive call returns false), it resets the cell to 0 (indicating empty cell) and tries the next number.

6. Return True When Solved: If all cells are filled correctly, the function returns true.

The isValid Function

This function checks if placing a number in a specific cell follows Sudoku rules:

1. Row and Column Check: It first checks if the number already exists in the same row or column. If it does, the function returns false.

2. Subgrid Check: It calculates which subgrid the cell belongs to and checks all cells in that subgrid to see if the number is already present. If it is, the function returns false.

If the number passes all checks (not found in the row, column, or subgrid), the function returns true, indicating it can be placed there.

Time Complexity Analysis

1. Board size: If board size is 𝑁. Then a sudoku board has 𝑁² cells.

2. Empty Cells: In the worst case, the algorithm may need to fill all the cells, i.e., 𝑁² cells.

3. Number placement attempts: For each empty cell, we may attempt to place numbers from 1 to 𝑁. This means we have up to 𝑁 attempts for each empty cell.

4. Validity Checks: The isValid function performs checks across a row, column and a subgrid of the current cell. The size of row and column are 𝑁 and size of the subgrid is √𝑁 * √𝑁 = 𝑁. That means it runs for 3𝑁 ≈ 𝑁; resulting in a total validity check complexity of O(𝑁).

5. Recursive Nature: The backtracking approach can lead to a branching factor of 𝑁, as for every empty cell, the algorithm may have explore placing each of the 𝑁 numbers.

Overall Time Complexity

Worst Case

Putting this together gives us:

$$N^{N*N}= N^{N^2}$$

This is because we potentially explore each cell 𝑁² and for each cell, try up to 𝑁 numbers. This is the worst case time complexity.

Best Case

The best-case time complexity of the backtracking algorithm for solving Sudoku can occur when the puzzle is almost solved, with only a few empty cells to fill, and the first attempts at placing numbers are successful without much backtracking. In this scenario, the best-case complexity would be significantly lower than the worst case.

That means, the best-case time complexity would be O(𝑁²), where the algorithm only has to check each empty cell once and fill it correctly on the first attempt. But it’s important to note that this best-case scenario is highly optimistic.

Average Case

The average-case time complexity of a backtracking algorithm for solving Sudoku is challenging to define precisely, as it depends on factors such as the puzzle's structure, the number of pre-filled cells, and how effectively the algorithm prunes the search space.

Due to constraint propagation and early pruning of the search space, the algorithm doesn't need to explore every possible board configuration. A reasonable estimate for the average case is

$$O(K^{N^2})$$

• K is a constant less than N, reflecting that not all numbers are tested in every cell.

• N² is the total number of cells in the grid.

Benchmarking

To better understand the practical implications of this time complexity, I conducted empirical measurements by solving Sudoku puzzles of different sizes and recording the time taken.

The setup involves generating puzzles of varying sizes of 9×9, 16×16 and 25×25 using a puzzle generator and solving these puzzles using the algorithm mentioned above and timing each solve.

Results

The reason the iteration count is odd because the puzzle generator creates unsolvable puzzles which are omitted.

The algorithm took forever to solve a 25×25 puzzle. Hence, it is not mentioned in the data above.

Conclusion

In this exploration of the backtracking algorithm for solving Sudoku puzzles, we demonstrated how it fills cells one at a time, backtracking when necessary. While this method is effective for smaller grids, its time complexity of N^{N^2} makes it impractical for larger sizes. The empirical measurements show that smaller puzzles can be solved relatively quickly, whereas larger ones, such as 25×25 grids, present significant challenges.

The code used for the demo above can be found here.

Thank you!