37. 解数独

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

• 37. 解数独

  • 题目描述

  • 方法 1: 回溯+哈希表

    • 思路

    • 复杂度分析

    • 代码

题目描述

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

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

数字 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

/**
 * @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

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)