N Queen Problem ( Backtracking)

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

For example, following is a solution for 8 Queen problem.

 

Naive Algorithm:

 Generate all possible configurations of queens on board and print a configuration that satisfies the given constraints.

Backtracking Algorithm:

The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we move to previous column and find other possible position for the previously placed queen.

1) Start in the leftmost column
2) If all queens are placed i.e. fill_count = no of queens

   Print the board

3) Try all rows in the current column. 

    Do following for every tried row.
    a) If the queen can be placed safely in this row then mark this [row, 
        column] as part of the solution and recursively check if placing  
        queen here leads to a solution.

    b) If placing queen in [row, column] leads to a solution then  print the board

    c) If placing queen doesn't lead to a solution then unmark this [row, 
        column] (Backtrack) and go to step (a) to try other rows.
4) If all rows have been tried and nothing worked,trigger 
    backtracking.

  

 Output for 4 queens:

Implementation of Backtracking solution (c++) :

Download the code here: Nqueens.cpp

#include<iostream>

#include<conio.h>
using namespace std;

int a[100][100],fill_count=0,filled,start=0,row_chk=0,n;
int row=0,col=0;
int sum_i_j,sub_i_j;     // sum and difference of row and col
int i,j,k,l;                     //all counters for the loop

void print_table();
void initial();
void mark_danger();
void fill_queen();
void rem_mark();

int main()
{
 cout<<"Enter the no of queen and the board size: ";
 cin>>n;
 initial();
 while(fill_count!=n)
 {
     fill_queen();
    rem_mark();
    mark_danger();
   }
rem_mark();
print_table();
}

// print the board
void print_table()
{
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cout<<a[i][j]<<"   ";
        }
    cout<<"\n\n";
    }
    cout<<"\n";
}

//initialize the array elements to 0
void initial()
{
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            a[i][j]=0;
        }
    }
}
//for filling the postition of the queen
void fill_queen()
{
    filled=0;

      for(row=start;row<n;row++)
      {
          if(a[row][col]!=2)
              {
            a[row][col]=1;
             fill_count=fill_count+1;       //calculating the no of queens on the board
              col=col+1;                          //move to next column
              start=0;                     
              filled=1;
            break;
            }
     }

     if(filled==0)
     {
            col=col-1;                       //moving one column backward if there is no possible position
            for(row=0;row<n;row++)
             {  
              if(a[row][col]==1 && row_chk<n)
              {
                  row_chk=row;
                a[row][col]=0;
               fill_count=fill_count-1;       
                row_chk=row+1;
                start=row_chk;               
                break;
             }
             }
         }

       if(row_chk>=n)               //start again from the col 0 and the next row( rowchk +1)
        {
            start=0;
            row_chk=0;
            col=col-1;
            for(row=0;row<n;row++)
             {  
              if(a[row][col]==1 && row_chk<n)
              {
                  row_chk=row;
                a[row][col]=0;
               fill_count=fill_count-1;
                row_chk=row+1;
                start=row_chk;
                break;
             }
        }
    }
}

//for marking the location where queens can capture each other with integer 2

void mark_danger()

{
   
    for(i=0;i<n;i++)           // Row
    {
        for(j=0;j<n;j++)     // Columns
        {
          
            //for calculating the sum and the difference of row and column
            if(a[i][j]==1)
            {
                for(k=0;k<n;k++)
                {
                    if(a[k][j]==0)
                    {
                    a[k][j]=2;
                    }
              
                    if(a[i][k]==0)
                    {
                    a[i][k]=2;
                    }
                    sum_i_j=i+j;
                    sub_i_j=i-j;
                }
              
          
                for(k=0;k<n;k++)
                {
                    for(l=0;l<n;l++)
                        {
                        if(k+l==sum_i_j || k-l==sub_i_j)
                        {
                            if(k!=i && l!=j)
                            {
                            a[k][l]=2;
                            }
                        }
                        }
                    }
            }
   
        }

    }
}

//for removing the marked locations in array

void rem_mark()

{
for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==2)
            {
            a[i][j]=0;  
            }
        }
    }
}