37. Sudoku Solver

Problem Description

The goal of this problem is to develop a program that can solve a classic Sudoku puzzle. Sudoku is a number puzzle played on a 9x9 grid divided into 9 smaller 3x3 sub-grids (also known as blocks or boxes). The rules are simple but require some strategic thinking:

Each row of the grid must contain all digits from 1 to 9, with no repetition.
Each column must also contain all digits from 1 to 9, without repeating any numbers.
Similarly, each of the 9 sub-grids must contain all digits from 1 to 9.

The puzzle starts with some cells already filled with numbers, and the rest are left blank, indicated by a '.' character. The objective is to fill the empty cells with the correct digits.

Intuition

To solve the Sudoku puzzle, we can use a depth-first search (DFS) algorithm—a form of backtracking. Here's the intuition behind this approach:

Represent the Sudoku board as a 2D array where each empty cell is a decision point.
For each decision point (i.e., an empty cell), try all possible numbers from 1 to 9, subject to the Sudoku rules.
Before placing a number in an empty cell, check if it's a valid choice:
- It must not already be present in the same row.
- It must not already be present in the same column.
- It must not already be present in the 3x3 sub-grid containing the cell.
If a number is valid, place it in the cell and move on to the next empty cell.
If at any point, a number cannot be placed in an empty cell (because all options have been exhausted and none are valid), backtrack to the previous cell and try a different number.
Continue this process until all cells are filled (sudoku solved), or you find that the puzzle is unsolvable with the current configuration (in which case, backtrack further).

The recursive DFS algorithm keeps track of which numbers are placed in which rows, columns, and blocks. This tracking allows the algorithm to quickly determine if a number can be placed in a cell. As soon as the solution is found, it's returned without further processing by setting a global flag, allowing the recursive calls to terminate quickly.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The solution uses Depth-First Search (DFS) with backtracking. Here's a breakdown of the implementation:

We define three lists to keep track of the numbers already used in each row, column, and block:
- row[9][9]: Each element corresponds to a row and a digit, set to True if that digit is already used in the row.
- col[9][9]: Similar to row, but tracks the columns.
- block[3][3][9]: Each element corresponds to one of the nine blocks and a digit, where each block is a 3x3 grid.
A list t is used to store the indices (i, j) of all empty cells, which the algorithm will attempt to fill in.
A variable ok is used as a flag to indicate whether the solution is found. Initially, it's set to False.
Initialize the row, col, and block lists based on the existing digits on the board. If a cell contains a number, it updates the corresponding row, col, and block entries to True.
The dfs function is the core of the backtracking algorithm:
- The base case is when the input index k is equal to the number of empty cells, meaning all cells have been successfully filled, and we set ok = True.
- It iterates over all possible values v from 0 to 8 (which corresponds to the digits 1 to 9 on the board) for each empty cell.
- It then checks if the value v has not been used in the row[i], col[j], and block[i // 3][j // 3]. If it hasn't, this value is placed in the cell, and the corresponding trackers are updated to True.
- Recursively calls dfs(k + 1) to proceed to the next cell.
- If placement of v leads to an invalid configuration later, it backtracks by resetting the trackers to False, which effectively removes the digit from the cell and tries the next digit.
- If at any point ok becomes True, indicating all cells are filled correctly, the function returns immediately, so the recursion unwinds and the filled board is preserved.
To start the process, dfs(0) is called after initializing the trackers, which begins the search for the solution using the first empty cell.
Since we maintain a global tracker of rows, columns, and blocks, we ensure that the space complexity is kept to O(1) since the auxiliary space does not grow with the size of the input.

The solution modifies the input board in-place to represent the filled Sudoku board after the solveSudoku function completes execution. At the core, this approach is an efficient use of DFS and backtracking, which systematically explores the feasible solutions and backtracks as soon as a partial solution is determined to be invalid.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider a simplified 4x4 Sudoku puzzle with a single empty cell for ease of demonstration:

1---------------------
2| 1 | 2 | 3 | 4 |
3---------------------
4| 3 | 4 | 1 | 2 |
5---------------------
6| 2 | 1 | 4 |   |
7---------------------
8| 4 | 3 | 2 | 1 |
9---------------------

In the above grid, the missing digit is in the third row and fourth column. According to our problem description, we have to fill this cell so that numbers 1 through 4 appear exactly once in each row, column, and 2x2 sub-grid.

Step by step, the backtracking algorithm would work as follows:

We represent our current state with the row, col, and block trackers. It would look something like this (simplified for the 4x4 grid):

1row = [
2  [True, True, True, True],
3  ...
4]
5
6col = [
7  [True, True, True, True],
8  ...
9]
10
11block = [
12  [[True, True, True, True], [True, True, True, True]],
13  ...
14]

And the list t of empty cells would hold just the index of the empty cell: [(2, 3)].

Next, we proceed with the depth-first search:

The DFS function is called with k = 0, as we have only one empty cell.
Now, the DFS algorithm will try to fill this cell with a valid number. Starting from value v = 0 (representing digit '1'), it will check if that number has already been used in the same row, column, and block.

For v = 0, we find that '1' is already present in the row and column, and so is '2' for v = 1, and '4' for v = 3. However, when v = 2, it represents the number '3', which satisfies our Sudoku rules:
- '3' is not present in the same row (which already has '2', '1', '4').
- '3' is not present in the same column (which already has '4', '1', '2').
- '3' is not present in the same block.
Seeing that it's a valid number to place, the DFS function will place '3' into the grid and update the row, col, and block trackers for '3' in the corresponding indices.
With the value placed, the DFS algorithm checks if it has reached the base case (k equal to the number of elements in t), which it has, and it then sets the ok flag to True.

The newly filled grid would look like this:

1---------------------
2| 1 | 2 | 3 | 4 |
3---------------------
4| 3 | 4 | 1 | 2 |
5---------------------
6| 2 | 1 | 4 | 3 |
7---------------------
8| 4 | 3 | 2 | 1 |
9---------------------

There is now a valid number in each row, column, and block. The ok flag being True will signal the end of the DFS call, and the backtracking will unwind having successfully filled in the puzzle.

Solution Implementation

1class Solution:
2    def solveSudoku(self, board: List[List[str]]) -> None:
3        """
4        This function solves a Sudoku puzzle using Depth First Search (DFS).
5        The given board is modified in-place to fill in the Sudoku solution.
6        """
7
8        def dfs(position: int):
9            # Base case: if all empty positions are filled, set completion flag to True
10            if position == len(empty_positions):
11                self.is_solved = True
12                return
13          
14            # Get the next position from the list of empty positions
15            row_index, col_index = empty_positions[position]
16
17            # Try placing all possible values (1-9) in the current empty cell
18            for value in range(9):
19                if (not rows_used[row_index][value] and 
20                        not cols_used[col_index][value] and 
21                        not blocks_used[row_index // 3][col_index // 3][value]):
22                  
23                    # Mark the value as used in the row, column, and 3x3 block
24                    rows_used[row_index][value] = cols_used[col_index][value] = blocks_used[row_index // 3][col_index // 3][value] = True
25                    board[row_index][col_index] = str(value + 1)
26
27                    # Recursively try to solve the rest of the puzzle
28                    dfs(position + 1)
29
30                    # Undo the move if it didn't lead to a solution
31                    rows_used[row_index][value] = cols_used[col_index][value] = blocks_used[row_index // 3][col_index // 3][value] = False
32
33                # If puzzle is solved, exit early
34                if self.is_solved:
35                    return
36
37        # Initialize tracking for used numbers in each row, column and block
38        rows_used = [[False] * 9 for _ in range(9)]
39        cols_used = [[False] * 9 for _ in range(9)]
40        blocks_used = [[[False] * 9 for _a in range(3)] for _b in range(3)]
41
42        empty_positions = []  # List to track the positions of empty cells
43        self.is_solved = False  # Flag to indicate when the puzzle is solved
44
45        # Process the Sudoku board to fill tracking structures and find empty cells
46        for row in range(9):
47            for col in range(9):
48                if board[row][col] == '.':
49                    # Save the position of the empty cell
50                    empty_positions.append((row, col))
51                else:
52                    # Mark the value as used in the row, column, and block
53                    value = int(board[row][col]) - 1
54                    rows_used[row][value] = cols_used[col][value] = blocks_used[row // 3][col // 3][value] = True
55
56        # Start the recursive DFS to solve the Sudoku
57        dfs(0)
58

1class Solution {
2    private boolean solved; // Variable to determine if the puzzle is solved
3    private char[][] board; // The Sudoku board
4    // List for tracking empty cells (those with '.')
5    private List<Integer> emptyCells = new ArrayList<>();
6    // Arrays to track the used numbers in rows, columns, and blocks
7    private boolean[][] usedInRow = new boolean[9][9];
8    private boolean[][] usedInColumn = new boolean[9][9];
9    private boolean[][][] usedInBlock = new boolean[3][3][9];
10
11    public void solveSudoku(char[][] board) {
12        this.board = board;
13        // Initialize the tracking structures and find the empty positions
14        for (int i = 0; i < 9; ++i) {
15            for (int j = 0; j < 9; ++j) {
16                if (board[i][j] == '.') {
17                    emptyCells.add(i * 9 + j); // Record the position of an empty cell
18                } else {
19                    // Convert char to int value ranging from 0-8
20                    int value = board[i][j] - '1';
21                    // Mark the value as used in the corresponding row, column, and block
22                    usedInRow[i][value] = true;
23                    usedInColumn[j][value] = true;
24                    usedInBlock[i / 3][j / 3][value] = true;
25                }
26            }
27        }
28        // Begin the recursive depth-first search to solve the puzzle
29        dfs(0);
30    }
31
32    private void dfs(int index) {
33        // If we have filled all empty cells, we have solved the puzzle
34        if (index == emptyCells.size()) {
35            solved = true;
36            return;
37        }
38        // Calculate the row and column from the current empty cell's index
39        int i = emptyCells.get(index) / 9;
40        int j = emptyCells.get(index) % 9;
41
42        // Try placing values 1-9 in the current empty cell
43        for (int value = 0; value < 9; ++value) {
44            if (!usedInRow[i][value] && !usedInColumn[j][value] && !usedInBlock[i / 3][j / 3][value]) {
45                // If the value isn't used in the row, column, or block, place it
46                usedInRow[i][value] = true;
47                usedInColumn[j][value] = true;
48                usedInBlock[i / 3][j / 3][value] = true;
49                board[i][j] = (char) (value + '1');
50                // Continue to the next empty cell
51                dfs(index + 1);
52                // If the puzzle is solved, exit
53                if (solved) {
54                    return;
55                }
56                // If placing value did not lead to a solution, backtrack
57                usedInRow[i][value] = false;
58                usedInColumn[j][value] = false;
59                usedInBlock[i / 3][j / 3][value] = false;
60            }
61        }
62    }
63}
64

1#include <vector>
2#include <functional>
3using std::vector;
4using std::pair;
5using std::function;
6
7class Solution {
8public:
9    void solveSudoku(vector<vector<char>>& board) {
10        // Initialize the checks for rows, columns, and blocks
11        bool rowCheck[9][9] = {false};
12        bool colCheck[9][9] = {false};
13        bool blockCheck[3][3][9] = {false};
14        bool isSolved = false; // Flag to indicate if the solution is found
15      
16        // Stores empty positions (represented as '.') in the board
17        vector<pair<int, int>> emptyPositions;
18      
19        // Build the initial state for empty positions and the values present
20        for (int i = 0; i < 9; ++i) {
21            for (int j = 0; j < 9; ++j) {
22                if (board[i][j] == '.') {
23                    // Keep track of empty positions for backtracking
24                    emptyPositions.push_back({i, j});
25                } else {
26                    // Calculate the value present in the cell
27                    int value = board[i][j] - '1';
28                    // Mark the value present in the corresponding row, column, and block
29                    rowCheck[i][value] = colCheck[j][value] = blockCheck[i / 3][j / 3][value] = true;
30                }
31            }
32        }
33      
34        // Define the DFS function for backtracking
35        function<void(int)> dfs = [&](int index) {
36            // Base case: if all empty positions are filled
37            if (index == emptyPositions.size()) {
38                isSolved = true; // Solution found
39                return;
40            }
41          
42            // Get the position to fill
43            int row = emptyPositions[index].first;
44            int col = emptyPositions[index].second;
45          
46            // Try all possible values in the current position
47            for (int value = 0; value < 9; ++value) {
48                // Check if the value is not already present in the row, column, or block
49                if (!rowCheck[row][value] && !colCheck[col][value] && !blockCheck[row / 3][col / 3][value]) {
50                    // Place the value and update the state
51                    rowCheck[row][value] = colCheck[col][value] = blockCheck[row / 3][col / 3][value] = true;
52                    board[row][col] = value + '1';
53                  
54                    // Continue with the next position
55                    dfs(index + 1);
56                  
57                    // If solution is found, no need to explore further
58                    if (isSolved) {
59                        return;
60                    }
61                  
62                    // Undo the decision and backtrack
63                    rowCheck[row][value] = colCheck[col][value] = blockCheck[row / 3][col / 3][value] = false;
64                }
65            }
66        };
67      
68        // Start the DFS from the first empty position
69        dfs(0);
70    }
71};
72

1// Here we're importing arrays from TypeScript, which will be our board
2import { Array } from "typescript";
3
4// Definition of the solveSudoku function
5function solveSudoku(board: char[][]): void {
6    // Initialize the checks for rows, columns, and blocks
7    const rowCheck: boolean[][] = Array(9).fill(false).map(() => Array(9).fill(false));
8    const colCheck: boolean[][] = Array(9).fill(false).map(() => Array(9).fill(false));
9    const blockCheck: boolean[][][] = Array(3).fill(false).map(() => Array(3).fill(false).map(() => Array(9).fill(false)));
10    let isSolved: boolean = false; // Flag to indicate if the solution is found
11  
12    // Stores empty positions (represented as '.') in the board
13    const emptyPositions: { row: number, col: number }[] = [];
14  
15    // Build the initial state for empty positions and the values present
16    board.forEach((row, i) => {
17        row.forEach((cell, j) => {
18            if (cell === '.') {
19                // Keep track of empty positions for backtracking
20                emptyPositions.push({ row: i, col: j });
21            } else {
22                // Calculate the value present in the cell
23                const value: number = parseInt(cell) - 1;
24                // Mark the value present in the corresponding row, column, and block
25                rowCheck[i][value] = colCheck[j][value] = blockCheck[Math.floor(i / 3)][Math.floor(j / 3)][value] = true;
26            }
27        });
28    });
29  
30    // Define the DFS function for backtracking
31    const dfs = (index: number): void => {
32        // Base case: if all the empty positions are filled, the puzzle is solved
33        if (index === emptyPositions.length) {
34            isSolved = true; // Solution found
35            return;
36        }
37      
38        // Get the position to fill
39        const pos = emptyPositions[index];
40        const row = pos.row;
41        const col = pos.col;
42      
43        // Try all possible values for the current position
44        for (let value = 0; value < 9; ++value) {
45            // Check if the value is not already present in the row, column, or block
46            if (!rowCheck[row][value] && !colCheck[col][value] && !blockCheck[Math.floor(row / 3)][Math.floor(col / 3)][value]) {
47                // Place the value and update the state
48                rowCheck[row][value] = colCheck[col][value] = blockCheck[Math.floor(row / 3)][Math.floor(col / 3)][value] = true;
49                board[row][col] = (value + 1).toString();
50              
51                // Continue with the next position
52                dfs(index + 1);
53              
54                // If a solution has been found, we don't need to proceed further
55                if (isSolved) {
56                    return;
57                }
58              
59                // Undo the decision and backtrack
60                rowCheck[row][value] = colCheck[col][value] = blockCheck[Math.floor(row / 3)][Math.floor(col / 3)][value] = false;
61            }
62        }
63    };
64  
65    // Start the DFS from the first empty position
66    dfs(0);
67}
68
69// The type for the Sudoku board (assuming 9x9)
70type char = string;
71

Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Time and Space Complexity

Time Complexity

The given algorithm solves a Sudoku puzzle using Depth-First Search (DFS). For each empty cell, the algorithm tries out all possible numbers (1-9), and for each number, it checks whether placing it violates any Sudoku rules. If the placement is not violating the Sudoku rules, the algorithm proceeds to place the number and move onto the next empty cell.

The worst-case time complexity is difficult to determine precisely due to the nature of the problem, but a brute-force approach has an upper bound of O(9^m), where m is the number of empty spaces in the Sudoku puzzle. However, this bound is a vast overestimation, as the early pruning greatly reduces the search space. The actual time complexity is much lower, but an accurate analysis depends on the initial configuration of the Sudoku board.

Space Complexity

The space complexity of the algorithm includes the storage for the board, the hash-check arrays (row, col, block), and the call stack for recursion.

The board itself will occupy O(9 * 9), which is constant O(1).
The row, col, and block arrays have a space complexity of O(3 * 9 * 9) since we store boolean values representing whether a certain number is already used in the corresponding row, column, and block. This also simplifies to O(1) in the context of Sudoku, since these sizes do not scale with any variable input but are constants.

The majority of the space complexity comes from the depth of the recursion stack, which in the worst case can be as many as m function calls deep, where m is the number of empty spaces. Thus, the space complexity due to recursion is O(m).

Combining these, the total space complexity is the maximum of these two, resulting in O(m).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

37. Sudoku Solver

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings