# Sudoku Solver
**Difficulty:** HARD
[External](https://leetcode.com/problems/sudoku-solver)
Canonical: https://scaleengineer.com/dsa/problems/sudoku-solver
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cadence](https://scaleengineer.com/companies/cadence), [DoorDash](https://scaleengineer.com/companies/doordash), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Confluent](https://scaleengineer.com/companies/confluent), [Pinterest](https://scaleengineer.com/companies/pinterest), [Riot Games](https://scaleengineer.com/companies/riot-games), [LINE](https://scaleengineer.com/companies/line)
---
## Problem
Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy **all of the following rules**:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

The `'.'` character indicates empty cells.

**Example 1:**

![](https://assets.glich.co/dsa/sudoku-solver/image0.png) 

**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:** The input board is shown above and the only valid solution is shown below:

![](https://assets.glich.co/dsa/sudoku-solver/image1.png)

**Constraints:**

* `board.length == 9`
* `board[i].length == 9`
* `board[i][j]` is a digit or `'.'`.
* It is **guaranteed** that the input board has only one solution.

# Approaches
## Simple Backtracking
This approach uses a standard recursive backtracking algorithm. It iterates through the grid to find an empty cell, then tries to place each digit from 1 to 9 in that cell. For each attempt, it checks if the placement is valid according to Sudoku rules. If it is, it proceeds recursively. If a path leads to a dead end, it backtracks and tries the next digit.
**Time:** O(9^m), where 'm' is the number of empty cells. In the worst case, we have to explore all possible number combinations for the empty cells. · **Space:** O(m) or O(81) for the recursion stack depth. Since the board size is fixed, this can be considered O(1).
**Pros:** Simple to understand and implement.; Guaranteed to find the solution for a valid puzzle.
**Cons:** Inefficient due to repeated validation checks.; Can be very slow for puzzles with a large number of empty cells.
### Explanation
This method employs a brute-force recursive strategy. The main `solve` function iterates through the grid. Upon finding an empty cell, it tries to fill it with a digit from 1 to 9. For each digit, it calls a helper function `isValid` to check if the move is legal. The `isValid` function performs three checks: whether the digit already exists in the current row, the current column, or the current 3x3 sub-grid. If the move is valid, the function calls itself recursively. If the recursion leads to a dead end (returns `false`), it backtracks by undoing the move and trying the next digit. This process continues until a full solution is found or all possibilities are exhausted.

```java
class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.'; // Backtrack
                            }
                        }
                    }
                    return false; // No valid number found for this cell
                }
            }
        }
        return true; // Board is solved
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check row
            if (board[row][i] == c) {
                return false;
            }
            // Check column
            if (board[i][col] == c) {
                return false;
            }
            // Check 3x3 box
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == c) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Define a recursive function, `solve()`, that attempts to solve the board.
*   Iterate through each cell of the board from `(0,0)` to `(8,8)`.
*   If a cell `(row, col)` is empty, loop through digits '1' to '9'.
*   For each digit, check its validity using a helper function `isValid()` which scans the current row, column, and 3x3 sub-grid.
*   If the digit is valid, place it and make a recursive call to `solve()`.
*   If the recursive call returns `true`, a solution is found, so return `true`.
*   If it returns `false`, backtrack by resetting the cell to '.' and try the next digit.
*   If all digits fail for a cell, return `false`.
*   If the entire board is scanned without finding empty cells, return `true`.

## Backtracking with Pre-computation
This approach improves upon the simple backtracking by optimizing the validation step. Instead of repeatedly scanning rows, columns, and boxes, it uses boolean arrays (or hash sets) to keep track of which numbers are already used in each row, column, and 3x3 sub-grid. This reduces the time to check for a valid placement from O(N) to O(1).
**Time:** O(9^m), where 'm' is the number of empty cells. While the theoretical worst-case is the same as the simple backtracking, the practical performance is significantly better due to O(1) validation checks. · **Space:** O(m) for the recursion stack plus O(1) for the boolean arrays (since their size is fixed: 9x10 x 3). Total space is O(m) or effectively O(1).
**Pros:** Much faster than simple backtracking.; O(1) time complexity for validating a number placement.
**Cons:** Still a brute-force search, which can be slow for the hardest puzzles.; Slightly more complex due to the management of auxiliary data structures.
### Explanation
This approach significantly optimizes the validation step of the simple backtracking algorithm. It maintains three 2D boolean arrays: `rows`, `cols`, and `boxes`. These arrays act as a cache to store which numbers are already present in each row, column, and 3x3 sub-grid. Before starting the backtracking process, these arrays are populated based on the initial numbers on the board. During backtracking, checking if a number can be placed in a cell becomes an O(1) operation by simply looking up the values in these three arrays. When a number is placed, the corresponding entries in the arrays are updated. If backtracking is needed, these entries are reverted.

```java
class Solution {
    private boolean[][] rows = new boolean[9][10];
    private boolean[][] cols = new boolean[9][10];
    private boolean[][] boxes = new boolean[9][10];
    private char[][] board;
    private boolean solved = false;

    public void solveSudoku(char[][] board) {
        this.board = board;
        // Pre-fill the boolean arrays
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    int boxIndex = (i / 3) * 3 + j / 3;
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[boxIndex][num] = true;
                }
            }
        }
        backtrack(0, 0);
    }

    private void backtrack(int row, int col) {
        if (row == 9) {
            solved = true;
            return;
        }

        int nextRow = (col == 8) ? row + 1 : row;
        int nextCol = (col == 8) ? 0 : col + 1;

        if (board[row][col] != '.') {
            backtrack(nextRow, nextCol);
        } else {
            int boxIndex = (row / 3) * 3 + col / 3;
            for (int num = 1; num <= 9; num++) {
                if (!rows[row][num] && !cols[col][num] && !boxes[boxIndex][num]) {
                    placeNumber(row, col, num);
                    backtrack(nextRow, nextCol);
                    if (!solved) {
                        removeNumber(row, col, num); // Backtrack
                    }
                }
            }
        }
    }

    private void placeNumber(int row, int col, int num) {
        int boxIndex = (row / 3) * 3 + col / 3;
        board[row][col] = (char) (num + '0');
        rows[row][num] = true;
        cols[col][num] = true;
        boxes[boxIndex][num] = true;
    }

    private void removeNumber(int row, int col, int num) {
        int boxIndex = (row / 3) * 3 + col / 3;
        board[row][col] = '.';
        rows[row][num] = false;
        cols[col][num] = false;
        boxes[boxIndex][num] = false;
    }
}
```
### Algorithm
*   Initialize boolean arrays `rows[9][10]`, `cols[9][10]`, and `boxes[9][10]`.
*   Scan the initial board to populate these arrays with used numbers.
*   Implement a recursive backtracking function `backtrack(row, col)`.
*   The function moves to the next cell `(nextRow, nextCol)` in each call.
*   If the current cell `(row, col)` is empty, loop through digits '1' to '9'.
*   Check validity in O(1) time using the boolean arrays.
*   If a digit is valid, place it, update the boolean arrays, and recurse with `backtrack(nextRow, nextCol)`.
*   If the recursion fails, backtrack by resetting the cell and the boolean arrays.
*   The base case for recursion is when `row == 9`, indicating the board is solved.

## Optimized Backtracking with Heuristics
This is the most efficient backtracking approach. It enhances the previous method by adding a heuristic for selecting which empty cell to fill next. Instead of processing cells in a fixed order (e.g., row-by-row), it scans all empty cells and chooses the one with the 'Minimum Remaining Values' (MRV). This means it picks the cell that has the fewest legal numbers that can be placed in it. This strategy helps to prune the search tree more aggressively by tackling the most constrained parts of the puzzle first, leading to earlier detection of dead ends.
**Time:** O(9^m), where 'm' is the number of empty cells. The heuristic does not change the worst-case theoretical complexity. However, in practice, it prunes the search space so effectively that it's one of the fastest algorithms for solving Sudoku puzzles. · **Space:** O(m) for the recursion stack, which is effectively O(1) for a fixed-size board. The space for the boolean arrays is also O(1).
**Pros:** Extremely fast in practice due to intelligent search space pruning.; Finds solutions for even very difficult puzzles quickly.
**Cons:** More complex to implement than simpler backtracking algorithms.; The overhead of finding the most constrained cell at each recursive step, while usually beneficial, adds complexity.
### Explanation
This advanced backtracking method incorporates a powerful heuristic to guide the search more intelligently. Instead of filling empty cells in a fixed order, at each step, it first identifies the most constrained cell—the one with the Minimum Remaining Values (MRV). To do this, it iterates through all empty cells and counts the number of valid candidate numbers for each. The cell with the fewest candidates is chosen to be filled next. This strategy prioritizes choices that are most likely to lead to a conflict, thereby pruning large portions of the search tree early. This makes the algorithm exceptionally fast in practice, even for very difficult Sudoku puzzles.

```java
class Solution {
    private boolean[][] rows = new boolean[9][10];
    private boolean[][] cols = new boolean[9][10];
    private boolean[][] boxes = new boolean[9][10];
    private char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    int boxIndex = (i / 3) * 3 + j / 3;
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[boxIndex][num] = true;
                }
            }
        }
        solve();
    }

    private boolean solve() {
        int bestRow = -1, bestCol = -1, minOptions = 10;

        // Find the most constrained empty cell (Minimum Remaining Values)
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    int options = 0;
                    int boxIndex = (r / 3) * 3 + c / 3;
                    for (int num = 1; num <= 9; num++) {
                        if (!rows[r][num] && !cols[c][num] && !boxes[boxIndex][num]) {
                            options++;
                        }
                    }
                    if (options < minOptions) {
                        minOptions = options;
                        bestRow = r;
                        bestCol = c;
                    }
                }
            }
        }

        // If no empty cells, puzzle is solved
        if (bestRow == -1) {
            return true;
        }

        // Try all valid numbers for the most constrained cell
        int r = bestRow;
        int c = bestCol;
        int boxIndex = (r / 3) * 3 + c / 3;
        for (int num = 1; num <= 9; num++) {
            if (!rows[r][num] && !cols[c][num] && !boxes[boxIndex][num]) {
                placeNumber(r, c, num);
                if (solve()) {
                    return true;
                }
                removeNumber(r, c, num); // Backtrack
            }
        }

        return false; // No solution found from this path
    }

    private void placeNumber(int row, int col, int num) {
        int boxIndex = (row / 3) * 3 + col / 3;
        board[row][col] = (char) (num + '0');
        rows[row][num] = true;
        cols[col][num] = true;
        boxes[boxIndex][num] = true;
    }

    private void removeNumber(int row, int col, int num) {
        int boxIndex = (row / 3) * 3 + col / 3;
        board[row][col] = '.';
        rows[row][num] = false;
        cols[col][num] = false;
        boxes[boxIndex][num] = false;
    }
}
```
### Algorithm
*   Set up boolean arrays `rows`, `cols`, `boxes` as in the previous approach.
*   Implement a recursive `solve()` function.
*   Inside `solve()`, first find the most constrained empty cell (the one with the Minimum Remaining Values or MRV). This involves scanning all empty cells and counting their valid placement options.
*   If no empty cells exist, the puzzle is solved; return `true`.
*   Let the most constrained cell be `(bestRow, bestCol)`.
*   Iterate through the valid digits for `(bestRow, bestCol)`.
*   For each valid digit, place it, update the boolean arrays, and call `solve()` recursively.
*   If the recursive call returns `true`, propagate `true`.
*   Otherwise, backtrack by resetting the cell and boolean arrays.
*   If all valid digits for the cell fail, return `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public void SolveSudoku(char[][] board) {
        this.board = new ushort ? [9, 9];
        for (var i = 0; i < 9; ++i) {
            for (var j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    this.board[i, j] = (ushort)(1 << (board[i][j] - '0' - 1));
                }
            }
        }
        if (SolveSudoku(0, 0)) {
            for (var i = 0; i < 9; ++i) {
                for (var j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        board[i][j] = '0';
                        while (this.board[i, j].Value != 0) {
                            board[i][j] = (char)(board[i][j] + 1);
                            this.board[i, j] >>= 1;
                        }
                    }
                }
            }
        }
    }
    private ushort ? [, ] board;
    private bool ValidateHorizontalRule(int row) {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i) {
            if (board[row, i].HasValue) {
                if ((temp | board[row, i].Value) == temp) {
                    return false;
                }
                temp |= board[row, i].Value;
            }
        }
        return true;
    }
    private bool ValidateVerticalRule(int column) {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i) {
            if (board[i, column].HasValue) {
                if ((temp | board[i, column].Value) == temp) {
                    return false;
                }
                temp |= board[i, column].Value;
            }
        }
        return true;
    }
    private bool ValidateBlockRule(int row, int column) {
        var startRow = row / 3 * 3;
        var startColumn = column / 3 * 3;
        ushort temp = 0;
        for (var i = startRow; i < startRow + 3; ++i) {
            for (var j = startColumn; j < startColumn + 3; ++j) {
                if (board[i, j].HasValue) {
                    if ((temp | board[i, j].Value) == temp) {
                        return false;
                    }
                    temp |= board[i, j].Value;
                }
            }
        }
        return true;
    }
    private bool SolveSudoku(int i, int j) {
        while (true) {
            if (j == 9) {
                ++i;
                j = 0;
            }
            if (i == 9) {
                return true;
            }
            if (board[i, j].HasValue) {
                ++j;
            } else {
                break;
            }
        }
        ushort stop = 1 << 9;
        for (ushort t = 1; t != stop; t <<= 1) {
            board[i, j] = t;
            if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j)) {
                if (SolveSudoku(i, j + 1)) {
                    return true;
                }
            }
        }
        board[i, j] = null;
        return false;
    }
}
```

### Java

```java
class Solution {
private
  boolean ok;
private
  char[][] board;
private
  List<Integer> t = new ArrayList<>();
private
  boolean[][] row = new boolean[9][9];
private
  boolean[][] col = new boolean[9][9];
private
  boolean[][][] block = new boolean[3][3][9];
public
  void solveSudoku(char[][] board) {
    this.board = board;
    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.') {
          t.add(i * 9 + j);
        } else {
          int v = board[i][j] - '1';
          row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
        }
      }
    }
    dfs(0);
  }
private
  void dfs(int k) {
    if (k == t.size()) {
      ok = true;
      return;
    }
    int i = t.get(k) / 9, j = t.get(k) % 9;
    for (int v = 0; v < 9; ++v) {
      if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
        board[i][j] = (char)(v + '1');
        dfs(k + 1);
        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
      }
      if (ok) {
        return;
      }
    }
  }
}

```

### CPP

```cpp
using pii = pair < int , int > ; class Solution { public: void solveSudoku ( vector < vector < char >>& board ) { bool row [ 9 ][ 9 ] = { false }; bool col [ 9 ][ 9 ] = { false }; bool block [ 3 ][ 3 ][ 9 ] = { false }; bool ok = false ; vector < pii > t ; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { if ( board [ i ][ j ] == '.' ) { t . push_back ({ i , j }); } else { int v = board [ i ][ j ] - '1' ; row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; } } } function < void ( int k ) > dfs = [ & ]( int k ) { if ( k == t . size ()) { ok = true ; return ; } int i = t [ k ]. first , j = t [ k ]. second ; for ( int v = 0 ; v < 9 ; ++ v ) { if ( ! row [ i ][ v ] && ! col [ j ][ v ] && ! block [ i / 3 ][ j / 3 ][ v ]) { row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; board [ i ][ j ] = v + '1' ; dfs ( k + 1 ); row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = false ; } if ( ok ) { return ; } } }; dfs ( 0 ); } };
```

### Python

```python
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None: def dfs(k): nonlocal ok if k == len(t): ok = True return i, j = t[k] for v in range(9): if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False: row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True board[i][j] = str(v + 1) dfs(k + 1) row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False if ok: return row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] block = [[[False] * 9 for _ in range(3)] for _ in range(3)] t = [] ok = False for i in range(9): for j in range(9): if board[i][j] == '.': t . append((i, j)) else: v = int(board[i][j]) - 1 row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True dfs(0)

```