8 Queens Problem

8 Queen problem is a problem in which we have to place 8 Queens on 8x8 chessboard such that no two Queens attack each other.For placing the queens Backtrack Algorithm is used.Let us know first what is backtrack algorithm.

Backtrack Algorithm : Backtrack algorithms uses a incremental technique to arrive at a final solution.It will take the candidate as valid and check all the constraints,if the solution is possible then it moves forward or else it will abandons it when it determines that solution is not possible taking the present candidate.

How backtracking is helpful in the case of 8 Queens problem??

We will be going to place all the Queens in columns one by one from the leftmost column.When we will be placing the queens in the column we will check the constraints like if there is another queen in the row or column or diagonally.If we find a row that is valid and we can place a queen in that then we will take that row and column as a part of the solution.But if we cannot find such row and column then we backtrack and return false.

Algorithm : 

1) Start with the leftmost column
2) If all the queens are placed in right position return True.
3) Try out all the rows in  the present column.If the queen can be safely placed in that row then mark this row and column as a part of the solution and recursively check that by placing the queen in that position will lead to the valid solution.
4) If placing queen in that particular row column results in a valid solution after applying recursion then return True
5) If placing queen in that particular row column does not lead to a valid solution then return False and check for next possibility.
6) If all the rows are tried for the present column and nothing worked then backtrack and return False.

Program :

int main()
{
int chess[8][8]={ {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,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,0,0,0,0,0,0},
      {0,0,0,0,0,0,0,0},
};
if(!8queenproblem(chess,0))    /*If solution does not exist return false */
return false;
}
bool 8queenproblem(int c[8][8],col)
{
if(col>=8)    /*If all Queens are placed */
return true;
for(int i=0;i<8;i++)   /*Try each rows one by one*/
{
if(valid(c,i,col))        /*if valid then make it 1*/
{
c[i][col]=1;
if(8queenproblem(c,col+1))  /*If results in valid solution after recursion then return true*/
return true;
c[i][col]=0;                         /*If not then make it again 0 and backtrack*/
}
}
return false;                      
}
bool valid(int c[8][8],int row,int col)
{
for(int i=0;i<col;i++)   /* Check rows on left side of present column*/
{
if(c[row][i])
return false;

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)  /* Check upper diagonal on left side */
    {
        if (c[i][j])
            return false;
    }

   
    for (i = row, j = col; j >= 0 && i < 8; i++, j--) /* Check lower diagonal on left side */
    {
        if (c[i][j])
            return false;
    }

    return true;

}
}

Here is one of the solution of 8 Queen problem.