【Day 49 】2023-04-03 - 52. N 皇后 II

[azl397985856]

52. N 皇后 II

入选理由

暂无

题目地址

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

前置知识

• 回溯
• 深度优先遍历

  题目描述

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

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

示例 1：

![](https://p.ipic.vip/e9jfjh.jpg)

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

输入：n = 1 输出：1  

提示：

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

[Meisgithub]

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        backtrack(count, n, 0, 0, 0, 0);
        return count;
    }

    void backtrack(int &count, int n, int depth, int column, int diag1, int diag2)
    {
        if (depth == n)
        {
            count++;
            return;
        }
        int avalable = ((1 << n) - 1) & (~(column | diag1 | diag2));
        while (avalable)
        {
            int avalablePos = avalable & (-avalable);
            backtrack(count, n, depth + 1, column | avalablePos, (diag1 | avalablePos) >> 1, (diag2 | avalablePos) << 1);
            avalable = avalable & (avalable - 1);
        }
    }
};

[aswrise]

class Solution:
    result = 0
    def track(self, n, cur_row, col, row, obliqueL, obliqueR):
        for cur_col in range(n):
            index_obliqueL = n - cur_row + cur_col - 1
            index_obliqueR = cur_col + cur_row
            if 1 not in (col[cur_col] | row[cur_row] | \
            obliqueL[index_obliqueL] | obliqueR[index_obliqueR]):
                if cur_row == n - 1:
                    self.result += 1
                    return
                col[cur_col].add(1)
                row[cur_row].add(1)
                obliqueL[index_obliqueL].add(1)
                obliqueR[index_obliqueR].add(1)
                self.track(n, cur_row + 1, col, row, obliqueL, obliqueR)
                col[cur_col].remove(1)
                row[cur_row].remove(1)
                obliqueL[index_obliqueL].remove(1)
                obliqueR[index_obliqueR].remove(1)

    def totalNQueens(self, n):
        if n <= 0:
            return []
        col = []
        row = []
        obliqueL = []
        obliqueR = []
        for k in range(n):
            col.append(set())
            row.append(set())
        for r in range((n - 1) * 2 + 1):
            obliqueL.append(set())
            obliqueR.append(set())

        self.track(n, 0, col, row, obliqueL, obliqueR)
        return self.result

[Bochengwan]

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;
        }
    }
}

[LIMBO42]

grid[i] 代表第 i 行的棋子放在 grid[i] 列；
如何判断能放在哪一列：枚举 row - k 到 row + k，看相减的结果
```C++
class Solution {
public:
    int ans = 0;
    void dfs(vector<int> &grid, int row, vector<bool> &used) {
        if(row == grid.size()) {
            ans++;
            return;
        }
        int n = grid.size();
        // 代表i行的棋子在grid[i]列
        for(int j = 0; j < n; ++j) {

            if(used[j]) continue;
            bool flag = true;
            for(int k = 1; k < n; k++) {
                if(row - k >= 0) {
                    int num = abs(j - grid[row-k]);
                    if(grid[row-k] == -1) num = grid[row];
                    if(num == k) {
                        flag = false;
                        break;
                    }
                }
                if(row + k < n) {
                    int num = abs(j - grid[row+k]);
                    if(grid[row+k] == -1) num = grid[row];
                    if(num == k) {
                        flag = false;
                        break;
                    }
                }
            }
            if(flag == false) {
                continue;
            }

            used[j] = true;
            grid[row] = j;
            dfs(grid, row + 1, used);
            used[j] = false;
            grid[row] = -1;
        }
    }
    int totalNQueens(int n) {
        vector<int> grid(n, -1);
        vector<bool> used(n, false);
        dfs(grid, 0, used);
        return ans;

    }
};

[NorthSeacoder]

var totalNQueens = function(n) {
    let res = 0;
    const cols = new Set(), // 列
        diagDown = new Set(), // -> 右下对角线，行列差相等
        diagUp = new Set(); // -> 右上对角线，行列和相等

    const setQueen = (row, col) => {
        const down = col - row;
        const up = col + row;
        if (cols.has(col) || diagDown.has(down) || diagUp.has(up)) return false;
        cols.add(col);
        diagUp.add(up);
        diagDown.add(down);
        return true;
    };

    const unSetQueen = (row, col) => {
        const down = col - row;
        const up = col + row;
        cols.delete(col);
        diagUp.delete(up);
        diagDown.delete(down);
    };

    const dfs = (row) => {
        if (row === n) { // 如果已经放置了 n 个皇后，则合法解加 1
            res++;
        } else {
            for (let col = 0; col < n; col++) { // 遍历所有的列
                if (!setQueen(row, col)) continue; // 如果不能放置皇后，则跳过本次循环
                dfs(row + 1); // 继续放下一行皇后
                unSetQueen(row, col); // 回溯，撤销本次放置的皇后
            }
        }
    };

    dfs(0);
    return res;
};

• TC:O(n!)
• SC:O(n)

[Abby-xu]

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.res = 0
        self.dfs([-1]*n, 0)
        return self.res

    def dfs(self, nums, index):
        if index == len(nums):
            self.res += 1
            return #backtracking
        for i in range(len(nums)):
            nums[index] = i
            if self.valid(nums, index):
                self.dfs(nums, index+1)

    def valid(self, nums, n):
        for i in range(n):
            if nums[i] == nums[n] or abs(nums[n]-nums[i]) == n-i:
                return False
        return True

[chanceyliu]

代码

const backtrack = (
  n: number,
  row: number,
  columns: Set<any>,
  diagonals1: Set<any>,
  diagonals2: Set<any>
) => {
  if (row === n) {
    return 1;
  } else {
    let count = 0;
    for (let i = 0; i < n; i++) {
      if (columns.has(i)) {
        continue;
      }
      const diagonal1 = row - i;
      if (diagonals1.has(diagonal1)) {
        continue;
      }
      const diagonal2 = row + i;
      if (diagonals2.has(diagonal2)) {
        continue;
      }
      columns.add(i);
      diagonals1.add(diagonal1);
      diagonals2.add(diagonal2);
      count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
      columns.delete(i);
      diagonals1.delete(diagonal1);
      diagonals2.delete(diagonal2);
    }
    return count;
  }
};

function totalNQueens(n: number): number {
  const columns = new Set();
  const diagonals1 = new Set();
  const diagonals2 = new Set();
  return backtrack(n, 0, columns, diagonals1, diagonals2);
}

复杂度分析

• 时间复杂度：O(N!)
• 空间复杂度：O(N)

[linlizzz]

看了官方题解..

/**
 * @param {number} n
 * @return {number}
 * @param row 当前层
 * @param col 列
 * @param pie 左斜线
 * @param na 右斜线
 */
const totalNQueens = function (n) {
  let res = 0;
  const dfs = (n, row, col, pie, na) => {
    if (row >= n) {
      res++;
      return;
    }
    // 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
    // 也就是得到当前所有的空位
    let bits = ~(col | pie | na) & ((1 << n) - 1);
    while (bits) {
      // 取最低位的1
      let p = bits & -bits;
      // 把P位置上放入皇后
      bits = bits & (bits - 1);
      // row + 1 搜索下一行可能的位置
      // col ｜ p 目前所有放置皇后的列
      // (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
      dfs(n, row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
    }
  };
  dfs(n, 0, 0, 0, 0);
  return res;
};

[tzuikuo]

思路

回溯

代码

class Solution {
public:
    vector<vector<int>> board;
    vector<vector<int>> record;
    vector<int> step;
    int totalNQueens(int n) {

        for(int i=0;i<n;i++){
            vector<int> temp;
            for(int j=0;j<n;j++) temp.push_back(0);
            board.push_back(temp);
        }
        recur(0,n);

        return record.size();
    }
    void recur(int layer,int n){
        if(layer>=n&&step.size()==n){
            if(find(record.begin(),record.end(),step)==record.end())record.push_back(step);
            for(int i=0;i<n;i++){
                cout<<step[i]<<" ";
            }
            cout<<endl;
            return;
        }
        for(int i=0;i<n;i++){
            if(board[layer][i]==0){
                board[layer][i]=1;
                step.push_back(i);
                vector<vector<int>> flag(n,vector<int>(n));
                for(int j=1;j<n;j++){
                    if(layer+j<n&&board[layer+j][i]==0){
                       board[layer+j][i]=-1; 
                       flag[layer+j][i]=1;
                    }
                    if(i+j<n&&layer+j<n&&board[layer+j][i+j]==0){
                        board[layer+j][i+j]=-1;
                        flag[layer+j][i+j]=1;
                    }
                    if(i-j>=0&&layer+j<n&&board[layer+j][i-j]==0){
                        board[layer+j][i-j]=-1;
                        flag[layer+j][i-j]=1;
                    }
                }
                recur(layer+1,n);
                board[layer][i]=0;
                for(int j=1;j<n;j++){
                    if(layer+j<n&&flag[layer+j][i]==1){
                       board[layer+j][i]=0; 
                    }
                    if(i+j<n&&layer+j<n&&flag[layer+j][i+j]==1){
                        board[layer+j][i+j]=0;
                    }
                    if(i-j>=0&&layer+j<n&&flag[layer+j][i-j]==1){
                        board[layer+j][i-j]=0;
                    }
                }
                step.pop_back();
            }
        }
    }
};

复杂度分析 -时间 O(N!)

[FireHaoSky]

思路：回溯+dfs+位运算

代码：python

class Solution:
    def totalNQueens(self, n: int) -> int:
        def dfs(n, row, cols, left, right):
            if (row == n):
                return 1
            count = 0
            void_posisiont = (~(cols| left | right)) & ((1 << n) - 1)
            while void_posisiont != 0:
                now_position = void_posisiont & (-void_posisiont)
                void_posisiont &= (void_posisiont - 1)
                count += dfs(n, row+1, cols|now_position, (left|now_position) << 1, (right|now_position)>>1)
            return count

        return dfs(n, 0, 0, 0, 0)

复杂度分析：

"""
时间复杂度：O(n!)
空间复杂度：O(n!)
"""

[wangzh0114]

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;
        }
    }
};

• TC:O(N!)
• SC:O(N)

[harperz24]

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        dia1 = set()
        dia2 = set()

        def backtrack(row):
            if row == n:
                return 1

            count = 0
            for i in range(n):
                if i in cols or row - i in dia1 or row + i in dia2:
                    continue
                cols.add(i)
                dia1.add(row - i)
                dia2.add(row + i)
                count += backtrack(row + 1)

                cols.remove(i)
                dia1.remove(row - i)
                dia2.remove(row + i)
            return count

        return backtrack(0)

        # backtrack
        # time: O(n!)
        # space: O(n)

[aoxiangw]

class Solution:
    def totalNQueens(self, n: int) -> int:
        col = set()
        posDiag = set()
        negDiag = set()

        res = 0
        def backtrack(r):
            if r == n:
                nonlocal res
                res += 1
                return

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                backtrack(r + 1)
                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)

        backtrack(0)
        return res

Time, space: O(n!), O(n)

[bingzxy]

思路

回溯

代码

class Solution {
    public int totalNQueens(int n) {
        return solveNQueens(n).size();
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<> ();
        int[] cols = new int[n];
        solveNQueens(n, 0, ans, cols);
        return ans;
    }

    private void solveNQueens(int n, int row, List<List<String>> ans, int[] cols) {
        if (row == n) {
            List<String> oneAns = new ArrayList<> ();
            for (int i = 0; i < n; i++) {
                String tmp = "";
                for (int j = 0; j < n; j++) {
                    tmp += cols[i] == j ? "Q" : ".";
                }
                oneAns.add(tmp);
            }
            ans.add(oneAns);
            return;
        }

        for (int j = 0; j < n; j++) {
            if (canVisit(n, cols, row, j)) {
                cols[row] = j;
                solveNQueens(n, row + 1, ans, cols);
            }
        }
    }

    private boolean canVisit(int n, int[] cols, int row, int col) {
        int leftUp = col - 1, rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (cols[i] == col) return false;
            if (leftUp >= 0 && cols[i] == leftUp) return false;
            if (rightUp < n && cols[i] == rightUp) return false;
            leftUp--;rightUp++;
        }
        return true;
    }
}

复杂度分析

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

[bookyue]

TC: O(n!)
SC: O(n^2)

class Solution {
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');

        return nQueensBacktrack(n, 0, board);
    }

    private int nQueensBacktrack(int n, int row, char[][] board) {
        if (n == row) return 1;

        int count = 0;
        for (int col = 0; col < n && row < n; col++) {
            if (!feasible(n, board, row, col)) continue;

            board[row][col] = 'Q';
            count += nQueensBacktrack(n, row + 1, board);
            board[row][col] = '.';
        }

        return count;
    }

    private boolean feasible(int n, char[][] board, int row, int col) {
        for (int i = row - 1; i >= 0; i--)
            if (board[i][col] == 'Q') return false;

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
            if (board[i][j] == 'Q') return false;

        return true;
    }
}

[kyo-tom]

class Solution { public int totalNQueens(int n) { Set columns = new HashSet(); Set diagonals1 = new HashSet(); Set diagonals2 = new HashSet(); 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;
    }
}

}

[SoSo1105]

class Solution: def totalNQueens(self, n: int) -> int: cols = set() dia1 = set() dia2 = set()

    def backtrack(row):
        if row == n:
            return 1

        count = 0
        for i in range(n):
            if i in cols or row - i in dia1 or row + i in dia2:
                continue
            cols.add(i)
            dia1.add(row - i)
            dia2.add(row + i)
            count += backtrack(row + 1)

            cols.remove(i)
            dia1.remove(row - i)
            dia2.remove(row + i)
        return count

    return backtrack(0)

[lp1506947671]

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row: int) -> int:
            if row == n:
                return 1
            else:
                count = 0
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    count += backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                return count

        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        return backtrack(0)

复杂度分析

• 时间复杂度：由于我们需要枚举所有全排列情况，因此时间复杂度为 O(n!)
• 空间复杂度：递归调用栈的开销是 n，因此空间复杂度为 O(n)

[RestlessBreeze]

code

class Solution {
public:

    bool ok(int i, int j, vector<vector<int>>& path)
    {
        int m = 0;
        int n = 0;
        while (m < i)
        {
            if (path[m][j] == 1)
                return false;
            m++;
        }
        while (n < j)
        {
            if (path[i][n] == 1)
                return false;
            n++;
        }
        m = i - 1;
        n = j - 1;
        while (m >= 0 && n >= 0)
        {
            if (path[m][n] == 1)
                return false;
            m--;
            n--;
        }
        m = i - 1;
        n = j + 1;
        while (m >= 0 && n < path[0].size())
        {
            if(path[m][n] == 1)
                return false;
            m--;
            n++;
        }
        return true;
    }

    void backtracking(int i, vector<vector<int>>& path, int& res)
    {
        if (i == path[0].size())
        {
            res++;
            return;
        }
        for (int j = 0; j < path[0].size(); j++)
        {
            if (!ok(i, j, path))
                continue;
            path[i][j] = 1;
            backtracking(i + 1, path, res);
            path[i][j] = 0;
        }
    }

    int totalNQueens(int n) {
        vector<int> temp(n);
        vector<vector<int>> path(n, temp);
        int res = 0;
        backtracking(0, path, res);
        return res;
    }
};

[kangliqi1]

class Solution { public int totalNQueens(int n) { Set columns = new HashSet(); Set diagonals1 = new HashSet(); Set diagonals2 = new HashSet(); return backtrack(n, 0, columns, diagonals1, diagonals2); } public int backtrack(int n, int row, Set columns, Set diagonals1, Set 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; } } }

[huizsh]

/**
 * @param {number} n
 * @return {number}
 * @param row 当前层
 * @param col 列
 * @param pie 左斜线
 * @param na 右斜线
 */
const totalNQueens = function (n) {
  let res = 0;
  const dfs = (n, row, col, pie, na) => {
    if (row >= n) {
      res++;
      return;
    }
    // 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
    // 也就是得到当前所有的空位
    let bits = ~(col | pie | na) & ((1 << n) - 1);
    while (bits) {
      // 取最低位的1
      let p = bits & -bits;
      // 把P位置上放入皇后
      bits = bits & (bits - 1);
      // row + 1 搜索下一行可能的位置
      // col ｜ p 目前所有放置皇后的列
      // (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
      dfs(n, row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
    }
  };
  dfs(n, 0, 0, 0, 0);
  return res;
};

[kofzhang]

思路

回溯法，用的方法比较笨

复杂度

时间复杂度：O(n!) 空间复杂度：O(n^2)

代码

class Solution:
    def totalNQueens(self, n: int) -> int:
        board = [[0] * n for _ in range(n)]
        res = 0

        def helper(level):
            for i in range(n):
                if judge(level, i):
                    if level == n-1:
                        nonlocal res
                        res += 1
                        return
                    if level < n-1:
                        board[level][i] = 1
                        helper(level + 1)
                        board[level][i] = 0
            return

        def judge(level, index):

            # zong            
            for i in range(n):
                if board[i][index] == 1:
                    return False
            # xie            
            mi = min(level, index)
            startlevel = level - mi
            startindex = index - mi
            while startlevel < n and startindex < n:
                if board[startlevel][startindex] == 1:
                    return False

                startlevel += 1
                startindex += 1
            ma = min(level, n - index-1)
            startlevel = level - ma
            startindex = index + ma
            while startlevel < n and startindex >= 0:
                if board[startlevel][startindex] == 1:
                    return False

                startlevel += 1
                startindex -= 1
            return True

        helper(0)
        return res

[chocolate-emperor]

class Solution {
public:
    int col[10];
    int dia[20];
    int backdia[20];
    int res = 0;

    bool judge(int x, int y,int n){
        return (col[y]==0 && backdia[x+y]==0 && dia[n+y-x]==0);
    }

    void dfs(int curr,int n){
        if(curr == n)   {
            res+=1;
        }

        for(int j=0; j<n; j++){
            if(judge(curr,j,n)){
                col[j] = 1;
                backdia[curr+j]=1;
                dia[n+j-curr]=1;

                dfs(curr+1,n);

                col[j] = 0;
                backdia[curr+j]=0;
                dia[n+j-curr]=0;
            }
        }
    }

    int totalNQueens(int n) {
        if(n==1)    return 1;
        for(int i=0 ; i<n ; i++){
            col[i] = 0;
            dia[i] = 0;
            backdia[i] = 0;
        }
        dfs(0,n);
        return res;
    }
};

[CruiseYuGH]

class Solution: def totalNQueens(self, n: int) -> int: board = [[0] * n for _ in range(n)] res = 0

    def helper(level):
        for i in range(n):
            if judge(level, i):
                if level == n-1:
                    nonlocal res
                    res += 1
                    return
                if level < n-1:
                    board[level][i] = 1
                    helper(level + 1)
                    board[level][i] = 0
        return

    def judge(level, index):

        # zong            
        for i in range(n):
            if board[i][index] == 1:
                return False
        # xie            
        mi = min(level, index)
        startlevel = level - mi
        startindex = index - mi
        while startlevel < n and startindex < n:
            if board[startlevel][startindex] == 1:
                return False

            startlevel += 1
            startindex += 1
        ma = min(level, n - index-1)
        startlevel = level - ma
        startindex = index + ma
        while startlevel < n and startindex >= 0:
            if board[startlevel][startindex] == 1:
                return False

            startlevel += 1
            startindex -= 1
        return True

    helper(0)
    return res

[joemonkeylee]

思路

没写出来 mark

代码

  public int TotalNQueens(int n)
    {
        HashSet<int> columns = new HashSet<int>();
        HashSet<int> diagonals1 = new HashSet<int>();
        HashSet<int> diagonals2 = new HashSet<int>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, HashSet<int> columns, HashSet<int> diagonals1, HashSet<int> 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;
        }
    }

复杂度分析

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

[yingchehu]

class Solution:
    def __init__(self):
        self.ans = 0

    def totalNQueens(self, n: int) -> int:
        def dfs(n, row, col, pie, na):
            if row >= n:
                self.ans += 1
                return
            bits = ~(col | pie | na) & ((1 << n) - 1)
            while bits:
                p = bits & -bits
                bits = bits & (bits - 1)
                dfs(n, row + 1, col | p, (pie | p) << 1, (na | p) >> 1)

        dfs(n, 0, 0, 0, 0)
        return self.ans

[zhangyu1131]

class Solution {
public:
    int totalNQueens(int n) {
        vector<vector<int>> grid(n, vector<int>(n, 0)); // n*n的棋盘，放置皇后的格子填充1
        int res = 0;
        dfs(grid, 0, res);

        return res;
    }

private:
    void dfs(vector<vector<int>>& grid, int row_idx, int& res)
    {
        if (row_idx >= grid.size()) // 成功到最后，结束
        {
            ++res;
            return;
        }

        for (int i = 0; i < grid.size(); ++i)
        {
            // 对每一行的每一个点做判断，该位置是否能放置皇后
            bool can_put = judge(grid, row_idx, i);
            if (can_put)// 能放置
            {
                grid[row_idx][i] = 1;
                dfs(grid, row_idx + 1, res);
                grid[row_idx][i] = 0; // 回溯
            }
        }
    }

    bool judge(vector<vector<int>>& grid, int i, int j)
    {
        // 行不用检查，因为这种写法保证了每一行本来就只会有一个
        // 检查同一列
        int n = grid.size();
        for (int ii = 0; ii < n; ++ii)
        {
            if (grid[ii][j] == 1)
            {
                return false;
            }
        }
        // 检查左上到右下的对角线
        int ii = i - 1, jj = j - 1;
        while (ii >= 0 && jj >= 0)
        {
            if (grid[ii][jj] == 1)
            {
                return false;
            }
            --ii;
            --jj;
        }
        ii = i + 1, jj = j + 1;
        while (ii < n && jj < n)
        {
            if (grid[ii][jj] == 1)
            {
                return false;
            }
            ++ii;
            ++jj;
        }

        // 检查左下到右上对角线
        ii = i + 1, jj = j - 1;
        while (ii < n && jj >= 0)
        {
            if (grid[ii][jj] == 1)
            {
                return false;
            }
            ++ii;
            --jj;
        }
        ii = i - 1, jj = j + 1;
        while (ii >= 0 && jj < n)
        {
            if (grid[ii][jj] == 1)
            {
                return false;
            }
            --ii;
            ++jj;
        }

        return true;
    }
};

[JingYuZhou123]

/**
 * @param {number} n
 * @return {number}
 * @param row 当前层
 * @param col 列
 * @param pie 左斜线
 * @param na 右斜线
 */
const totalNQueens = function (n) {
  let res = 0;
  const dfs = (n, row, col, pie, na) => {
    if (row >= n) {
      res++;
      return;
    }
    // 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
    // 也就是得到当前所有的空位
    let bits = ~(col | pie | na) & ((1 << n) - 1);
    while (bits) {
      // 取最低位的1
      let p = bits & -bits;
      // 把P位置上放入皇后
      bits = bits & (bits - 1);
      // row + 1 搜索下一行可能的位置
      // col ｜ p 目前所有放置皇后的列
      // (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
      dfs(n, row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
    }
  };
  dfs(n, 0, 0, 0, 0);
  return res;
};

[Fuku-L]

代码

class Solution {
    public int totalNQueens(int n) {
      return backtrack(n, 0, 0, 0, 0);
    }
    public int backtrack(int n, int row, int col, int d1, int d2){
        if(row == n){
            return 1;
        } else {
            int count = 0;
            int availablePosition = ((1<<n) - 1) & (~(col | d1 | d2));
            while(availablePosition != 0){
                int position = availablePosition & (-availablePosition);
                availablePosition = availablePosition & (availablePosition - 1);
                count += backtrack(n, row+1, col|position, (d1|position)<<1, (d2|position)>>1);
            }
            return count;
        }
    }
}

复杂度分析

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

[AstrKing]

代码

class Solution {
    public int totalNQueens(int n) {
        return solveNQueens(n).size();
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<> ();
        int[] cols = new int[n];
        solveNQueens(n, 0, ans, cols);
        return ans;
    }

    private void solveNQueens(int n, int row, List<List<String>> ans, int[] cols) {
        if (row == n) {
            List<String> oneAns = new ArrayList<> ();
            for (int i = 0; i < n; i++) {
                String tmp = "";
                for (int j = 0; j < n; j++) {
                    tmp += cols[i] == j ? "Q" : ".";
                }
                oneAns.add(tmp);
            }
            ans.add(oneAns);
            return;
        }

        for (int j = 0; j < n; j++) {
            if (canVisit(n, cols, row, j)) {
                cols[row] = j;
                solveNQueens(n, row + 1, ans, cols);
            }
        }
    }

    private boolean canVisit(int n, int[] cols, int row, int col) {
        int leftUp = col - 1, rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (cols[i] == col) return false;
            if (leftUp >= 0 && cols[i] == leftUp) return false;
            if (rightUp < n && cols[i] == rightUp) return false;
            leftUp--;rightUp++;
        }
        return true;
    }
}

[X1AOX1A]

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

        def dfs(pre, i):
            nonlocal queen
            if i == n:
                queen += 1
                return
            for j in range(n):
                if j in col:
                    if i - j in right and i + j in left:
                        col.discard(j)
                        right.discard(i - j)
                        left.discard(i + j)
                        dfs(pre + [j], i + 1)
                        col.add(j)
                        right.add(i - j)
                        left.add(i + j)
            return

        col = set(list(range(n)))
        right = set(list(range(1 - n, n, 1)))
        left = set(list(range(2 * n)))
        queen = 0
        dfs([], 0)
        return queen

[Jetery]

const int N = 20;
class Solution {
public:
    bool row[N], col[N], dg[N], udg[N];
    int n, ans;

    void dfs(int x, int y, int k) {
        if (k > n) return ;
        if (y == n) y = 0, x ++;
        if (x == n) {
            if (k == n) ans++;
            return ;
        }
        dfs(x, y + 1, k);
        if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
            dfs(x, y + 1, k + 1);
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        }
    }

    int totalNQueens(int n) {
        this->n = n;
        dfs(0, 0, 0);
        return ans;
    }
};

[Lydia61]

# queen
class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        dia1 = set()
        dia2 = set()

        def backtrack(row):
            if row == n:
                return 1

            count = 0
            for i in range(n):
                if i in cols or row - i in dia1 or row + i in dia2:
                    continue
                cols.add(i)
                dia1.add(row - i)
                dia2.add(row + i)
                count += backtrack(row + 1)

                cols.remove(i)
                dia1.remove(row - i)
                dia2.remove(row + i)
            return count

        return backtrack(0)

[KrabbeJing]

class Solution:
    def totalNQueens(self, n: int) -> int:
        res = 0
        def dfs(n, row, col, left, right):
            if row == n:
                return 1
            else:
                res = 0
                # 将所有能放置皇后的位置0变成1
                bit = ~(right | col | left) & ((1<<n)-1)
                while bit:
                    # 取最低位的1，11100指的是第三位
                    p = bit & -bit
                    # 把最低位的1置为0，放上皇后
                    bit = bit & (bit - 1)
                    # col | p 目前所有放置皇后的列
                    # (left|p)<<1 目前皇后的左对角线
                    # (right|p)>>1 目前皇后的右对角线
                    res += dfs(n, row+1, col | p, (left|p)<<1, (right|p)>>1)
                return res
        return dfs(n, 0, 0, 0, 0)

[snmyj]

public int totalNQueens(int n) {
    List<Integer> ans = new ArrayList<>();
    backtrack(new ArrayList<Integer>(), ans, n);
    return ans.size();
}

private void backtrack(List<Integer> currentQueen, List<Integer> ans, int n) {
    if (currentQueen.size() == n) {
        ans.add(1);
        return;
    }
    for (int col = 0; col < n; col  ) {
        if (!currentQueen.contains(col)) {
            if (isDiagonalAttack(currentQueen, col)) {
                continue;
            }
            currentQueen.add(col);
            backtrack(currentQueen, ans, n);
            currentQueen.remove(currentQueen.size() - 1);
        }

    }

}

private boolean isDiagonalAttack(List<Integer> currentQueen, int i) {
    int current_row = currentQueen.size();
    int current_col = i;
    for (int row = 0; row < currentQueen.size(); row  ) {
        if (Math.abs(current_row - row) == Math.abs(current_col - currentQueen.get(row))) {
            return true;
        }
    }
    return false;
}

[JasonQiu]

• Bit manipulation

  class Solution:
  def totalNQueens(self, n: int) -> int:
      def dfs(row, col, diag1, diag2):
          if row == n:
              return 1
          count = 0
          available_pos = ((1 << n) - 1) & (~ (col | diag1 | diag2))
          while available_pos:
              position = available_pos & (-available_pos)
              available_pos = available_pos & (available_pos - 1)
              count += dfs(row + 1, col | position, (diag1 | position) << 1, (diag2 | position) >> 1)
          return count
  
      return dfs(0, 0, 0, 0)

  Time: O(n!) Space: O(n)

[jmaStella]

思路

backTracking 用index 来代表queen CheckisValid只需要check column 上面，左上，右上

代码

public int totalNQueens(int n) {
        List<Set> result = new ArrayList<>();
        backTrack(n, result, new HashSet<Integer>(), 0);
        //System.out.print(result);
        return result.size();
    }
    public void backTrack(int n, List<Set> result, HashSet<Integer> set,int row){
        if(row == n){
            result.add(new HashSet<>(set));
            return;
        }
        //column
        for(int i=0; i<n; i++){
            if(!isValid(row, i, n, set)){
                continue;
            }
            //HashSet<Integer> dupSet= new HashSet<Integer>(set);
            //dupSet.add(row*n+i);
            set.add(row*n+i);
            //System.out.print(set);
            backTrack(n, result, set, row+1);
            set.remove(row*n+i);

        }
    }
    public boolean isValid(int row, int col, int n, HashSet<Integer> set){
        //check column
        for(int i=0; i<=row; i++){
            if(set.contains(n*i+col)){
                return false;
            }
        }
        int cRow = row;
        int cCol = col;

        while(cRow>=0 && cCol>=0){
            if(set.contains(cRow*n+cCol)){
                return false;
            }
            cRow--;
            cCol--;
        }
        cRow = row;
        cCol = col;

        while(cRow>=0 && cCol<n){
            if(set.contains(cRow*n+cCol)){
                return false;
            }
            cRow--;
            cCol++;
        }
        return true;

    }

复杂度

时间 O(N!*N) 空间 O(N)