Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sudoku Solver

HARDProblemSolveExternal Links

Description

Write a program to solve a Sudoku puzzle by filling in all the empty cells.

A valid Sudoku solution must satisfy three rules simultaneously:

  1. Row Rule: Each digit from 1 to 9 must appear exactly once in every row.
  2. Column Rule: Each digit from 1 to 9 must appear exactly once in every column.
  3. Box Rule: Each digit from 1 to 9 must appear exactly once in each of the nine 3×3 sub-boxes of the grid.

The board is a 9×9 grid where each cell contains either a digit character ('1' to '9') or a '.' representing an empty cell that needs to be filled. The puzzle is guaranteed to have exactly one valid solution. The board should be modified in-place.

Examples

Example 1

Input:

board =
[["5","3",".",".","7",".",".",".","."],
 ["6",".",".","1","9","5",".",".","."],
 [".","9","8",".",".",".",".","6","."],
 ["8",".",".",".","6",".",".",".","3"],
 ["4",".",".","8",".","3",".",".","1"],
 ["7",".",".",".","2",".",".",".","6"],
 [".","6",".",".",".",".","2","8","."],
 [".",".",".","4","1","9",".",".","5"],
 [".",".",".",".","8",".",".","7","9"]]

Output:

[["5","3","4","6","7","8","9","1","2"],
 ["6","7","2","1","9","5","3","4","8"],
 ["1","9","8","3","4","2","5","6","7"],
 ["8","5","9","7","6","1","4","2","3"],
 ["4","2","6","8","5","3","7","9","1"],
 ["7","1","3","9","2","4","8","5","6"],
 ["9","6","1","5","3","7","2","8","4"],
 ["2","8","7","4","1","9","6","3","5"],
 ["3","4","5","2","8","6","1","7","9"]]

Explanation: Every row, column, and 3×3 sub-box in the solved board contains exactly the digits 1 through 9 with no repetition. The 51 empty cells marked with '.' have been filled with the unique valid digits.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit '1'-'9' or '.'
  • It is guaranteed that the input board has exactly one solution

Editorial

Brute Force

Intuition

Think about how you solve a Sudoku puzzle by hand. You find an empty cell, consider which digits are allowed there, try one, and move on to the next empty cell. If you eventually reach a cell where no digit is possible, you erase your last choice and try a different digit. This trial-and-error process is called backtracking.

The simplest implementation uses backtracking with naive validation: every time we want to place a digit in a cell, we scan the entire row (9 cells), the entire column (9 cells), and the entire 3×3 sub-box (9 cells) to check whether that digit already exists. If the digit is not found in any of these 27 cells, the placement is valid.

This approach is correct but slow on the validation step — we perform up to 27 cell comparisons every single time we test a digit. Since we may try up to 9 digits per empty cell and there can be up to 81 empty cells with deep backtracking, these 27-check validations add up quickly.

9x9 Sudoku grid divided into 9 sub-boxes, with row, column, and box constraints highlighted
9x9 Sudoku grid divided into 9 sub-boxes, with row, column, and box constraints highlighted

Step-by-Step Explanation

Let's trace the backtracking process on the example board. We collect all empty cells and process them in row-major order.

Step 1: Scan the board. Collect 51 empty cells. First empty cell is (0,2).

Step 2: At cell (0,2), scan row 0 to find existing digits: {5, 3, 7}. Scan column 2: {8}. Scan box(0,0) (rows 0-2, cols 0-2): {5, 3, 6, 9, 8}. Available digits: {1, 2, 4}. Try digit 1.

Step 3: Place 1 at (0,2). Move to (0,3). Scan row 0: {5, 3, 1, 7}. Scan col 3: {1, 8, 4}. Scan box(0,1): {7, 1, 9, 5}. Available: {2, 6}. Try 2.

Step 4: Place 2 at (0,3). Continue forward. Place 4 at (0,5), 8 at (0,6), 9 at (0,7). Board row 0 is now: [5, 3, 1, 2, 7, 4, 8, 9, _].

Step 5: At cell (0,8), the only missing digit for row 0 is 6. Scan column 8: {3, 1, 6, 5, 9}. Digit 6 is already in column 8! Try all other digits — none are valid. Dead end!

Step 6: Backtrack. Undo cell (0,7), then (0,6). At (0,6), the next candidate after 8 is 9. Place 9 at (0,6). But now at (0,7), the remaining digits for the row are {6, 8}, and both are present in column 7 ({6, 8, 7}). Dead end again.

Step 7: Backtrack further, undoing all the way to (0,5). The next candidate after 4 is 6. Place 6 at (0,5). Continue: place 4 at (0,6), 9 at (0,7), 8 at (0,8). But this eventually leads to deeper conflicts in rows 1-2.

Step 8: After many rounds of backtracking, the algorithm discovers that digit 1 at (0,2) was the root cause. Undo back to (0,2). Try digit 2 — also leads to failure. Try digit 4.

Step 9: With 4 at (0,2), the correct path opens up: (0,3)=6, (0,5)=8, (0,6)=9, (0,7)=1, (0,8)=2. Row 0 is correctly filled: [5, 3, 4, 6, 7, 8, 9, 1, 2].

Step 10: The algorithm continues to row 1 and fills subsequent empty cells. Eventually all 51 cells are filled and the puzzle is solved.

Backtracking with Scanning — Wrong Path, Dead End, Recovery — Watch how the solver tries digit 1 at cell (0,2), fills forward, hits a dead end at (0,8), backtracks, and eventually finds the correct digit 4.

Algorithm

  1. Collect all empty cells (cells containing '.') into a list.
  2. Define a recursive function solve(k) that processes the k-th empty cell:
    a. Base case: If k equals the number of empty cells, all cells are filled — the puzzle is solved.
    b. Let (row, col) be the position of the k-th empty cell.
    c. For each digit d from 1 to 9:
    • Validate by scanning all 9 cells in the row, all 9 cells in the column, and all 9 cells in the 3×3 box. If d appears in any of them, skip d.
    • Place d on the board at (row, col).
    • Recursively call solve(k + 1).
    • If the recursion solves the puzzle, return immediately.
    • Otherwise, backtrack: remove d from (row, col) and try the next digit.
  3. Call solve(0) to begin.

Code

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<pair<int,int>> emptyCells;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.')
                    emptyCells.push_back({i, j});
        solve(board, emptyCells, 0);
    }

private:
    bool isValid(vector<vector<char>>& board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == ch) return false;  // check row
            if (board[i][col] == ch) return false;  // check column
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == ch) return false;  // check box
        }
        return true;
    }

    bool solve(vector<vector<char>>& board, vector<pair<int,int>>& cells, int k) {
        if (k == cells.size()) return true;
        auto [row, col] = cells[k];
        for (char ch = '1'; ch <= '9'; ch++) {
            if (isValid(board, row, col, ch)) {
                board[row][col] = ch;
                if (solve(board, cells, k + 1)) return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
};
class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        empty_cells = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty_cells.append((i, j))

        def is_valid(row, col, ch):
            for i in range(9):
                if board[row][i] == ch:  # check row
                    return False
                if board[i][col] == ch:  # check column
                    return False
                box_row = 3 * (row // 3) + i // 3
                box_col = 3 * (col // 3) + i % 3
                if board[box_row][box_col] == ch:  # check box
                    return False
            return True

        def solve(k):
            if k == len(empty_cells):
                return True
            row, col = empty_cells[k]
            for d in range(1, 10):
                ch = str(d)
                if is_valid(row, col, ch):
                    board[row][col] = ch
                    if solve(k + 1):
                        return True
                    board[row][col] = '.'
            return False

        solve(0)
class Solution {
    public void solveSudoku(char[][] board) {
        List<int[]> emptyCells = new ArrayList<>();
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.')
                    emptyCells.add(new int[]{i, j});
        solve(board, emptyCells, 0);
    }

    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == ch) return false;
            if (board[i][col] == ch) return false;
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == ch) return false;
        }
        return true;
    }

    private boolean solve(char[][] board, List<int[]> cells, int k) {
        if (k == cells.size()) return true;
        int row = cells.get(k)[0], col = cells.get(k)[1];
        for (char ch = '1'; ch <= '9'; ch++) {
            if (isValid(board, row, col, ch)) {
                board[row][col] = ch;
                if (solve(board, cells, k + 1)) return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(9^m × 27) where m is the number of empty cells

In the worst case, for each of the m empty cells, we try all 9 possible digits. Each digit requires a validity check that scans 9 cells in the row, 9 in the column, and 9 in the box — totaling 27 comparisons per check. With up to 9 digits per cell and recursive branching, the worst case is O(9^m) paths, each involving O(27) validation work. For a nearly empty board (m ≈ 81), this is astronomically large, though pruning from constraint violations cuts the practical runtime significantly.

Space Complexity: O(m)

The recursion stack depth equals the number of empty cells m (at most 81). The list storing empty cell coordinates takes O(m) space. No additional data structures are used beyond the board itself.

Why This Approach Is Not Efficient

The fundamental bottleneck in the brute force approach is the validation step. Every time we want to test whether a digit is safe to place, we scan 27 cells — 9 in the row, 9 in the column, and 9 in the 3×3 sub-box. This scanning is done for every digit we try, at every empty cell, and it repeats after every backtrack.

Consider: with 51 empty cells in the example, and up to 9 digits tried per cell, that's up to 51 × 9 × 27 = 12,393 cell scans just in a single forward pass without any backtracking. With backtracking, the same cells get validated over and over, multiplying this cost dramatically.

The key insight is that we are re-discovering the same information every time. When we scan row 0 to check if digit 4 exists, we get the answer. But the next time we want to check a digit in row 0, we scan all 9 cells again — even though the row barely changed (at most one new digit was added or removed).

What if we could answer the question "is digit d already in row i?" in O(1) time instead of O(9)? If we precompute and maintain three boolean arrays — one for rows, one for columns, one for boxes — tracking which digits are present, each validation becomes just three O(1) lookups instead of 27 cell scans. This eliminates the entire scanning overhead.

Optimal Approach - Backtracking with Constraint Tracking

Intuition

The core algorithm remains backtracking — there is no way to avoid trying different digit combinations when the puzzle has multiple possibilities at a cell. However, we can make each step of the backtracking dramatically faster by maintaining precomputed constraint information.

Imagine three ledger books:

  • Row Ledger: For each of the 9 rows, a checklist of which digits (1-9) are already used.
  • Column Ledger: For each of the 9 columns, the same checklist.
  • Box Ledger: For each of the 9 sub-boxes, the same checklist.

Before we start solving, we scan the board once and fill in these ledgers for all pre-given digits. Now, to check whether placing digit d at cell (i, j) is valid, we just look at three checklist entries:

  1. Is d marked in row i's ledger? → row_used[i][d]
  2. Is d marked in column j's ledger? → col_used[j][d]
  3. Is d marked in the box containing (i, j)? → box_used[i/3][j/3][d]

If all three answer "no", the placement is valid. This is three constant-time lookups instead of scanning 27 cells.

When we place a digit, we mark it in all three ledgers. When we backtrack (remove a digit), we unmark it. This bookkeeping is O(1) per operation.

Step-by-Step Explanation

Let's trace the optimized approach on the same example:

Step 1: Initialize three boolean arrays: row_used[9][9], col_used[9][9], box_used[3][3][9]. Scan the board and mark all pre-given digits. For example, board[0][0]='5' → mark row_used[0][5]=true, col_used[0][5]=true, box_used[0][0][5]=true. Collect 51 empty cells.

Step 2: At cell (0,2), check digit 4: row_used[0][4]=false, col_used[2][4]=false, box_used[0][0][4]=false. All false → valid! Place 4. Mark row_used[0][4]=true, col_used[2][4]=true, box_used[0][0][4]=true. Three O(1) lookups + three O(1) updates.

Step 3: At cell (0,3), check digit 6: row_used[0][6]=false, col_used[3][6]=false, box_used[0][1][6]=false. Valid! Place 6.

Step 4: At cell (0,5), check digit 8: all three arrays say false. Valid! Place 8.

Step 5: Continue: (0,6)=9, (0,7)=1, (0,8)=2. Each validation is just three boolean lookups. Row 0 is complete: [5,3,4,6,7,8,9,1,2].

Step 6: Move to row 1. At (1,1), check digit 7: row_used[1][7]=false, col_used[1][7]=false, box_used[0][0][7]=false. Valid! Place 7.

Step 7: At (1,2), check digit 2: valid. Place 2. Continue filling: (1,6)=3, (1,7)=4, (1,8)=8. Row 1 complete: [6,7,2,1,9,5,3,4,8].

Step 8: Continue through all remaining rows. Each validation requires exactly 3 constant-time lookups. When backtracking is needed (wrong guess at a deeper cell), the unmark operations are also O(1) each.

Step 9: All 51 empty cells filled. The board is solved.

Optimized Backtracking — O(1) Constraint Lookups — Watch how the optimized solver uses precomputed boolean arrays for instant validation, filling cells efficiently without scanning 27 cells each time.

Algorithm

  1. Create three boolean arrays:
    • row_used[9][9] — row_used[i][d] is true if digit d+1 is in row i
    • col_used[9][9] — col_used[j][d] is true if digit d+1 is in column j
    • box_used[3][3][9] — box_used[i/3][j/3][d] is true if digit d+1 is in that sub-box
  2. Initialize: Scan the entire board once. For each pre-filled cell with digit d at position (i, j), set row_used[i][d-1], col_used[j][d-1], and box_used[i/3][j/3][d-1] to true. Collect all empty cells into a list.
  3. Define recursive function solve(k):
    a. Base case: If k equals the number of empty cells, return true (solved).
    b. Let (row, col) = k-th empty cell.
    c. For each digit index d from 0 to 8 (representing digits 1-9):
    • If row_used[row][d] OR col_used[col][d] OR box_used[row/3][col/3][d] is true, skip (digit already used).
    • Otherwise: mark digit as used in all three arrays, place digit on board, and recurse with solve(k+1).
    • If recursion returns true, propagate true (solution found).
    • Otherwise: backtrack — unmark digit in all three arrays.
  4. Call solve(0).

Code

class Solution {
public:
    bool rowUsed[9][9] = {};
    bool colUsed[9][9] = {};
    bool boxUsed[3][3][9] = {};
    vector<pair<int,int>> emptyCells;
    bool solved = false;

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    emptyCells.push_back({i, j});
                } else {
                    int d = board[i][j] - '1';
                    rowUsed[i][d] = colUsed[j][d] = boxUsed[i/3][j/3][d] = true;
                }
            }
        }
        solve(board, 0);
    }

    void solve(vector<vector<char>>& board, int k) {
        if (k == emptyCells.size()) {
            solved = true;
            return;
        }
        auto [row, col] = emptyCells[k];
        for (int d = 0; d < 9 && !solved; d++) {
            if (!rowUsed[row][d] && !colUsed[col][d] && !boxUsed[row/3][col/3][d]) {
                rowUsed[row][d] = colUsed[col][d] = boxUsed[row/3][col/3][d] = true;
                board[row][col] = '1' + d;
                solve(board, k + 1);
                if (!solved) {
                    rowUsed[row][d] = colUsed[col][d] = boxUsed[row/3][col/3][d] = false;
                }
            }
        }
    }
};
class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        row_used = [[False] * 9 for _ in range(9)]
        col_used = [[False] * 9 for _ in range(9)]
        box_used = [[[False] * 9 for _ in range(3)] for _ in range(3)]
        empty_cells = []

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty_cells.append((i, j))
                else:
                    d = int(board[i][j]) - 1
                    row_used[i][d] = True
                    col_used[j][d] = True
                    box_used[i // 3][j // 3][d] = True

        def solve(k):
            if k == len(empty_cells):
                return True
            row, col = empty_cells[k]
            for d in range(9):
                if not row_used[row][d] and not col_used[col][d] and not box_used[row // 3][col // 3][d]:
                    row_used[row][d] = True
                    col_used[col][d] = True
                    box_used[row // 3][col // 3][d] = True
                    board[row][col] = str(d + 1)
                    if solve(k + 1):
                        return True
                    row_used[row][d] = False
                    col_used[col][d] = False
                    box_used[row // 3][col // 3][d] = False
            return False

        solve(0)
class Solution {
    private boolean[][] rowUsed = new boolean[9][9];
    private boolean[][] colUsed = new boolean[9][9];
    private boolean[][][] boxUsed = new boolean[3][3][9];
    private List<int[]> emptyCells = new ArrayList<>();
    private boolean solved = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    emptyCells.add(new int[]{i, j});
                } else {
                    int d = board[i][j] - '1';
                    rowUsed[i][d] = true;
                    colUsed[j][d] = true;
                    boxUsed[i / 3][j / 3][d] = true;
                }
            }
        }
        solve(board, 0);
    }

    private void solve(char[][] board, int k) {
        if (k == emptyCells.size()) {
            solved = true;
            return;
        }
        int row = emptyCells.get(k)[0];
        int col = emptyCells.get(k)[1];
        for (int d = 0; d < 9 && !solved; d++) {
            if (!rowUsed[row][d] && !colUsed[col][d] && !boxUsed[row / 3][col / 3][d]) {
                rowUsed[row][d] = true;
                colUsed[col][d] = true;
                boxUsed[row / 3][col / 3][d] = true;
                board[row][col] = (char) ('1' + d);
                solve(board, k + 1);
                if (!solved) {
                    rowUsed[row][d] = false;
                    colUsed[col][d] = false;
                    boxUsed[row / 3][col / 3][d] = false;
                }
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(9^m) where m is the number of empty cells

The theoretical worst case is still O(9^m) because we may need to try all 9 digits at each of the m empty cells in the worst backtracking scenario. However, each digit validation is now O(1) — just three boolean array lookups instead of scanning 27 cells. This makes the constant factor approximately 9× smaller per validation compared to the brute force approach. In practice, constraint propagation from the boolean arrays prunes invalid branches extremely quickly, and most well-formed Sudoku puzzles are solved with very little backtracking.

Space Complexity: O(1) (since the board size is fixed)

The three boolean arrays use row_used: 9×9 = 81 booleans, col_used: 9×9 = 81 booleans, box_used: 3×3×9 = 81 booleans. Total: 243 booleans. The empty cell list is at most 81 entries. The recursion stack is at most 81 frames deep. All of these are bounded by constants (the board is always 9×9), so the auxiliary space is O(1) in terms of input size.