N-Queens

Solution 1

【这个题虽然是模版题但是我还是忘了最经典的部分】首先声明这是一道dfs模版题，其次说明我看了题解😭。这道题的DFS并不是难点，直接暴力实现也不是不行，但是可以进一步优化其所用的空间（就是这个部分，当时学算法的时候就学习了这个优化方法，很不负众望地忘记了！）。

如果使用传统的DFS的思路，就是创建一个二维的状态棋盘，从第一行到最后一行逐行的各个位置便利，同时记录所在的列和两条对角线的禁止状态。

当然这样写没有任何问题（其实能过），但是这里的状态棋盘可以进一步优化：使用三个一维数组分别记录当前禁止的列和对角线。列比较好找，两条对角线需要额外计算一个斜率（就这里我忘记了！看的题解！对自己很生气！）。对于左下到右上的对角线，斜率是行号加列号；另外一条就是行号减列号。因此记录对角线状态的数组会长一倍（$2n$）。

• 时间复杂度：$O(n!)$，其中$n$为放置的皇后个数，对应棋盘的尺寸。
• 空间复杂度：$O(n)$，其中$n$为放置的皇后个数，对应棋盘的尺寸。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans = vector<vector<string>>();
        vector<int> posRow = vector<int>(n, -1); // 每行皇后的位置
        vector<bool> stateCol = vector<bool>(n, false); // 每列对应的位置
        vector<bool> stateUp = vector<bool>(n * 2, false); // 左下到右上对角
        vector<bool> stateDown = vector<bool>(n * 2, false); // 左上到右下对角
        this->dfs(0, n, ans, posRow, stateCol, stateUp, stateDown);
        
        return ans;
    }
    
private:
    void dfs(int row, int n, vector<vector<string>> &ans, vector<int> &posRow, vector<bool> &stateCol, vector<bool> &stateUp, vector<bool> &stateDown) {
        if (row == n) {
            ans.emplace_back(getSolution(posRow));
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (stateCol[i] || stateUp[n + row + i] || stateDown[n + row - i]) { continue; }

            posRow[row] = i;

            stateCol[i] = true; // 对应列不能放
            stateUp[n + row + i] = true; // 左下到右上对角不能放
            stateDown[n + row - i] = true; // 左上到右下对角不能放

            this->dfs(row + 1, n, ans, posRow, stateCol, stateUp, stateDown);

            stateDown[n + row - i] = false;
            stateUp[n + row + i] = false;
            stateCol[i] = false;
          
            posRow[row] = -1;
        }
    }
    
    
    vector<string> getSolution(vector<int> &posRow) {
        int n = posRow.size();
        auto solution = vector<string>();
        for (int i = 0; i < n; ++i) {
            string solutionRow = string(n, '.');
            solutionRow[posRow[i]] = 'Q';
            solution.push_back(solutionRow);
        }
        
        return solution;
    }
};

Solution 2

Solution 1的Python实现

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        def dfs(row: int) -> None:
            if row == n: 
                ans.append(self.__getSolution(posRow))
                return
                
            for i in range(n):
                # print(len(stateUp), n + row + i, len(stateDown), n + row - i)
                if stateCol[i] or stateUp[row + i] or stateDown[n + row - i]: continue
                    
                posRow[row] = i
                
                stateCol[i] = True
                stateUp[row + i] = True
                stateDown[n + row - i] = True
                
                dfs(row + 1)
                
                stateDown[n + row - i] = False;
                stateUp[row + i] = False;
                stateCol[i] = False;
                
                posRow[row] = -1
        
        ans = list()

        posRow = [-1] * n
        stateCol = [False] * n
        stateUp = [False] * (2 * n)
        stateDown = [False] * (2 * n)
        
        dfs(0)
        
        return ans
        
    def __getSolution(self, posRow: List[int]) -> List[str]:
        solution = list()
        n = len(posRow)
        
        for i in range(n):
            solutionRow = ['.'] * n
            solutionRow[posRow[i]] = 'Q'
            solution.append("".join(solutionRow))
            
        return solution