51. N-Queens

1.問題

• n queen

2.想法

• 提問

  • 確認題意: col, row, diagonal都只能有一個queen

• parameter

• • record list

  • res list

  • n

  • new row (new col在程式中)

  • col list (存放已經放入的queen的位置)

• test input

• 說明想法

  • isValid function:

    • 檢查col:

      • col list的index是row, value是col, 由於在相同row下我們只有放一個queen, 因此檢查時只需要檢查col有沒有collision

    • 檢查對角線: 新位置跟array中的所有值去比較, col的差值不可以等於row的差值

  • solveHQ function

    • DFS

      • base case: 當new row == n表示所有row都擺上了queen, push record到res中

        • ray tracking: 在每一輪中嘗試對new row的不同col放置queen, 若能通過isValid, 則push到record及col中, 進到下一輪迭帶, 如同別的DFS + ray tracking題目, 要記得pop回來

• 測試計算複雜度

3.程式碼

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> record;
        vector<int> col;
        solveHQ(n, 0, res, record, col);
        return res;
    }
private:
    //假設棋盤為正方形, 依序填完第0個row後, 再換下個row, 共填n個row
    void solveHQ(int n, int newRow, vector<vector<string>>& res, vector<string>& record, vector<int>& col){
        if (newRow == n) {
            res.push_back(record);
            return;
        }
        
        for (int i = 0; i <n; i++) {
            if (isValid(col, i, newRow)) {
                //填入Q
                string s(n, '.');
                s[i] = 'Q';
                record.push_back(s);
                col.push_back(i);
                solveHQ(n, newRow + 1, res, record, col);
                record.pop_back();
                col.pop_back();
            }
        }
    }
    
    //確認new col的位置是否合法
    //用一個vector來存放col, row的值: index代表第幾個row, col[index]代表第幾個col
    bool isValid(vector<int> col, int newCol, int newRow) {
        for (int i = 0; i <col.size(); i++) {
            if (col[i] == newCol ||
                abs(i - newRow) == abs(col[i] - newCol)) {
                //對角線: 當row差值等於col差值時
                return false;
            }
        }
        return true;
    }
};