# 51 - N-Queens

解法一 - Backtracking

這題也算是滿經典的，主要的概念就是要把所有的可能放法都搜過一遍。最直覺的做法就是在第一個 row 的每一個 col 上都放放看 queen，然後繼續往下一個 row 放，只要遇到 queen 會互相攻擊就不繼續往下放。

其中判斷會不會互相攻擊，我們是用 isValid 這個 function 來判斷，我們只需要判斷目前這個 (row, col) 位置，會不會跟上方 row 的 queen 有幾種衝突：

1. 在同一 col

2. 在同一左上-右下的斜線上(這一斜線上的所有位置都有著相同的 row-col 值)

3. 在同一右上-左下的斜線上(這一斜線上的所有位置都有著相同的 row+col 值)

如果成功熬過 n 次 isValid 的考驗，就表示目前的擺法正確，可以呼叫 drawChessBoard 把這一種擺法畫出來放進答案。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if(n <= 0) return res;

        vector<int> cols;
        search(n, res, cols);

        return res;
    }

private:
    void search(int& n, vector<vector<string>>& res, vector<int>& cols) {
        if(cols.size() == n) {
            res.push_back(drawChessBoard(cols));
        }

        for(int col=0; col<n; col++) {
            if(!isValid(cols, col))
                continue;

            cols.push_back(col);
            search(n, res, cols);
            cols.pop_back();
        }
    }

    bool isValid(const vector<int>& cols, const int col) {
        // We only need to consider queens in the rows above
        int row = cols.size();

        for(int r=0; r<row; r++) {
            // Up-Down direction
            if(cols[r] == col)
                return false;

            // Top-Left to Bottom-Right direction
            if(cols[r]-r == col-row)
                return false;

            // Top-Right to Bottom-Left direction
            if(cols[r]+r == col+row)
                return false;   
        }

        return true;
    }

    vector<string> drawChessBoard(vector<int>& cols) {
        vector<string> board;

        for(int r=0; r<cols.size(); r++) {
            int col = cols[r];
            string row;

            for(int j=0; j<cols.size(); j++) {
                if(j != col) row += ".";
                else row += "Q";
            }

            board.push_back(row);
        }

        return board;
    }
};