In this video, implementation of N-Queen Problem using Bitsets and Backtracking has been discussed. This is an optimised approach than the normal backtracking approach. Here we don’t need to write is Safe Positon Function which works in linear time instead we use bitsets which work in O(1) time.

Optimised Bitset Code to count all configurations

#include<iostream>
#include<bitset>
using namespace std;

bitset<30> col,d1,d2;

void solve(int r,int n,int &ans){
    if(r==n){ ans++; return;}

    for(int c=0;c<n;c++){
        if( !col[c] && !d1[r-c+n-1] && !d2[r+c]){
            col[c] = d1[r-c+n-1] = d2[r+c] = 1;
            solve(r+1,n,ans);
            col[c] = d1[r-c+n-1] = d2[r+c] = 0;
        }
    }
}

int main(){
    int n;
    cin>>n;
    int ans = 0;
    solve(0,n,ans);
    cout<<ans<<endl;

return 0;
}

Bitset Code to Print all configurations

#include<iostream>
#include<bitset>
using namespace std;

bitset<30> col,d1,d2;
int board[15][15] = {0};


void printboard(int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


void solve(int r,int n,int &ans){
    if(r==n){ ans++; printboard(n); return; }
    for(int c=0;c<n;c++){
        if(!col[c] && !d1[r-c+n-1] && !d2[r+c]){

            col[c] = d1[r-c+n-1] = d2[r+c] = board[r][c] = 1;
            solve(r+1,n,ans);
            col[c] = d1[r-c+n-1] = d2[r+c] = board[r][c] = 0;
        }
    }
}

int main(){
    int n;
    cin>>n;
    int ans=0;
    solve(0,n,ans);
    cout<<ans<<endl;

}

Normal Backtracking Code To Print One Configuration

#include<iostream>
using namespace std;


bool canPlace(char board[][100],int row,int col,int n){

    ///Row mein queen to nahi h
    for(int i=0;i<n;i++){
        if(board[row][i]=='Q'){
            return false;
        }
    }
    ///Col mein queen to nahi h
    for(int i=0;i<n;i++){
        if(board[i][col]=='Q'){
            return false;
        }
    }
    /// Diagonals
    ///Top Left
    int i=row,j=col;
    while(i>=0&&j>=0){
        if(board[i][j]=='Q'){
            return false;
        }
        i--;
        j--;
    }
    ///Top Right
    i=row,j=col;
    while(i>=0 && j<n){
        if(board[i][j]=='Q'){
            return false;
        }
        i--;
        j++;
    }

    return true;
}



bool solveNQueen(char board[][100],int n,int row){
    if(row==n){
        ///Print the board
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                cout<<board[x][y]<<" ";
            }
            cout<<endl;

        }

        return true;
    }

    ///Rec Case

    ///Try to place the queen in the current row

    for(int pos=0;pos<n;pos++){

            if(canPlace(board,row,pos,n)){
                    board[row][pos]='Q';

                    bool agliQueenRakhPayeKya = solveNQueen(board,n,row+1);
                    if(agliQueenRakhPayeKya==true){
                        return true;
                    }

                    board[row][pos]='.';
            }

    }
    ///Backtracking
    return false;
}

int main(){

    char board[100][100];

    int n;
    cin>>n;

    for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                board[x][y]='.';
            }

        }
    solveNQueen(board,n,0);


return 0;
}

Thank you for Reading !

Keep Coding, Keep Building !

For more such informative videos, subscribe us on Youtube