LeetCode 52. N-Queens II [Hard] [C++] 解題筆記

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 the number of distinct solutions to the n-queens puzzle.

EX:

     Input: 4

    Output: 2
    Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
    [
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],

     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]

想法:

    這題與 51. N-Queens 基本上是一樣的問題，差別在於這題只需要解法個數，因此可以直接利用 51 題的

解法。

完整程式碼:

class Solution {
public:
    int totalNQueens(int n) {
        cols = vector<bool>(n, false);
        diag1 = vector<bool>(2 * n - 1, false);
        diag2 = vector<bool>(2 * n - 1, false);
        cnt = 0;
        nqueens(n, 0);
        
        return cnt;
    }
private:
    vector<bool> cols;
    vector<bool> diag1;
    vector<bool> diag2;
    int cnt;
    
    bool isValid(int r, int c, int n) {
        return !cols[c] && !diag1[r + c] && !diag2[r - c + (n - 1)];
    }
    
    void updateBoard(int r, int c, int n, bool blocked) {
        cols[c] = blocked;
        diag1[r + c] = blocked;
        diag2[r - c + (n - 1)] = blocked;
    }
    
    void nqueens(const int n, const int r) {
        if (r == n) {
            cnt++;
            return;
        }
        
        for (int c = 0; c < n; c++) {
            if (!isValid(r, c, n)) { continue; }
            updateBoard(r, c, n, true);
            nqueens(n, r + 1);
            updateBoard(r, c, n, false);
        }
    }
};