N皇后(系列)

51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

 

示例 1：
输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[[“Q”]]  

提示：

1 <= n <= 9

回溯穷举

逐行尝试选择皇后放置的列，放置之前先检查可以放置在哪一列。当所有行都判断完后，可以将答案放置在答案数组中

一个皇后可以放置的位置，需要满足：
1.同列上方无皇后
2.左右斜对角延伸的上方每一行无皇后

python3代码

2020.07.25 15:37:13年的代码

printN负责打印结果数组

cal8queens通过递归穷举每一行

is_valid判断指定行和列是否OK

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def printN():
            solution = []
            for row in range(n):
                tmp = ['.']*n
                tmp[result[row]] = 'Q'
                tmp = ''.join(tmp)
                solution.append(tmp)
            ans.append(solution)
        
        def cal8queens(row):
            if row == n:
                printN()
            for column in range(n):
                if is_valid(row, column, n, result):
                    result[row] = column
                    cal8queens(row+1)
        
        def is_valid(row, column, n, result):
            leftup = column - 1
            righttop = column + 1
            for i in range(row-1, -1, -1):
                if result[i] == column:
                    return False
                if leftup >= 0 and result[i] == leftup:
                    return False
                if righttop < n and result[i] == righttop:
                    return False
                leftup -= 1
                righttop += 1
            return True
        
        # result记录  第i行的皇后放在第几列
        result = [-1]*n
        ans = []
        cal8queens(0)
        return ans

C++的代码

class Solution {
    vector<string> chess;
    vector<vector<string>> ans;
    void backtrack(int row, int n){
        if (row == n) {
            ans.emplace_back(chess);
            return;
        }
        for (int column = 0; column < n; column++) {
            if (check(row, column, n)) {
                chess[row][column] = 'Q';
                // print();
                backtrack(row+1, n);
                chess[row][column] = '.';
                
            }
        }
    }

    bool check(int row, int column, int n) {
        int left = column - 1, right = column + 1;
        for (int i = row-1; i >= 0; i--) {
            if (chess[i][column] == 'Q') return false;
            if (left >= 0 && chess[i][left] == 'Q') return false;
            if (right < n && chess[i][right] == 'Q') return false;
            left--;
            right++;
        }
        return true;
    }

    void print(){
        cout << endl;
        for (int i = 0; i < chess.size(); i++){
            cout << chess[i] << endl;
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        chess.resize(n, string(n, '.'));
        backtrack(0, n);
        return ans;
    }
};

基于集合的回溯

前一种方法中，check函数的时间复杂度为O(n)，导致整体的时间复杂度较高为O(n*n!)
可以使用集合将check的时间复杂度降低到O(1)

通过分析，我们可以发现：

• 1. 左上方斜线上的元素，横纵坐标之差相等
• 2. 右上方斜线上的元素，横纵坐标之和相等
• 3. 纵向方向的元素，纵坐标相等。

所以可以用三个集合存储上述的数，用空间换时间

class Solution {
    vector<string> chess;
    vector<vector<string>> ans;
    // 分别记录左上方、右上方、垂直方向三条线的值
    unordered_set<int> leftup;
    unordered_set<int> rightup;
    unordered_set<int> columns;
    void backtrack(int row, int n){
        if (row == n) {
            ans.emplace_back(chess);
            return;
        }
        for (int column = 0; column < n; column++) {
            if (leftup.find(row-column) != leftup.end()) continue;
            if (rightup.find(row+column) != rightup.end()) continue;
            if (columns.find(column) != columns.end()) continue;
            
            chess[row][column] = 'Q';
            leftup.insert(row-column);
            rightup.insert(row+column);
            columns.insert(column);
            backtrack(row+1, n);
            //还原现场
            chess[row][column] = '.';
            leftup.erase(row-column);
            rightup.erase(row+column);
            columns.erase(column);
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        chess.resize(n, string(n, '.'));
        backtrack(0, n);
        return ans;
    }
};

基于位运算的回溯

前一种使用集合来记录三个方向是否可以放置皇后，这里用三个数通过位运算来表示，
可以将判断是否能放皇后的空间复杂度从O(N)降低为O(1)

TODO

52. N皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

 

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：1  

提示：

1 <= n <= 9

基于集合的回溯

思路同上

class Solution {
    int ans;
    // 分别记录左上方、右上方、垂直方向三条线的值
    unordered_set<int> leftup;
    unordered_set<int> rightup;
    unordered_set<int> columns;
    void backtrack(int row, int n){
        if (row == n) {
            ans++;
            return;
        }
        for (int column = 0; column < n; column++) {
            if (leftup.find(row-column) != leftup.end()) continue;
            if (rightup.find(row+column) != rightup.end()) continue;
            if (columns.find(column) != columns.end()) continue;
            
            leftup.insert(row-column);
            rightup.insert(row+column);
            columns.insert(column);
            backtrack(row+1, n);
            //还原现场
            leftup.erase(row-column);
            rightup.erase(row+column);
            columns.erase(column);
        }
    }

public:
    int totalNQueens(int n) {
        backtrack(0, n);
        return ans;
    }
};