52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

• q is queens on same col
• diagonal is queens on diagonal ways like ↘
• anti diagonal is queens on reverse diagonal ways like ↙

check queen is available to put on board[cur][i]
if (q | diagonal | antiDiagonal) & (1<<i) is not 0 it means queen is not possible to put on board[cur][i]

C++ code

class Solution {
    int res = 0;

    int dfs(int n, int cur = 0, int q = 0, int diagonal = 0, int antiDiagonal = 0) {
        if(cur == n) return ++res;
        for(int i = 0; i < n; i++) {
            if((q & (1<<i)) || (diagonal & (1<<i)) || (antiDiagonal & (1<<i))) continue;
            dfs(n, cur + 1, q ^ (1<<i), (diagonal ^ (1<<i)) << 1, (antiDiagonal ^ (1<<i)) >> 1);
        }
        return res;
    }
public:
    int totalNQueens(int n) {
        return dfs(n);
    }
};

java Code

class Solution {
    private int res = 0;
    public int totalNQueens(int n) {
        return dfs(0, n, 0, 0, 0);
    }

    private int dfs(int cur, int n, int q, int diagonal, int antiDiagonal) {
        if(cur == n) return ++res;
        for(int i = 0; i < n; i++) {
            if((q & (1<<i)) > 0 || (diagonal & (1<<i)) > 0|| (antiDiagonal & (1<<i)) > 0) continue;
            dfs(cur + 1, n, q ^ (1<<i), (diagonal ^ (1<<i)) << 1, (antiDiagonal ^ (1<<i)) >> 1);
        }
        return res;
    }
}

python Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        return self.dfs(n)
    
    def dfs(self, n, cur = 0, q = 0, diagonal = 0, antiDiagonal = 0):
        if cur == n: return 1
        res = 0
        for i in range(n):
            if q & (1<<i) or diagonal & (1<<i) or antiDiagonal & (1<<i): continue
            res += self.dfs(n, cur + 1, q ^ (1<<i), (diagonal ^ (1<<i)) << 1, (antiDiagonal ^ (1<<i)) >> 1);
        return res