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

這題是經典的 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.

EX:

        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.

想法:

    通常這種棋盤類型的題目(ex: 37. Sudoku Solver )都是利用 DFS 遍歷列舉出所有 solution 然後在過程中

看看有沒有甚摸情況是可以剪枝(prune)來減少搜索時間的，而這題的關鍵之處在於怎摸快速判斷兩個 Queen 之間

是否可同時存在，因為 Queen 的行為模式是可以走 "直行"，"橫列" 還有 "斜線"，直行橫列的部份很容易處理，

"斜線" 的部份就需要一些 index 操作的技巧來表達，我們可以利用 row + col 來表示 / 這個方向的對角線 index，因為

最大會是 num of row + num of col = n + n - 1 因此需要一個 2*n - 1 的一維 array 來紀錄，而 \ 這個方向的對角線 index 

比較複雜一點，可以用 row - col + (n - 1) 來表示範圍一樣是 0 ~ 2*n - 1。

當然我們可以用另一個二維陣列來紀錄每個位置上有沒有 Queen，然後遍歷看看有沒有兩個 Queen 在同一個對角線上，

但這樣會特別耗費時間和空間，接著只要利用 DFS 按列/行列舉擺放 Queen 即可。

完整程式碼:

/* key: the index setting for diagonal
 * row num + col num can unique represent one diagonal "/"
 * row num - col num + n - 1 (n is num of queens i.e. num of rows and cols)can unique represent one diagonal "\"
 */
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        cols = vector<int>(n, 0);
        diag1 = vector<int>(2 * n - 1, 0);
        diag2 = vector<int>(2 * n - 1, 0);
        board = vector<string>(n, string(n, '.'));
        sols.clear();
        
        nqueens(n, 0);
        
        return sols;
    }
private:
    vector<int> cols;
    vector<int> diag1;
    vector<int> diag2;
    vector<string> board;
    vector<vector<string>> sols;
    
    // row, col, num of queens(i.e. num of rows)
    bool isVaild(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;
        board[r][c] = (blocked)? 'Q' : '.';
    }
    
    // try to put queen on r-th row
    void nqueens(const int n, const int r) {
        // find one solution!
        if (r == n) {
            sols.push_back(board);
            return;
        }
        
        for (int c = 0; c < n; c++) {
            if (!isVaild(r, c, n)) { continue; }
            updateBoard(r, c, n, true);
            // try to put queen on r+1-th row
            nqueens(n, r + 1);
            updateBoard(r, c, n, false);
        }
    }
};