# 37. 解数独

<https://leetcode-cn.com/problems/sudoku-solver>

* [37. 解数独](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#37-解数独)
  * [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#题目描述)
  * [方法 1: 回溯+哈希表](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#方法-1-回溯哈希表)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#思路)
    * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#复杂度分析)
    * [代码](https://suki.gitbook.io/91-days-algorithm/basic/hashmap/pages/-MNWDoks4EuCHBaUQ4RX#代码)

## 题目描述

```
编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

提示：

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

## 方法 1: 回溯+哈希表

### 思路

这种题的思路就是，先在当前这步做一个决定，然后递归走下一步，每走一步做一个决定；如果走了死胡同，就回到上一步，改变当时的决定再走下一步；或者回到上上步，改变决定再重新往下走，总之就是把所有可能的决定的组合都尝试一遍，直到找到通路。

1. 找到一个空格，填入一个数字，然后递归找另一个空格。
2. 如果在这个空格没有数字可填，说明此路不通，那就原路返回到上一个空格（回溯）。
3. 由于每个空格可填的数字可能不止一个，每个数字都得尝试一遍，然后在循环中递归找另一个空格。
4. 怎么确定空格能填的数字？我们需要知道同一行、同一列、同一个小宫里已经填过的数字：
   1. 用一个 `数组 + 哈希表` 记录每行和每列已填的数字。
   2. 用一个 `3*3 二维数组 + 哈希表` 记录每个小宫已填的数字。
   3. 对于每个空格，尝试数字 1\~9，排除记录在哈希表中的数字。
5. 怎么根据坐标确定空格属于哪个 `3*3` 小宫？
   1. `floor(x/3)` 可以确定是第几行的小宫。
   2. `floor(y/3)` 可以确定是第几列的小宫。

其他看代码注释吧。

p.s. 不用哈希表，用数组记录已填数字的状态也行。

### 复杂度分析

* 时间复杂度：$O(9^n)$，因为一共有 9 个数字，所以递归树可以看成是一个九叉树，这里九叉树的高度是数独表的格子总数 n，所以九叉树的节点最多有 $O(9^n)$ 吧。
* 空间复杂度：$O(n)$，n 是数独表的格子总数，递归栈最大深度，以及哈希表空间都是 n。

### 代码

JavaScript Code

```javascript
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
    // 记录每行已填的数字
    const rows = matrix(9);
    // 记录每列已填的数字
    const cols = matrix(9);
    // 记录每个小宫已填的数字
    const boxes = matrix(3, 3);

    // 记录所有空格子的坐标
    const spaces = [];
    // 遍历数独：
    // 1. 找空格
    // 2. 标记已填数字
    board.forEach((row, x) =>
        row.forEach((cell, y) => {
            // 记录空格的坐标
            if (cell === '.') spaces.push([x, y]);
            // 不是空格的话，标记这个数字已经使用
            else mark(x, y, cell, true);
        }),
    );

    // 开始填空格
    dfs(0);

    // *******************************************

    function dfs(pos) {
        // 所有空格都填完了，说明这条路是通的，返回 true
        if (pos >= spaces.length) return true;

        const [x, y] = spaces[pos];

        // 1~9 的数字都试着填一遍
        for (let n = 1; n <= 9; n++) {
            // 同一行、同一列、同一个小宫出现过的数字不能填
            if (!isValidDigit(x, y, n)) continue;

            // 填入数字
            board[x][y] = n + '';
            mark(x, y, n, true);

            // 递归填下一个空格
            const res = dfs(pos + 1);
            // 回溯
            mark(x, y, n, false);

            // 如果这条路可行，就可以提前返回了
            // 不然递归回来会进入下一个循环
            // 就把原来填的数字覆盖了
            if (res) return true;
        }
    }

    // 根据坐标判断是哪个小宫里的格子
    function getBox(x, y) {
        return boxes[(x / 3) >> 0][(y / 3) >> 0];
    }

    // 检查对应的行和列，还有小宫里有没有出现过该数字
    function isValidDigit(x, y, n) {
        return !rows[x][n] && !cols[y][n] && !getBox(x, y)[n];
    }

    // 标记已填数字
    function mark(x, y, n, status) {
        rows[x][n] = cols[y][n] = getBox(x, y)[n] = status;
    }

    function matrix(rows = 0, cols = 0) {
        return Array(rows)
            .fill(0)
            .map(_ => (cols === 0 ? {} : matrix(cols, 0)));
    }
};
```

Python Code

```python
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        rows = [[False]*9 for _ in range(9)]
        cols = [[False]*9 for _ in range(9)]
        boxes = [[[False]*9 for _ in range(3)] for _ in range(3)]

        def mark(x, y, n, status):
            rows[x][n] = cols[y][n] = boxes[x // 3][y // 3][n] = status

        def valid(x, y, n):
            return (not rows[x][n]) and (not cols[y][n]) and (not boxes[x // 3][y // 3][n])

        def dfs(pos):
            if pos >= len(spaces): return True

            x, y = spaces[pos]
            for n in range(9):
                if not valid(x, y, n): continue

                board[x][y] = str(n + 1)
                mark(x, y, n, True)

                if dfs(pos + 1): return True

                mark(x, y, n, False)

        spaces = []
        for x in range(9):
            for y in range(9):
                cell = board[x][y]

                if cell == '.':
                    spaces.append((x, y))
                else:
                    mark(x, y, int(cell) - 1, True)
        dfs(0)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/91-days-algorithm/basic/hashmap/24.sudoku-solver.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.