N-Queens II Problem Solution

N-Queens II Problem: 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.

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

N-Queens II Problem Solution

Problem Solution In Python

class Solution:
    def __init__(self):
        self.res = 0
        
    def totalNQueens(self, n: int) -> int:
        def BT(cur_row, n, queens):
            if cur_row == n:
                self.res += 1
                return
            for cur_col in range(n):
                good = True
                for q in queens:
                    if cur_col == q[1] or abs(q[0] - cur_row) == abs(q[1] - cur_col):
                        good = False
                        break
                if good:
                    queens.append((cur_row, cur_col))
                    BT(cur_row+1, n, queens)
                    queens.pop()
                    
        queens = []
        BT(0, n, queens)
        return self.res

Problem Solution In Java

class Solution {
    int count=0;
    public int totalNQueens(int n) {
        if(n==1)
            return 1;
        if(n==0)
            return 0;
        char board[][]=new char[n][n];
        nqueens(n,0,board);
        return count;
    }
    boolean isSafe(int row,int i,int n,char[][]board){
        
        for(int r=1;r<n;r++){
        if(row-r>=0)
        if(board[row-r][i]=='Q')
            return false;
        }
        for(int r=1;r<n;r++){
            if(row-r>=0&&i-r>=0)
        if(board[row-r][i-r]=='Q')
            return false;
            }
        for(int r=1,k=1;r<n&&k<n;r++,k++){
            if(row-r>=0&&i+k<n)
                if(board[row-r][i+k]=='Q')
                    return false;
        }
        return true;
    }
    void nqueens(int n,int row,char[][]board){
        if(row==n){
            count++;
            return;
        }
        for(int i=0;i<n;i++){
            if(isSafe(row,i,n,board)){
                board[row][i]='Q';
                nqueens(n,row+1,board);
                board[row][i]='.';
            }
        }
        
        
    }
   
}

Problem Solution In C++

typedef vector<bool> vb;
class Solution {
    vector<vb> dp;
    void whatTheFuck(int &ans,int k,int &n){
        if(k==n){
            ++ans;
            return;
        }
        for(int i=0;i<n;++i) if(dp[0][i] && dp[1][k+i] && dp[2][n+k-i]){
            dp[0][i] = dp[1][k+i] = dp[2][n+k-i] = false;
            whatTheFuck(ans,k+1,n);
            dp[0][i] = dp[1][k+i] = dp[2][n+k-i] = true;
        }
    }
public:
    int totalNQueens(int n) {
        dp = vector<vb>(3,vb(2*n+1,true));
        int ans;
        whatTheFuck(ans,0,n);
        return ans;
    }
};

Problem Solution In C

void DFS(bool** flag,int* count,int deep,int n)
{
    int i,j;
    deep++;
    if(deep==n)
    {
        (*count)++;
        return;
    }
    for(i=0;i<n;i++)
    {
        if(!flag[1][i]&&!flag[2][i+deep]&&!flag[3][deep-i+n-1])
        {
            flag[1][i]=true;
            flag[2][i+deep]=true;
            flag[3][deep-i+n-1]=true;
            DFS(flag,count,deep,n);
            flag[1][i]=false;
            flag[2][i+deep]=false;
            flag[3][deep-i+n-1]=false;
        }
    }
    return;
}
int totalNQueens(int n) {
    bool** flag;
    char*** Queen;
    int i,*returnSize;
    flag=(bool**)malloc(sizeof(bool*)*4);
    flag[1]=(bool*)malloc(sizeof(bool)*9);
    flag[2]=(bool*)malloc(sizeof(bool)*17);
    flag[3]=(bool*)malloc(sizeof(bool)*17);
    returnSize=(int*)malloc(sizeof(int*));
    for(i=0;i<9;i++)
    {
        flag[1][i]=false;
    }
    for(i=0;i<17;i++)
    {
        flag[2][i]=false;
        flag[3][i]=false;
    }
    DFS(flag,returnSize,-1,n);
    return *returnSize;
}