N Queen Problem Using Backtracking

N Queen Problem

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 queen Attack Each other.

N Queen Problem Algorithm –

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 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 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 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 steps further in same row, this is where I use BackTracking. I go to our back stage and increment 1 then I procced further

In 4*4 Square

If we follow above algorithm from start

Position of first Queen – (0,0)

Position of second Queen – (1,2)

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

Now,

Position of First Queen – (0,0)

Position of Second Queen – (1,3) [We move our second queen to +1 in 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 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 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 second Queen we check where value of column of 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 third queen
  3. If we did not find any place to place our queen , we increase our position and then again check for same row and it’s  column
  4. If we did not find any position, we mark our previous placed queen to 0 and increase 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);

}

Tagged : /

Leave a Reply

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