题目描述

题目链接

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

思路

前言
我们可以考虑按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过「递归 + 回溯」的方法枚举所有可能的填法。当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。

由于每个数字在同一行、同一列、同一个九宫格中只会出现一次，因此我们可以使用，以及这三个数组分别表示第行，第列，第个九宫格中填写数字的情况。

:::warning 九宫格的范围为以及。
具体地，第行第列的格子位于第个九宫格中，其中表示对向下取整。 :::

实现
由于我们可以填写的数字范围为，而数组的下标从开始，因此在存储时，我们使用一个长度为的布尔类型的数组，其中第个元素的值为时表示数字出现过。例如我们用表示数字在第行已经出现过，那么我们在遍历到第行的空白格时，就不能填入数字了。

我们首先对整个数独数组进行遍历，来记录数字的初始情况。当我们遍历到第行第列的位置时，如果该位置是一个数字，那么我们需要将、以及均置为。

当我们结束了遍历过程后，就可以开始递归枚举。当递归到第行第列的位置时，我们枚举填入的数字。根据题目的要求，数字不能和当前行、列、九宫格中已经填入的数字相同，因此、以及必须均为。

当我们填入了数字之后，我们要将上述的三个值都置为，并且继续对下一个空白格位置进行递归。在回溯到当前递归层时，我们还要将上述的三个值重新置为。

代码实现

public void solveSudoku(char[][] board) {
    // 遍历矩阵元素，记录初始值
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int digit = board[i][j] - '1';
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
            }
        }
    }
    // 遍历矩阵元素，填充数独
    recur(board, 0, 0);
}
private final boolean[][] line = new boolean[9][9];
private final boolean[][] column = new boolean[9][9];
private final boolean[][][] block = new boolean[3][3][9];
private boolean recur(char[][] board, int i, int j) {
    // 当前行已填充满，继续填充下一行
    if (j == board.length) {
        j = 0;
        i++;
        // 所有行已经全部填充完成
        if (i == board.length) {
            return true;
        }
    }
    // 当前元素不需要填充
    if (board[i][j] != '.') {
        return recur(board, i, j + 1);
    }
    // 遍历所有可用选择的数字，寻找一个符合当前要求的数字
    for (int digit = 0; digit < 9; digit++) {
        if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
            // 填充数字
            board[i][j] = (char) (digit + '0' + 1);
            line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
            // 递归
            if (recur(board, i, j + 1)) {
                return true;
            }
            // 回溯
            board[i][j] = '.';
            line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
        }
    }
    return false;
}

复杂度分析

由于这些方法均以「递归 + 回溯」为基础，算法运行的时间（以及时间复杂度）很大程度取决于给定的输入数据，而我们很难找到一个非常精确的渐进紧界。因此这里只给出一个较为宽松的渐进复杂度上界，即最多有个空白格，每个格子可以填中的任意整数。