37. 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

---

回溯

先遍历一次board，找到需要填数的位置，然后依次遍历填写，如果填写完成就结束。

class Solution {
    int rows[9][9], columns[9][9], subboxes[3][3][9];
    int valid;
    vector<pair<int, int>> spaces;
    void backtrack(vector<vector<char>>& board, int index) {
        // cout << "index:" << index << endl;
        if (index == spaces.size()) {
            valid = true;
            return;
        }
        auto [row, column] = spaces[index];
        // 题目保证了仅有一个唯一解, 当所有的数都填完以后，即结束
        for (int i = 0; i < 9 && !valid; i++) {
            if (rows[row][i] == 0 && columns[column][i] == 0 && subboxes[row/3][column/3][i] == 0) {
                board[row][column] = i + 1 + '0';
                rows[row][i]++;
                columns[column][i]++;
                subboxes[row/3][column/3][i]++;
                backtrack(board, index+1);
                // board[row][column] = '.';
                rows[row][i]--;
                columns[column][i]--;
                subboxes[row/3][column/3][i]--;
            }
        }
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        valid = false;
        memset(rows, 0, sizeof(rows));
        memset(columns, 0, sizeof(columns));
        memset(subboxes, 0, sizeof(subboxes));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0' - 1;
                    rows[i][num]++;
                    columns[j][num]++;
                    subboxes[i/3][j/3][num]++;
                    if (rows[i][num] > 1 || columns[j][num] > 1 || subboxes[i/3][j/3][num] > 1){
                        return;
                    }
                }else{
                    spaces.emplace_back(i, j);
                }
            }
        }
        backtrack(board, 0);
    }
};