Solving ๐‘ ร— ๐‘ Sudoku with Backtracking

Solving ๐‘ ร— ๐‘ Sudoku with Backtracking

ยท

7 min read

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

Board sizeAverage solve time (in ms)Iterations
9ร—91.049901
16ร—165548809

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!

ย