N Queen LeetCode Problem

 

N Queen Problem

N Queen Problem is the leetcode question of placing N chess queens on an NxN

Chessboard in order that no queens assault every different, for which answers exist for all herbal numbers n besides n=2 and n=3. An answer calls for that no queens percentage of the identical row, column, or diagonal. It is the greater trendy shape of the preliminary Eight queens problem, in which we want to discover positions for eight Queens on an eight×eight chessboard. If you're inquisitive about java packages for different board video games like Sudoku Solver, Sudoku Checker, Snake N Lader, and Tic Tac Toe, you could test out my posts withinside the Board Games section. N Queen's Problem may be solved through the usage of a recursive backtracking algorithm. For different Backtracking algorithms, test my posts below the tag Backtracking.

What Is Backtracking Algorithm?

In backtracking algorithms, you attempt to construct an answer one step at a time. If a few steps it will become clear that the cutting-edge direction you are on can't cause an answer, you cross lower back to the preceding step (back off) and pick a one-of-a-kind direction. Briefly, when you exhaust all of your alternatives at a sure step you cross your lower back.

Think of a labyrinth or maze – how do you discover a manner from the front to an exit? Once you attain a useless end, you should back off. But back off to where? to the preceding preference point. Backtracking is likewise called Depth First Search.

Approach to solve N-Queen Problem Using Recursion Backtracking 

Since our board is four×four, our recursion can be four degrees deep.

At the 0th-degree recursion, we located the 0th Queen at the 0th row.

At the first degree of recursion, we location the first queen at the 1st row such that she does now no longer assault the 0th queen.

At the 2d degree of recursion, we location the 2d queen at the 2d row such that she does now no longer assault the first and 0th queen and so on.

At any factor in time, if we can't discover a molecular for a queen on that row, we go back fake to the calling characteristic and that degree of recursion will then attempt to location the queen on the following to be had mobileular of that row. If that does not work out then that characteristic itself goes to go back fake to the calling characteristic above it and so on.

In the grid/matrix of n*n, we will place the queen at different places accordingly to find the right position using backtracking.

C++ Code

// here we have to place queens on chessboard

// we do it using backtracking and recursion

#include<bits/stdc++.h>

using namespace std;

bool isSafe(int** arr, int x, int y, int n){

    for(int row=0; row<=x; row++){

        if(arr[row][y]==1){

            return false;

        }

    }

    int row=x;

    int col=y;

    while(row>=0 && col>=0){

        if(arr[row][col]==1){

            return false;

        }

        row--;

        col--;

    }

    row=x;

    col=y;

    while(row>=0 && col<n){

        if(arr[row][col]==1){

            return false;

        }

        row--;

        col++;

    }

    return true;

}

bool nQueen(int** arr, int x, int n){

    if(x>=n){

        return true;

    }

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

        if(isSafe(arr,x,col,n)){

            arr[x][col]=1;

            if(nQueen(arr,x+1,n)){

                return true;

            }

            arr[x][col]=0; //backtracking

        }

    }

    return false;

}

int main(){

    int n;

    cin>>n;

    int** arr=new int*[n];

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

        arr[i]=new int[n];

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

            arr[i][j]=0;

        }

    }

    if(nQueen(arr,0,n)){

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

       

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

            cout<<arr[i][j]<<" ";

        }cout<<endl;

    }

    }

    return 0;

}

Time Complexity for this question is exponential due to recursive calls and the backtracking set of rules.

Space Complexity is O(n) due to the fact withinside the worst case, our recursion could be N-degree deep for an NxN board.