分析

• 本题的考点：递归回溯。

• 可以开辟三个哈希表，分别存储行、列、九宫格已经有哪些数字被填写了。这里九宫格从左向右，从上向下标号依次是(0, 0)~(2, 2)，对于某个坐标(i, j)，其所在的九宫格编号为(i/3, j/3)。

• 暴搜所有方案，然后判断是否合法即可。

代码

• C++

class Solution {
public:

    bool row[9][9], col[9][9], cell[3][3][9];

    void solveSudoku(vector<vector<char>> &board) {
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        memset(cell, 0, sizeof(cell));

        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int x, int y) {
        if (y == 9) x++, y = 0;
        if (x == 9) return true;

        if (board[x][y] != '.') return dfs(board, x, y + 1);
        for (int i = 0; i < 9; ++i) {
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                board[x][y] = '1' + i;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if (dfs(board, x, y + 1)) return true;
                board[x][y] = '.';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};

• Java

class Solution {

    boolean[][] row = new boolean[9][9], col = new boolean[9][9];
    boolean[][][] cell = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            Arrays.fill(row[i], false);
            Arrays.fill(col[i], false);
        }
        for (int i = 0; i < 3; i++) 
            for (int j = 0; j < 3; j++)
                Arrays.fill(cell[i][j], false);

        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) 
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
        dfs(board, 0, 0);
    }

    // 从(0, 0)开始搜
    private boolean dfs(char[][] board, int x, int y) {

        if (y == 9) {
            x++; y = 0;
        }
        if (x == 9) return true;

        if (board[x][y] != '.') return dfs(board, x, y + 1);
        for (int i = 0; i < 9; i++) 
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                board[x][y] = (char)('1' + i);
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if (dfs(board, x, y + 1)) return true;
                board[x][y] = '.';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            }
        return false;
    }
}

时空复杂度分析

• 时间复杂度：指数级别。

• 空间复杂度：和递归的深度有关。