【Day 49 】2022-01-29 - 52. N 皇后 II

[azl397985856]

52. N 皇后 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/n-queens-ii/

前置知识

• 回溯
• 深度优先遍历

  题目描述

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

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

示例 1：

![](https://tva1.sinaimg.cn/large/008i3skNly1gvucyhyefdj30k208yq3f.jpg)

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

输入：n = 1 输出：1  

提示：

1 <= n <= 9 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

[for123s]

class Solution {
public:
    int totalNQueens(int n) {
        return solve(n, 0, 0, 0, 0);
    }

    int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int position = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
            }
            return count;
        }
    }
};

[zzzpppy]

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }

    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }

    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

[CodingProgrammer]

思路

在51题的基础上，返回结果的size

代码

class Solution {
    public int totalNQueens(int n) {
         List<List<String>> res = solveNQueens(n);
         return res.size();
    }

    public List<List<String>> solveNQueens(int n) {
        char[][] chessBoard = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(chessBoard[i], '.');
        }
        List<List<String>> res = new ArrayList<>();
        char[][] test = new char[][] {{'.','Q'}, {'.','Q'}};
        backtracking(chessBoard, 0, n, res);
        return res;
    }

    private List<String> array2List(char[][] chessBoard, int n) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            path.add(new String(chessBoard[i]));
        }
        return path;
    }

    private boolean isValid(char[][] chessBoard, int row, int col, int n) {
        // 同列校验
        for (int i = 0; i < n; i++) {
            if (chessBoard[i][col] == 'Q') return false;
        }

        // 45度校验
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessBoard[i][j] == 'Q') return false;
        }

         // 135度校验
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessBoard[i][j] == 'Q') return false;
        }

        return true;
    }

    private void backtracking(char[][] chessBoard, int row, int n, List<List<String>> res) {
        if (row == n) {
            res.add(array2List(chessBoard, n));
        }

        for (int col = 0; col < n; col++) {
            if (isValid(chessBoard, row, col, n)) {
                chessBoard[row][col] = 'Q';
                backtracking(chessBoard, row + 1, n, res);
                chessBoard[row][col] = '.';
            }
        }
    }
}

复杂度

• 时间复杂度：O(N!)，其中 N 是皇后数量。
• 空间复杂度：O(N)，其中 N 是皇后数量。

[Yachen-Guo]

class Solution {
    int res = 0;
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        init(board);
        backTracking(board,0);
        return res;
    }

    private void init(char[][] board){
        for(int i = 0; i < board.length; i++)
            Arrays.fill(board[i],'.');
    }

    private void backTracking(char[][] board, int rowIndex){
        if(rowIndex == board.length){
            res ++;
            return;
        }

        for(int colIndex = 0; colIndex < board.length; colIndex++){
            if(isValid(board,rowIndex,colIndex)){
                board[rowIndex][colIndex] = 'Q';
                backTracking(board,rowIndex+1);
                board[rowIndex][colIndex] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int rowIndex, int colIndex){
        for(int i = rowIndex - 1; i >= 0; i--){
            if(board[i][colIndex] == 'Q') return false;
        }

        for(int i = rowIndex - 1, j = colIndex -1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] == 'Q') return false;
        }

        for(int i = rowIndex -1, j = colIndex +1; i >= 0 && j < board.length; i--, j++){
            if(board[i][j] == 'Q') return false;
        }

        return true;
    }
}

[chakochako]

class Solution:
    def totalNQueens(self, n: int) -> int:
        def solve(row: int, columns: int, diagonals1: int, diagonals2: int) -> int:
            if row == n:
                return 1
            else:
                count = 0
                availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2))
                while availablePositions:
                    position = availablePositions & (-availablePositions)
                    availablePositions = availablePositions & (availablePositions - 1)
                    count += solve(row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1)
                return count

        return solve(0, 0, 0, 0)

[Jay214]

/**

• @param {number} n
• @return {number} */ var totalNQueens = function (n) { let count = 0 /**
  • dfs函数
  • @param {number} x x坐标 0~n-1
  • @param {number} y y坐标 0~n-1
  • @param {number[][]} arr 存已放置皇后坐标的数组 */ const dfs = (x, y, arr) => { // 遍历已放置皇后的坐标 for (let [x0, y0] of arr) { // 如果在一条直线或者一条斜线上，直接return if (y === y0 || Math.abs(x - x0) === Math.abs(y - y0)) { return } } // 如果x坐标等于n-1，则表示已经放置n个皇后，为一种解法 if (x === n - 1) { count++ return } // 对x坐标为x+1的那一行进行遍历，挨个进行dfs for (let i = 0; i < n; i++) { arr.push([x, y]) dfs(x + 1, i, arr) arr.pop() } } // 对x坐标为0的那一行进行遍历，挨个进行dfs for (let i = 0; i < n; i++) { dfs(0, i, []) } return count };

[machuangmr]

代码

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
            return count;
        }
    }
}

[spacker-343]

class Solution {
    public int totalNQueens(int n) {
        int[] chessboard = new int[n];
        int[] cnt = new int[]{0};
        traceback(chessboard,0,n,cnt);
        return cnt[0];
    }

    private void traceback(int[] chessboard, int row, int n, int[] cnt){
        if(row == n){
            cnt[0]++;
        }
        for(int col=0; col<n; col++){
            if(check(chessboard, row, col)){
                chessboard[row] = col;
                traceback(chessboard,row+1,n,cnt);
                chessboard[row] = -1;
            }
        }
    }

    private boolean check(int[] chessboard, int row, int col){
        for(int i=0; i<row; i++){
            if(chessboard[i] == col) return false;
            if(chessboard[i]+i == col+row) return false;
            if(chessboard[i]-i == col-row) return false;
        }
        return true;
    }
}

[tangjy149]

class Solution {
public:
    vector<int> v;
    unordered_map<int, int> m; 
    int ans = 0;
    void dfs(int row, int n) {
        if (row > n) {
            ans++;
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (m.find(j) == m.end()) { 
                int condition = 1;
                for (int k = 1; k < row; k++) { 
                    if (k - v[k] == row - j || k + v[k] == row + j) { 
                        condition = 0;
                        break;
                    }
                }
                if (condition == 1) {
                    v[row] = j;
                    m[j]++;
                    dfs(row + 1, n);
                    v[row] = 0; 
                    m.erase(j);
                }
            }
        }
    }
    int totalNQueens(int n) {
        v.resize(n + 5);
        dfs(1, n);
        return ans;
    }
};

[GaoMinghao]

思路

主要是回溯思想的应用，虽然看起来优化空间很大，但是结构和思路还是比较清晰的， 感觉遇到一个一直困扰我的问题，就是在这种相对复杂的条件中（对我现在而言），是否可以将判断标准进行转化而再进一步优化，例如判断是否可以放置皇后，是否可以不用每次都比较↖️，⬆️，↗️这么多的场景呢

代码

class Solution {
    public int totalNQueens(int n) {
        String[][] cheeseBoard = new String[n][n];
        for(int i = 0; i < n;i++) {
            for(int j = 0; j <n;j++) {
                cheeseBoard[i][j] = "*";
            }
        }
        int ans = 0;
        return bareBack(cheeseBoard, 0, ans);
    }

    private int bareBack(String[][] cheeseBoard, int row , int ans) {
        if(row == cheeseBoard.length) {
            ans ++;
            return ans;
        }
        int n = cheeseBoard.length;
        for(int col = 0; col < n;col++) {
            if(!isValid(cheeseBoard, col, row))
                continue;
            cheeseBoard[row][col] = "Q";
            ans = bareBack(cheeseBoard, row+1, ans);
            cheeseBoard[row][col] = "*";
        }
        return ans;
    }

    private boolean isValid(String[][] cheeseBoard, int col, int row) {
        int size = cheeseBoard.length;
        // 检查同一列
        for(int i = 0; i < row; i++)
            if(cheeseBoard[i][col].equals("Q"))
                return false;

        // 检查左上方
        for(int i = row - 1, j = col -1 ; i >= 0 && j >= 0; i --,j--)
            if(cheeseBoard[i][j].equals("Q"))
                return false;

        // 检查右上方
        for(int i = row -1,j= col + 1; i>=0&& j < size;i--,j++)
            if(cheeseBoard[i][j].equals("Q"))
                return false;

        return true;
    }
}

复杂度

时间复杂度O(n^n)

[hx-code]

class Solution { public: vector v; unordered_map<int, int> m; int ans = 0; void dfs(int row, int n) { if (row > n) { ans++; return; } for (int j = 1; j <= n; j++) { if (m.find(j) == m.end()) { int condition = 1; for (int k = 1; k < row; k++) { if (k - v[k] == row - j || k + v[k] == row + j) { condition = 0; break; } } if (condition == 1) { v[row] = j; m[j]++; dfs(row + 1, n); v[row] = 0; m.erase(j); } } } } int totalNQueens(int n) { v.resize(n + 5); dfs(1, n); return ans; } };

[Alfie100]

题目连接： 52. N皇后 II https://leetcode-cn.com/problems/n-queens-ii/

解题思路

LeetCode—51. N 皇后 的姊妹问题，相比之下本题只需要记录方案数，要更为简单一些。

运用回溯的思想依次在第 $i\in [0, n-1]$ 行的第 $j\in [0, n-1]$ 列试探性地放置第 $i$ 个皇后：

判断能否在 $(i,j)$ 处放置皇后，

• 若能则记录下当前位置，并继续试探性地在第 $i+1$ 行放置第 $i+1$ 个皇后；
• 若不能，则继续试探在第 $i$ 行后面的位置，即 $(i,j+1)$处，放置第 $i$ 个皇后。

代码

class Solution:
    def totalNQueens(self, n: int) -> int:

        cols = set()    # 列
        diag1 = set()   # 主对角线：x-y = const
        diag2 = set()   # 次对角线：x+y = const
        self.ans = 0    # 记录方案数

        def backtrack(i, n):
            if i == n:      # 找到一种合适的方案
                self.ans += 1
            else:           # 在第 i 行 [0, n-1] 放置queen
                cnt = 0
                for j in range(n):  # 在 (i,j) （即i行j列）处放置queen
                    if j in cols or i-j in diag1 or i+j in diag2:
                        continue    # 不能满足放置的条件，继续试探下一个位置

                    # 可将第i个queen放在 (i,j) 位置处
                    cols.add(j)         # 记录下位置(i,j)已被占用
                    diag1.add(i-j)
                    diag2.add(i+j)

                    backtrack(i+1, n)   # 放置下一个queen，即第i+1个queen

                    cols.remove(j)      # 复原
                    diag1.remove(i-j)
                    diag2.remove(i+j)

        # 主程序开始
        backtrack(0, n)
        return self.ans

复杂度分析

• 时间复杂度：$O(n!)$。
• 空间复杂度：$O(n)$。

[tian-pengfei]

```c++
class Solution {

public:
    unordered_set<int> diagonal1;
    unordered_set<int> diagonal2;
    unordered_set<int> column_set;
    int n;
//    有点象中国象棋的车
    int totalNQueens(int n) {
        this->n=n;
       return dfs(0);
    }

    int dfs(int row){
        if(row == n)return 1;
        int re=0;
        for (int i = 0; i < n; ++i) {

            if (column_set.find(i)!=column_set.end())continue;

            if(diagonal1.find(row-i)!=diagonal1.end())continue;

            if(diagonal2.find(row+i)!=diagonal2.end())continue;

            column_set.insert(i);
            diagonal1.insert(row-i);
            diagonal2.insert(row+i);
            re+=dfs(row+1);
            column_set.erase(i);
            diagonal1.erase(row-i);
            diagonal2.erase(row+i);

        }
        return re;
    }
};