# LC 37. Sudoku Solver

### [Problem link](https://leetcode.com/problems/sudoku-solver/)

###### tags: `leedcode` `python` `c++` `hard` `Backtracking`

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

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

- Each of the digits <code>1-9</code> must occur exactly once in each row.
- Each of the digits <code>1-9</code> must occur exactly once in each column.
- Each of the digits <code>1-9</code> must occur exactly once in each of the 9 <code>3x3</code> sub-boxes of the grid.

The <code>'.'</code> character indicates empty cells.

**Example 1:**
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png" style="height:250px; width:250px" />

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:

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png" style="height:250px; width:250px" />

**Constraints:**

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

## Solution 1 - Backtracking
#### python
(523ms)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def isValid(row, col, val):
            val = str(val)
            for i in range(9):
                if board[row][i] == val:
                    return False
                if board[i][col] == val:
                    return False
            start_row = row - (row % 3)
            start_col = col - (col % 3)
            for i in range(start_row, start_row + 3):
                for j in range(start_col, start_col + 3):
                    if board[i][j] == val:
                        return False

            return True

        def backtrack():
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if board[i][j] != '.':
                        continue
                    for k in range(1, 10):
                        if isValid(i, j, k):
                            board[i][j] = str(k)
                            if backtrack():
                                return True
                            board[i][j] = '.'
                    return False

            return True

        backtrack()

(319ms)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = defaultdict(set)
        cols = defaultdict(set)
        blocks = defaultdict(set)

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != '.':
                    rows[i].add(board[i][j])
                    cols[j].add(board[i][j])
                    blocks[(i // 3) * 3 + (j // 3)].add(board[i][j])

        def isValid(row, col, val):
            if val in rows[row] or val in cols[col] or val in blocks[(row // 3) * 3 + (col // 3)]:
                return False
            return True

        def backtrack():
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if board[i][j] != '.':
                        continue
                    for k in range(1, 10):
                        if isValid(i, j, str(k)):
                            board[i][j] = str(k)
                            rows[i].add(board[i][j])
                            cols[j].add(board[i][j])
                            blocks[(i // 3) * 3 + (j // 3)].add(board[i][j])
                            if backtrack():
                                return True
                            rows[i].remove(board[i][j])
                            cols[j].remove(board[i][j])
                            blocks[(i // 3) * 3 + (j // 3)].remove(board[i][j])
                            board[i][j] = '.'
                    return False

            return True

        backtrack()

#### C++

class Solution {
public:
    bool isValid(int row, int col, int num, vector<vector<char>>& board) {
        // check row
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }

        // check col
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }

        // check block
        int blockRow = (row / 3) * 3;
        int blockCol = (col / 3) * 3;
        for (int i = blockRow; i < blockRow + 3; i++) {
            for (int j = blockCol; j < blockCol + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }

        return true;
    }

    bool backtracking(vector<vector<char>>& board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    continue;
                }
                for (char num = '1'; num <= '9'; num++) {
                    if (isValid(row, col, num, board)) {
                        board[row][col] = num;
                        if (backtracking(board)) {
                            return true;
                        }
                        board[row][col] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(1) | O(1) |

## Note
[reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.md)