解数独

约 1552 字大约 5 分钟

2025-02-28

37. 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：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"]]
输出：[["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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

回溯

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0); // 开始从 (0, 0) 位置开始进行回溯
    }

    // 注意返回值是true或false，不是List！可以用全局变量+回溯，这样就不用返回值了。
    boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9; // 数独的大小固定为 9x9
        if (j == n) {
            // 如果穷举到最后一列的后一列，即越界的话，就换到下一行重新开始。重点。
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            // 如果穷举到最后一行的下一行，说明越界，说明找到一个可行解。重点。
            return true;
        }
        if (board[i][j] != '.') {
            // 如果当前位置有预设数字，不用我们穷举，直接跳到下一个位置。重点。
            return backtrack(board, i, j + 1);
        }

        // 尝试填入数字 1 到 9。
        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，跳过
            if (!isValid(board, i, j, ch))
                continue;

            board[i][j] = ch; // 做选择：填入数字 ch
            // 如果找到一个可行解，立即结束
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.'; // 撤销选择：恢复为空格
        }
        
        // 穷举完 1 到 9，依然没有找到可行解，返回 false 表示此路不通
        return false;
    }

    // 判断 board[r][c] 是否可以填入字符 n
    boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // 判断行是否存在重复
            if (board[r][i] == n) return false;
            // 判断列是否存在重复
            if (board[i][c] == n) return false;
            // 判断 3x3 方框是否存在重复。重点。r/3是从上往下数第几个方块，每一个方块都有三行，所以r/3就是第几行。
            // (r/3, c/3)是(r,c)所在的方框的左上角的索引，i是在遍历这个方框中的9个点。
            if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n)
                return false;
        }
        return true; // 如果以上条件都不满足，说明可以填入字符 n
    }
}

假设我们在一个数独棋盘上操作，当前的位置是 (r, c)，比如说位置 (4, 4)，我们要检查数字 5 是否可以放在这个位置。

首先，我们需要找到 (4, 4) 所在的 3x3 小方框：

+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . 5 . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

我们看到 (4, 4) 在棋盘的中心，位于中间的 3x3 小方框中。

(r / 3) 表示当前行 r 所在的 3x3 小方框的行索引。对于 r = 4，计算 (4 / 3) = 1，表示当前行位于第二个 3x3 小方框的行。
(c / 3) 表示当前列 c 所在的 3x3 小方框的列索引。对于 c = 4，计算 (4 / 3) = 1，表示当前列位于第二个 3x3 小方框的列。

所以，当前 3x3 小方框的左上角坐标是 (1 * 3, 1 * 3)，即 (3, 3)。

for (int i = 0; i < 9; i++) {
    if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n) {
        return false;
    }
}

我们需要遍历这个 3x3 小方框的所有位置，检查是否有重复数字 n。遍历的索引用 i 从 0 到 8，每个 i 对应小方框中的一个位置。

i / 3 是当前元素在 3x3 小方框中的行索引。例如，当 i 取 0, 1, 2 时，对应 3x3 小方框的第一行，i / 3 = 0；当 i 取 3, 4, 5 时，对应 3x3 小方框的第二行，i / 3 = 1；当 i 取 6, 7, 8 时，对应 3x3 小方框的第三行，i / 3 = 2。
i % 3 是当前元素在 3x3 小方框中的列索引。例如，当 i 取 0, 3, 6 时，对应 3x3 小方框的第一列，i % 3 = 0；当 i 取 1, 4, 7 时，对应 3x3 小方框的第二列，i % 3 = 1；当 i 取 2, 5, 8 时，对应 3x3 小方框的第三列，i % 3 = 2。

在数独中，每个空格可以填写 1 到 9 这 9 个数字。对于一个有 N 个空格的数独：

在最坏情况下，每个空格都需要穷举 9 个数字。
最差情况下，时间复杂度是 O(9^N)。

然而，实际的复杂度会比 O(9^N) 低得多，因为 isValid 函数可以剪枝掉大量不合法的尝试。

空间复杂度主要由递归调用栈的深度决定：

在最坏情况下，递归的最大深度为 N，即数独中所有空格的数量。
每次递归调用会使用常数级别的空间（例如局部变量和参数），所以空间复杂度为 O(N)。