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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment