**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,

Sudokuis 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:

**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.**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).**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.**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.**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.**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:

**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`

.**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

**Board size**: If board size is ๐. Then a sudoku board has ๐ยฒ cells.**Empty Cells**: In the worst case, the algorithm may need to fill all the cells, i.e., ๐ยฒ cells.**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.**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(๐).**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 size | Average solve time (in ms) | Iterations |

9ร9 | 1.04 | 9901 |

16ร16 | 554 | 8809 |

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!