【Day 49 】2022-12-19 - 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 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

[FlipN9]

/**
    优化: 可以用二进制 优化 int[] state
*/  
class Solution {
    public int totalNQueens(int n) {
        return solve(n, 0, 0, 0, 0);
    }

    public int solve(int n, int row, int cols, int diag1, int diag2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            /**
                (1 << n) - 1        生成了 n 个 1, 
                ~(col | ld | rd)    分别代表了列及两个斜线的放置情况, 这里的1表示的是不能放置皇后
            */
            int availablePos = ((1 << n) - 1) & (~(cols | diag1 | diag2));

            while (availablePos != 0) {     // 说明bits中还有1存在，就说明遍历还没有完成
                int pos = availablePos & (-availablePos);           // 找到 最后一位1 的位置
                availablePos = availablePos & (availablePos - 1);   // 获得把最后一位 1 变成 0 之后的 availablePos
                count += solve(n, row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1);     // cols | pos: 把所有放置皇后的列都计算出来了
            }
            return count;
        }
    }
}

class Solution1 {
    int N;
    int res;

    public int totalNQueens(int n) {
        this.N = n;
        int[] state = new int[n];   
        backtrack(0, state);
        return res;
    }

    // 一行行 fill, 如果一个 col valid, 那就填下一行
    private void backtrack(int row, int[] state) {
        if (row == N) {
            res++;
            return;
        }
        for (int col = 0; col < N; col++) {
            if (isValid(row, col, state)) {
                state[row] = col;
                backtrack(row + 1, state);
            }
        }
    }

    private boolean isValid(int row, int col, int[] state) {
        for (int i = 0; i < row; i++) { // loop all options in the previous rows
            if (state[i] == col || Math.abs(col - state[i]) == row - i)
                return false;
        }
        return true;
    }
}

[guowei0223]

先定义一个helper function 检查该点是否符合条件（查找左上，右上，和列），不需要查找row，因为后续会简化用row来控制搜索进程。 最后用回溯方法检查每一个点是否符合条件，如果符合，则放入Q

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.res = 0
        board = [["."] * n for i in range(n)]
        def isValid(board, row, col):
            #check column
            for i in range(len(board)):
                if board[i][col] == "Q":
                    return False

            #check left corner
            i = row -1
            j = col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == "Q":
                    return False
                i -= 1
                j -= 1

            #check right corner
            i = row - 1
            j = col + 1
            while i >= 0 and j < len(board):
                if board[i][j] == "Q":
                    return False
                i -= 1
                j += 1
            return True

        def backtrack(board, row, n):
            if row == n:
                self.res += 1
            for col in range(n):
                if not isValid(board, row, col):
                    continue
                board[row][col] = "Q"
                backtrack(board, row+1, n)
                board[row][col] = "."
        backtrack(board, 0, n)
        return self.res

TC O(N!) SCO(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

[testplm]

class Solution(object):
    def totalNQueens(self, n):
        row = col = ans = 0
        queens = [-1]*n
        columns = [True] * n + [False]
        back = [True] * n * 2
        forward = [True] * n * 2
        while True:
            if columns[col] and back[col - row + n] and forward[col + row]:
                queens[row] = col
                columns[col] = back[col - row + n] = forward[col + row] = False
                row += 1
                col = 0
            else:
                if row == n or col == n:
                    if row == n:
                        ans += 1
                    if row == 0:
                        return ans
                    row -= 1
                    col = queens[row]
                    columns[col] = back[col - row + n] = forward[col + row] = True
                col += 1

[syh-coder]

struct hashTable { int key; UT_hash_handle hh; };

struct hashTable* find(struct hashTable* hashtable, int ikey) { struct hashTable tmp = NULL; HASH_FIND_INT(*hashtable, &ikey, tmp); return tmp; }

void insert(struct hashTable* hashtable, int ikey) { struct hashTable tmp = NULL; HASH_FIND_INT(hashtable, &ikey, tmp); if (tmp == NULL) { tmp = malloc(sizeof(struct hashTable)); tmp->key = ikey; HASH_ADD_INT(hashtable, key, tmp); } }

void erase(struct hashTable* hashtable, int ikey) { struct hashTable tmp = NULL; HASH_FIND_INT(hashtable, &ikey, tmp); if (tmp != NULL) { HASH_DEL(hashtable, tmp); free(tmp); } }

struct hashTable columns, diagonals1, *diagonals2;

int backtrack(int n, int row) { if (row == n) { return 1; } else { int count = 0; for (int i = 0; i < n; i++) { if (find(&columns, i) != NULL) { continue; } int diagonal1 = row - i; if (find(&diagonals1, diagonal1) != NULL) { continue; } int diagonal2 = row + i; if (find(&diagonals2, diagonal2) != NULL) { continue; } insert(&columns, i); insert(&diagonals1, diagonal1); insert(&diagonals2, diagonal2); count += backtrack(n, row + 1); erase(&columns, i); erase(&diagonals1, diagonal1); erase(&diagonals2, diagonal2); } return count; } }

int totalNQueens(int n) { columns = diagonals1 = diagonals2 = NULL; return backtrack(n, 0); }

[mayloveless]

思路

同8皇后1，遍历每个row，试探col，增加一个看看是否满足，然后再去掉。满足条件的计数+1

代码

var totalNQueens = function(n) {
    let result = 0;
    let board = Array(n).fill().map(() => Array(n).fill('.'))
    let backtrack = row => {
        if (row == n) {
            result++;
            return
        }
        for (let col = 0; col < n; ++col) {
            if (isOk(board, n, row, col)) {
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
            }
        }
    }
    backtrack(0)
    return result
};

let isOk = (board, n, row, col) => {
    for (let i = 0; i < n; i++) {// 检查列是否冲突
        if (board[i][col] == 'Q') {
            return false
        }
    }
    let i = row - 1
    let j = col + 1
    while (i >= 0 && j < n) {// 检查右上对⻆线是否有冲突
        if (board[i][j] == 'Q') {
            return false
        }
        i--
        j++
    }
    i = row - 1
    j = col - 1
    while (i >= 0 && j >= 0) {// 检查左上对⻆线是否有冲突
        if (board[i][j] == 'Q') {
            return false
        }
        i--
        j--
    }
    return true
}

复杂度

时间：O(n!) 空间：O(n)

[yin02]

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

[bwspsu]

(referring to solution)

/**
 * @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;
};

[snmyj]

public int totalNQueens(int n) {
    List<Integer> ans = new ArrayList<>();
    boolean[] cols = new boolean[n]; 
    boolean[] d1 = new boolean[2 * n]; 
    boolean[] d2 = new boolean[2 * n]; 
   return backtrack(0, cols, d1, d2, n, 0);
}

private int backtrack(int row, boolean[] cols, boolean[] d1, boolean[] d2, int n, int count) { 
    if (row == n) {
        count++;
    } else {
        for (int col = 0; col < n; col++) {
            int id1 = row - col + n; 
            int id2 = row + col;
            if (cols[col] || d1[id1] || d2[id2])
                continue;
            cols[col] = true;
            d1[id1] = true;
            d2[id2] = true;
            count = backtrack(row + 1, cols, d1, d2, n, count);
            cols[col] = false;
            d1[id1] = false;
            d2[id2] = false;
        }

    }
    return count;
}

[zywang0]

public int totalNQueens(int n) {
    List<Integer> ans = new ArrayList<>();
    boolean[] cols = new boolean[n]; 
    boolean[] d1 = new boolean[2 * n]; 
    boolean[] d2 = new boolean[2 * n]; 
   return backtrack(0, cols, d1, d2, n, 0);
}

private int backtrack(int row, boolean[] cols, boolean[] d1, boolean[] d2, int n, int count) { 
    if (row == n) {
        count++;
    } else {
        for (int col = 0; col < n; col++) {
            int id1 = row - col + n; 
            int id2 = row + col;
            if (cols[col] || d1[id1] || d2[id2])
                continue;
            cols[col] = true;
            d1[id1] = true;
            d2[id2] = true;
            count = backtrack(row + 1, cols, d1, d2, n, count);
            cols[col] = false;
            d1[id1] = false;
            d2[id2] = false;
        }

    }
    return count;
}

[bookyue]

code

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

[chenming-cao]

解题思路

回溯+集合。用三个集合分别记录列和两条对角线信息。每行放置一个皇后，找到合适的列，保证该列没有其他皇后，并且两个对角线方向没有其他皇后。如果n个皇后放置完毕则方案数加1。判断是否在同一对角线上比较难想。

代码

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> cols = new HashSet<>(); // check column index. Direction: |
        Set<Integer> diag1 = new HashSet<>(); // check diagonal. Direction: \  row1 - col1 == row2 - col2
        Set<Integer> diag2 = new HashSet<>(); // check diagonal. Direction: /  row1 + col1 == row2 + cols
        return backtrack(n, 0, cols, diag1, diag2);
    }

    private int backtrack(int n, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
        if (row == n) return 1;
        int count = 0;
        // there can only be one queen in each row.
        // check each column position in the current row.
        for (int col = 0; col < n; col++) {
            if (!cols.contains(col) && !diag1.contains(row - col) && !diag2.contains(row + col)) {
                cols.add(col);
                diag1.add(row - col);
                diag2.add(row + col);
                count += backtrack(n, row + 1, cols, diag1, diag2);
                // backtrack
                cols.remove(col);
                diag1.remove(row - col);
                diag2.remove(row + col);
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：O(n!)，排列问题，第一行n个选择，第二行n - 1个选择，。。。
• 空间复杂度：O(n)，递归层数为n，同时集合大小也为n

[Jetery]

代码 (cpp)

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

[Elsa-zhang]

''' 52. N皇后 II
    思路: 任何两个皇后都不能处于同一条横行、纵行或斜线上。
    # diagonals1 左斜线
    # diagonals2 右斜线
'''

class Solution:
    def totalNQueens(self, n: int):
        def dfs(row, columns, diagonals1, diagonals2):
            if row == n:
                return 1
            else:
                count = 0
                avaliable = (~(columns|diagonals1|diagonals2)) & ((1<<n)-1)
                while avaliable:
                    position = avaliable & (-avaliable)   # 最低位的 1 的位置
                    avaliable = avaliable & (avaliable-1) # 最低位的 1 置成 0
                    count += dfs(row+1, columns|position, (diagonals1|position) << 1, (diagonals2|position) >> 1)
                return count

        return dfs(0,0,0,0)

[buer1121]

class Solution: def totalNQueens(self, n: int) -> int: if not n: return [] board = [['.'] * n for _ in range(n)] res = [] def isVaild(board,row, col):

判断同一列是否冲突

        for i in range(len(board)):
            if board[i][col] == 'Q':
                return False
        # 判断左上角是否冲突
        i = row -1
        j = col -1
        while i>=0 and j>=0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # 判断右上角是否冲突
        i = row - 1
        j = col + 1
        while i>=0 and j < len(board):
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def backtrack(board, row, n):
        # 如果走到最后一行，说明已经找到一个解
        if row == n:
            temp_res = []
            for temp in board:
                temp_str = "".join(temp)
                temp_res.append(temp_str)
            res.append(temp_res)
        for col in range(n):
            if not isVaild(board, row, col):
                continue
            board[row][col] = 'Q'
            backtrack(board, row+1, n)
            board[row][col] = '.'
    backtrack(board, 0, n)
    return len(res)

[RestlessBreeze]

代码

class Solution {
public:
    int totalNQueens(int n) {
        unordered_set<int> columns, diagonals1, diagonals2;
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    int backtrack(int n, int row, unordered_set<int>& columns, unordered_set<int>& diagonals1, unordered_set<int>& diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.find(i) != columns.end()) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.find(diagonal1) != diagonals1.end()) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.find(diagonal2) != diagonals2.end()) {
                    continue;
                }
                columns.insert(i);
                diagonals1.insert(diagonal1);
                diagonals2.insert(diagonal2);
                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.erase(i);
                diagonals1.erase(diagonal1);
                diagonals2.erase(diagonal2);
            }
            return count;
        }
    }
};

[954545647]

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
  let res = 0;
  const board = new Array(n)
  for (let i = 0; i < n; i++) {
    // 棋盘的初始化
    board[i] = new Array(n).fill('.')
  }
  const isValid = (row, col) => {
    for (let i = 0; i < row; i++) {
      // 之前的行
      for (let j = 0; j < n; j++) {
        // 所有的列
        if (
          board[i][j] == 'Q' && // 发现了皇后，并且和自己同列/对角线
          (j == col || i + j === row + col || i - j === row - col)
        ) {
          return false // 不是合法的选择
        }
      }
    }
    return true
  }
  const helper = row => {
    // 放置当前行的皇后
    if (row == n) {
        res++
    }
    for (let col = 0; col < n; col++) {
      // 枚举出所有选择
      if (isValid(row, col)) {
        // 剪掉无效的选择
        board[row][col] = 'Q' // 作出选择，放置皇后
        helper(row + 1) // 继续选择，往下递归
        board[row][col] = '.' // 撤销当前选择
      }
    }
  }
  helper(0) // 从第0行开始放置
  return res
};

[wtdcai]

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)

[klspta]

打表可行？

class Solution {
    public int totalNQueens(int n) {
        int[] result = {1,0,0,2,10,4,40,92,352};
        return result[n - 1];
    }
}

[chiehw]

class Solution {
public:
    int totalNQueens(int n) {
        unordered_set<int> columns, diagonals1, diagonals2;
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    int backtrack(int n, int row, unordered_set<int>& columns, unordered_set<int>& diagonals1, unordered_set<int>& diagonals2) {
        if (row == n) {
            return 1;
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (columns.find(i) != columns.end()) {
                continue;
            }
            int diagonal1 = row - i;
            if (diagonals1.find(diagonal1) != diagonals1.end()) {
                continue;
            }
            int diagonal2 = row + i;
            if (diagonals2.find(diagonal2) != diagonals2.end()) {
                continue;
            }
            columns.insert(i);
            diagonals1.insert(diagonal1);
            diagonals2.insert(diagonal2);
            count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
            columns.erase(i);
            diagonals1.erase(diagonal1);
            diagonals2.erase(diagonal2);
        }
        return count;
    }
};

[klspta]

class Solution {
    public int totalNQueens(int n) {
        int[] rows = new int[n];
        return process(0, rows, n);
    }

    private int process(int i, int[] rows, int n){
        if(i == n){
            return 1;
        }
        int res = 0;
        for(int j = 0; j < n; j++){
            if(isValid(rows, i, j)){
                rows[i] = j;
                res += process(i + 1, rows, n);
            }
        }
        return res;
    }

    private boolean isValid(int[] rows, int i, int j){
        for(int k = 0; k < i; k++){
            if(rows[k] == j || Math.abs(i - k) == Math.abs(j - rows[k])){
                return false;
            }
        }
        return true;
    }
}

[MaylingLin]

思路

---

每次获得可以放置皇后的位置中的最低位，并将该位的值置成 0，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。

代码

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)

复杂度

---

• Time: $O(N!)$，N为皇后个数
• Space: $O(N)$

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int totalNQueens(int n) {
Set<Integer> columns = new HashSet<>();
        Set<Integer> dis1 = new HashSet<>();
        Set<Integer> dis2 = new HashSet<>();
        return dfs( n, 0, columns, dis1, dis2);
    }

    public int dfs(int n, int row, Set<Integer> columns, Set<Integer> dis1, Set<Integer> dis2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int di1 = row - i;
                if (dis1.contains(di1)) {
                    continue;
                }
                int di2 = row + i;
                if (dis2.contains(di2)) {
                    continue;
                }
                columns.add(i);
                dis1.add(di1);
                dis2.add(di2);
                count += dfs(n, row+1, columns, dis1, dis2);
                columns.remove(i);
                dis1.remove(di1);
                dis2.remove(di2);
            }
            return count;
        }
    }
}

[whoam-challenge]

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)

[Alexno1no2]

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(r):
            if r == n:
                result.append(1)
                return
            for i in range(n):
                if i in columns or r - i in diagonal1 or r + i in diagonal2:
                    continue
                #当前列及正反对角线都没有皇后时；再进行放置皇后
                columns.append(i)           #将放置皇后的列添加到用来存放已放置过皇后的数组中
                diagonal1.append(r - i)     #将放置皇后所在的反对角线坐标的值添加到用来存放相应的数组里记录
                diagonal2.append(r + i)     #将放置皇后所在的正对角线坐标的值添加到用来存放相应的数组里记录
                backtrack(r + 1)            #对下一行进行放置
                columns.pop()               #回溯，将之前添加的pop出
                diagonal1.pop()             #回溯，将之前添加的pop出
                diagonal2.pop()             #回溯，将之前添加的pop出
        result = []
        columns, diagonal1, diagonal2 = [], [], []
        row = ["."] * n
        backtrack(0)
        return len(result)

[paopaohua]

class Solution {
    public int totalNQueens(int n) {
        int[] rows = new int[n];
        return process(0, rows, n);
    }

    private int process(int i, int[] rows, int n){
        if(i == n){
            return 1;
        }
        int res = 0;
        for(int j = 0; j < n; j++){
            if(isValid(rows, i, j)){
                rows[i] = j;
                res += process(i + 1, rows, n);
            }
        }
        return res;
    }

    private boolean isValid(int[] rows, int i, int j){
        for(int k = 0; k < i; k++){
            if(rows[k] == j || Math.abs(i - k) == Math.abs(j - rows[k])){
                return false;
            }
        }
        return true;
    }
}

[tiandao043]

class Solution {
public:
    int res=0;
    // x & -x ：得到最低位的 1 代表除最后一位 1 保留，其他位全部为 0

//  x & (x-1)：清零最低位的 1 代表将最后一位 1 变成 0

// x & ((1 << n) - 1)：将 x 最高位至第 n 位(含)清零
    void dfs(int n,int row,int col,int pie,int na){
        if(row>=n){
            res++;
            return;
        }
        int bits= ~(col | pie | na) & ((1 << n) - 1);
        while(bits){
            int p=bits&-bits;
            bits=bits&(bits-1);
            dfs(n,row+1,col|p,(pie|p)<<1,(na|p)>>1);
        }
    }
    int totalNQueens(int n) {
        dfs(n,0,0,0,0);
        return res;
    }
};