37. Sudoku Solver

題目網址：https://leetcode.cn/problems/sudoku-solver/

題意：寫一程式, 可填充空格來解決數獨問題。

數獨的解法需遵從以下規則：

• 數字 1-9 在每一行只能出現一次
• 數字 1-9 在每一列只能出現一次
• 數字 1-9 在每一個以粗實線分隔的 3x3 九宮格內只能出現一次

數獨部分空格已填入數字, 而空格用 '.' 來表示。

Solution：

想法：利用 DFS + Backtracking

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

private:
    // y 為 row, x 為 col
    bool fill(vector<vector<char>>& board, int y, int x){
        // 代表 0 ~ 8 列所有空格都能填完, 故返回 true
        if (y == 9) {
            return true;
        }

        const int nextY = (x == 8) ? y + 1 : y;
        const int nextX = (x == 8) ? 0 : x + 1;

        if (board[y][x] == '.') {
            // 嘗試填入 1 ~ 9
            for (char ch = '1'; ch <= '9'; ++ch) {
                // 若 board[y][x] 不可填入 ch, 則嘗試下一個數
                if (!isValid(board, y, x, ch)) {
                    continue;
                }

                // 可以填入 ch
                board[y][x] = ch;

                // 遞迴找下去, 若可以填, 則返回 true
                if (fill(board, nextY, nextX)) {
                    return true;
                }

                // 否則, 恢復盤面, 並嘗試下一數
                board[y][x] = '.';
            }
        } else { // 若 board[y][x] 已經有數字, 則跳過
            return fill(board, nextY, nextX);
        }

        return false;
    }

    // 檢查在 board[y][x] 填入數字 i 是否會衝突
    bool isValid(const vector<vector<char>>& board, const int y, const int x, const char ch){
        for (int i = 0; i < 9; ++i) {
            if (board[y][i] == ch) { // 同 row 是否衝突
                return false;
            }

            if (board[i][x] == ch) { // 同 col 是否衝突
                return false;
            }

            int blockY = 3 * (y / 3) + (i / 3); // 3 * (y / 3) 為 blockY 的起始位置
            int blockX = 3 * (x / 3) + (i % 3); // 3 * (x / 3) 為 blockX 的起始位置

            if (board[blockY][blockX] == ch) { // 同 block 是否衝突
                return false;
            }
        }

        return true;
    }
};

• time：$O(9^m)$ ➔ m 為所有的空格數, 每一個空格最多有 9 種選擇
• space：$O(1)$ ➔ $O(9*9)$, 遞迴深度最多不超過 9 * 9