一、题目描述

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

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

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

示例一：
输入：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"]
]

二、题解

通过回溯法求解，整体思路与N皇后问题相似，都是依次处理每个格子，同时通过一个 isValid 函数判断当前位置填充值的有效性。

同时因为题目中已经说明题目数据保证输入数独有且仅有一个解，因此我们需要让回溯函数返回值为布尔类型，这样只要遇到任意一种成功的情况，就立即依次返回。

class Solution {
public:
    void solveSudoku(vector<vector<char>> &board) {
        backtracking(board, 0, 0);
    }

private:
    bool backtracking(vector<vector<char>> &board, int row, int col) {
        if (row == board.size()) {
            return true;
        }

        if (board.at(row).at(col) == '.') {
            for (int i = 1; i <= 9; i++) {
                board.at(row).at(col) = static_cast<char>(i + 48);
                if (isValid(board, row, col)) {
                    if (col == board.size() - 1) {
                        if (backtracking(board, row + 1, 0)) {
                            return true;
                        }
                    } else {
                        if (backtracking(board, row, col + 1)) {
                            return true;
                        }
                    }
                }
            }
            board.at(row).at(col) = '.';
        } else {
            if (col == board.size() - 1) {
                if (backtracking(board, row + 1, 0)) {
                    return true;
                }
            } else {
                if (backtracking(board, row, col + 1)) {
                    return true;
                }
            }
        }

        return false;
    }

    bool isValid(vector<vector<char>> &board, int row, int col) {
        char c = board.at(row).at(col);

        /* 检查列重复 */
        for (int i = 0; i < board.size(); i++) {
            if (board.at(i).at(col) == c && i != row) {
                return false;
            }
        }

        /* 检查行重复 */
        for (int j = 0; j < board.size(); j++) {
            if (board.at(row).at(j) == c && j != col) {
                return false;
            }
        }

        /* 检查组内重复 */
        for (int i = (row / 3) * 3; i < ((row / 3) + 1) * 3; i++) {
            for (int j = (col / 3) * 3; j < ((col / 3) + 1) * 3; j++) {
                if (board.at(i).at(j) == c && i != row && j != col) {
                    return false;
                }
            }
        }

        return true;
    }
};