LeetCode 37. Sudoku Solver [Hard] [C++] 解題筆記

這題是 36. Valid Sudoku 的進階題，要我們實作一個 9 X 9 數獨的 Solver。

EX:

                                    

想法:

         這題沒有甚摸特別的作法，只能用 DFS 搭配剪枝法來嘗試所有可能，首先像 36. Valid Sudoku 一樣先把已經填好的數字紀錄起來，接著在 DFS 搜索時變可以將已經填好數字的格子濾掉減少搜索範圍。

完整程式碼:

class Solution {

private:

    vector<vector<int>> row, col, box;

public:

    bool solver(vector<vector<char>>& board, int r, int c) {

        // finish

        if (r == 9) { return true; }

        // next col

        int next_c = (c + 1) % 9;

        // next row

        int next_r = (next_c == 0)? r + 1 : r;

        // board[r][c] already filled

        if (board[r][c] != '.') { return solver(board, next_r, next_c); }

        

        // try to fill in 1 ~ 9 in current row, col and box

        for (int i = 1; i <= 9; i++) {

            int box_idx = (r / 3) * 3 + c / 3;

            // can fill with this number

            if (!row[r][i] && !col[c][i] && !box[box_idx][i]) {

                row[r][i] = 1;

                col[c][i] = 1;

                box[box_idx][i] = 1;

                board[r][c] = i + '0';

                if (solver(board, next_r, next_c)) { return true; }

                row[r][i] = 0;

                col[c][i] = 0;

                box[box_idx][i] = 0;

                board[r][c] = '.';

            }

        }

        return false;

    }

    void solveSudoku(vector<vector<char>>& board) {

        row = vector<vector<int>>(9, vector<int>(10));

        col = vector<vector<int>>(9, vector<int>(10));

        box = vector<vector<int>>(9, vector<int>(10));

        

        for (int i = 0; i < board.size(); i++) {

            for (int j = 0; j < board[i].size(); j++) {

                if (board[i][j] == '.') { continue; }

                int n = board[i][j] - '0';

                row[i][n] = 1;

                col[j][n] = 1;

                box[(i / 3) * 3 + j / 3][n] = 1;

            }

        }

        solver(board, 0, 0);

    }

};