NQueen Problem

Solution :-

#include <iostream>
using namespace std;

bool isSafe(int board[][10],int i,int j){
    ///check for upper columns
    for(int row=0;row<i;row++){
        if(board[row][j]==1){
            return false;
        }
    }
    ///check for upper left diagonal
    int x=i;
    int y=j;
    while(x>=0&&y>=0){
        if(board[x][y]==1){
            return false;
        }
        x--;
        y--;
    }
    ///check for upper right diagonal
    x=i;
    y=j;
    while(x>=0&&y>=0){
        if(board[x][y]==1){
            return false;
        }
        x--;
        y++;
    }
    return true;
}

bool nqueenProblem(int board[][10],int i,int n){
    ///Base case when every queen place safely in every rows
    if(i==n){
        ///print the queens at it's safe position
        ///And return true to indicate that ever queen in every row is in right place
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==1)
                    cout<<" Q ";
                else{
                    cout<<" _ ";
                }
            }
            cout<<endl;
        }
        cout<<endl;
        return true;
    }
    ///Recursive call
    for(int j=0;j<n;j++){
        if(isSafe(board,i,j)){
            board[i][j]=1; ///place the queen after checking the ith and jth position

            ///check next n-i rows that queen are safely placed after place the queen in ith row
            bool isNextQueenSafe=nqueenProblem(board,i+1,n);

            ///if next n-i rows are safe then place the queen don't further check other columns of ith row
            if(isNextQueenSafe){
                return true;
            }

            ///if n-i rows are not safe first remove the queen at ith and jth column and then check other column of ith row
            board[i][j]=0; ///Backtracking
        }
    }
}

int main() {
    int n;
    cin>>n;
    int board[10][10]={0};
    nqueenProblem(board,0,n);
    return 0;
}

Contact us





JDoodle for WordPress
Scroll Up