C++實現LeetCode(51.N皇後問題)

Posted on by

[LeetCode] 51. N-Queens N皇後問題

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
[“.Q..”,  // Solution 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”,  // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

經典的N皇後問題，基本所有的算法書中都會包含的問題。可能有些人對國際象棋不太熟悉，大傢都知道中國象棋中最叼的是車，橫豎都能走，但是在國際象棋中還有更叼的，就是皇後，不但能橫豎走，還能走兩個斜線，有如 bug 一般的存在。所以經典的八皇後問題就應運而生瞭，在一個 8×8 大小的棋盤上如果才能放8個皇後，使得兩兩之間不能相遇，所謂一山不能容二虎，而這裡有八個母老虎，互相都不能相遇。對於這類問題，沒有太簡便的方法，隻能使用窮舉法，就是嘗試所有的組合，每放置一個新的皇後的時候，必須要保證跟之前的所有皇後不能沖突，若發生瞭沖突，說明當前位置不能放，要重新找地方，這個邏輯非常適合用遞歸來做。我們先建立一個長度為 nxn 的全是點的數組 queens，然後從第0行開始調用遞歸。在遞歸函數中，我們首先判斷當前行數是否已經為n，是的話，說明所有的皇後都已經成功放置好瞭，所以我們隻要將 queens 數組加入結果 res 中即可。否則的話，我們遍歷該行的所有列的位置，行跟列的位置都確定後，我們要驗證當前位置是否會產生沖突，那麼就需要使用一個子函數來判斷瞭，首先驗證該列是否有沖突，就遍歷之前的所有行，若某一行相同列也有皇後，則沖突返回false；再驗證兩個對角線是否沖突，就是一些坐標轉換，主要不要寫錯瞭，若都沒有沖突，則說明該位置可以放皇後，放瞭新皇後之後，再對下一行調用遞歸即可，註意遞歸結束之後要返回狀態，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> queens(n, string(n, '.'));
        helper(0, queens, res);
        return res;
    }
    void helper(int curRow, vector<string>& queens, vector<vector<string>>& res) {
        int n = queens.size();
        if (curRow == n) {
            res.push_back(queens);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (isValid(queens, curRow, i)) {
                queens[curRow][i] = 'Q';
                helper(curRow + 1, queens, res);
                queens[curRow][i] = '.';
            }
        }
    }
    bool isValid(vector<string>& queens, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (queens[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (queens[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < queens.size(); --i, ++j) {
            if (queens[i][j] == 'Q') return false;
        }
        return true;
    }
};

我們還可以隻使用一個一維數組 queenCol 來保存所有皇後的列位置，初始化均為-1， 那麼 queenCol[i] 就是表示第i個皇後在 (i, queenCol[i]) 位置，遞歸函數還是跟上面的解法相同，就是在當前行數等於n的時候，我們要將 queenCol 還原成一個 nxn 大小的矩陣，並存入結果 res 中。這種記錄每個皇後的坐標的方法在驗證沖突的時候比較簡單，隻要從第0行遍歷到當前行，若跟之前的皇後的列數相同，直接返回false，叼就叼在判斷對角線沖突非常簡便，因為當兩個點在同一條對角線上，那麼二者的橫坐標差的絕對值等於縱坐標差的絕對值，利用這條性質，可以快速的判斷沖突，代碼如下：

解法二：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> queenCol(n, -1);
        helper(0, queenCol, res);
        return res;
    }
    void helper(int curRow, vector<int>& queenCol, vector<vector<string>>& res) {
        int n = queenCol.size();
        if (curRow == n) {
            vector<string> out(n, string(n, '.'));
            for (int i = 0; i < n; ++i) {
                out[i][queenCol[i]] = 'Q';
            }
            res.push_back(out);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (isValid(queenCol, curRow, i)) {
                queenCol[curRow] = i;
                helper(curRow + 1, queenCol, res);
                queenCol[curRow] = -1;
            }
        }
    }
    bool isValid(vector<int>& queenCol, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (col == queenCol[i] || abs(row - i) == abs(col - queenCol[i])) return false;
        }
        return true;
    }
};

到此這篇關於C++實現LeetCode(51.N皇後問題)的文章就介紹到這瞭,更多相關C++實現N皇後問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：