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:
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 returnstrue
, 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!