LeetCode N皇後 解數獨（回溯算法）

文章目錄

• ​​51. N 皇後​​
• ​​37. 解數獨​​

51. N 皇後

我們已知一行隻能有一個皇後，是以可以用一維數組chessboard表示皇後的位置，即(i, chessboard[i])表示第i個皇後的位置

通過上圖全排列，剪枝的方式可以獲得滿足規則的皇後位置，驗證是否沖突時，我們隻需要驗證和前面的皇後是否沖突即可，因為我們是一行一行放置皇後

class Solution {
public:
    vector<int> chessboard;
    vector<vector<string>> ans;

    bool isCollide(int pos){
        for(int i = 0; i < pos; i++){
            if(chessboard[i] == chessboard[pos] || abs(i - pos) == abs(chessboard[i] - chessboard[pos])){
                return true;
            }
        }
        return false;
    }

    void func(int startIndex, int n){
        if(startIndex == n){
            vector<string> tmp;
            for(int i = 0; i < n; i++){
                string path(n, '.');
                path[chessboard[i]] = 'Q';
                tmp.push_back(path);
            }
            ans.push_back(tmp);
        }
        for(int i = startIndex; i < n; i++){
            // 這裡開始一行一行放皇後，一行放一個
            swap(chessboard[startIndex], chessboard[i]);
            if(!isCollide(startIndex)){
                // 目前擺放的位置(startIndex, chessboard[startIndex])是否和前面的皇後沖突
                func(startIndex + 1, n);
            }
            swap(chessboard[startIndex], chessboard[i]);
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        for(int i = 0; i < n; i++){
            chessboard.push_back(i);
        }
        func(0, n);
        return ans;
    }
};      

37. 解數獨

class Solution {
public:
    // 檢查在board[row][col]的位置放val是否合法
    bool isValid(int row, int col, char val, const vector<vector<char>>& board){
        // 檢查列
        for(int i = 0; i < 9; i++){
            if(board[i][col] == val){
                return false;
            }
        }
        // 檢查行
        for(int j = 0; j < 9; j++){
            if(board[row][j] == val){
                return false;
            }
        }
        // 檢查board[row][col]所在的3x3宮格
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for(int i = startRow; i < startRow + 3; i++){
            for(int j = startCol; j < startCol + 3; j++){
                if(board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }

    bool func(vector<vector<char>>& board){
        // 這裡從0開始...
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    // board[i][j]已經被填寫了
                    continue;
                }
                // 開始在board[i][j]位置嘗試放置數字
                for(char val = '1'; val <= '9'; val++){
                    if(!isValid(i, j, val, board)){
                        continue;
                    }
                    board[i][j] = val;
                    if(func(board)){
                        // 找到合法的解，傳回即可，不用再回溯了
                        return true;
                    }
                    board[i][j] = '.';
                }
                // 9個數字都不能放在board[i][j]位置，目前分支失敗，需要向上回溯
                return false;
            }
        }
        return true;
    }


    void solveSudoku(vector<vector<char>>& board) {
        func(board);
    }
};