N Queen Problem

N Queen Problem Using Backtracking Explained

N Queen Problem

In N Queen Problem, Given a square of size N*N. You have to place 1 Queen in each row, such that no queen can attack any other Queen placed in Square, we use backtracking for this

N Queen Problem

Above Square is of 4*4 size and we show the places where I placed the Queen’s so no Two queens Attack Each other.

N Queen Problem Algorithm using BackTracking–

Read this algorithm by making 4*4 Chess Board

The first thing we think is, we place our first Queen on (0,0) i.e first row and first column now,

Step – 1

We place the second Queen on (1,0) i.e second row and first column and if it is clashing with our previous placed queen then we move next column of the same row, i.e (1,1), and if this position is also clashing we move our second queen to (1,2) and we keep incrementing until we found a safe position

Step – 2

Now, If we can not find any Place in the row to place our queen, what should I do then. Yes, you think right, we move our previous placed queen to one step further in the same row, this is where I use BackTracking. I go to our backstage and increment 1 then I proceed further

In 4*4 Square

If we follow the above algorithm from the start

Position of first Queen – (0,0)

Position of second Queen – (1,2)

Hence, we see that there is no place where we placed our third queen, so we move our second Queen to one step further in the same row,

Now,

Position of First Queen – (0,0)

Position of Second Queen – (1,3) [We move our second queen to +1 in the same row]

Now, we see that again there is no any place where we placed our third queen, so we move our second Queen to one step further but there is also no any place where we move our second queen,

So we move our first Queen to (0,1) and start again as we start above.

From following the above steps final position is

Position of First Queen – (0,1)

Position of Second Queen – (1,3)

Position of Third Queen – (2,0)

Position of Fourth Queen – (3,2)

Now, We know the n queen problem using backtracking algorithm, we only need is code. Try Yourself and then Come Back

  1. We placed our Queen in (0,0) and mark the cell to -1,
  2. By placing the second Queen we check where the value of a column of the same row, diagonal’s cell is not -1 and if we not find any place where -1 is not present we placed our queen there and then go for the third queen
  3. If we did not find any place to place our queen, we increase our position and then again check for the same row and it’s a column
  4. If we did not find any position, we mark our previous placed queen to 0 and increase the position of our previous placed queen
  5. Finally, repeat until we can’t find our position and exit;

 

#include<iostream>
using namespace std;

void print(int a[10][10],int n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
bool check(int a[10][10],int x,int y,int n){
for(int i=x-1;i>=0;i--)

{
if(a[i][y]==1)

return false;
}
for(int i=x-1,j=y-1;i>=0 && j>=0;i--,j--){
if(a[i][j]==1)

return false;
}
for(int i=x-1,j=y+1;i>=0 && j<n;i--,j++){
if(a[i][j]==1)

return false;
}
return true;
}
void PlacedNQUeend(int a[10][10],int n,int i)
{
if(i==n){
print(a,n);
return;
}
for(int j=0;j<n;j++)

{
if(check(a,i,j,n))

{
a[i][j]=1;
PlacedNQUeend(a,n,i+1);
a[i][j]=0;
}
}
return;
}

void placeNQueens(int n)
{
int a[10][10];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=0;
}
}
PlacedNQUeend(a,n,0);
}

int main(){
int n;
cin >> n ;
placeNQueens(n);

}
Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

Leave a Comment

Your email address will not be published. Required fields are marked *