N Queen Problem – Backtracking

The N Queen Problem is a well known problem which can be solved using backtracking. In this problem we have N queens which are placed on N x N chessboard. We have to find position for each queen such that no two queens attack each other.




For example we have a chessboard of 5×5 and 5 queens. Below is the possible solution:

N Queen Problem

To represent the chess board we will use a matrix of size NxN where the value 0 in matrix represents empty space and 1 represents one of the queen location. So the above solution can be represented in the form of matrix as:

 1  0  0  0  0 
 0  0  0  1  0 
 0  1  0  0  0 
 0  0  0  0  1 
 0  0  1  0  0

Below is the program to solve N Queen Problem using backtracking.

Program


#include <iostream>

using namespace std;

#define N 5


void printMat(int mat[N][N])
{
    cout<<endl<<endl;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
           cout<<mat[i][j]<<" ";
    
        cout<<"\n";
    }
}

bool isSafe(int mat[N][N], int row, int col)
{
    int i,j;
    
    for(i=0;i<row;i++) 
      if(mat[i][col]) 
         return false; 

  for(i=row,j=col; i>=0 && j>=0 ; i--,j--)
    {
        if(mat[i][j])
          return false;
    }
    
    
    for(i=row,j=col;i>=0,j<N; i--,j++) 
      if(mat[i][j]) 
         return false; 

   return true; } 

 bool canSolve(int mat[N][N], int row){ 
  if(row >= N)
      return true;
    
    for(int i=0;i<N;i++)
    {
        if(isSafe(mat,row,i)){
           mat[row][i] = 1;
           
           if(canSolve(mat,row+1))
              return true;
           
           mat[row][i] = 0;
           
        }
        
        
    }
    
    return false;
    
}



int main()
{
    
    int mat[N][N] = {
        {0,0,0,0,0},
        {0,0,0,0,0},
        {0,0,0,0,0},
        {0,0,0,0,0},
        {0,0,0,0,0}
    };
    
    if(canSolve(mat,0))
       printMat(mat);
    else
      cout<<"Not Possible!";
    
 return 0;   
}

Output

0 1 0 0 0 
0 0 0 0 1 
0 0 1 0 0 
1 0 0 0 0 
0 0 0 1 0

Leave a Reply

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