N-Queen Problem[EXPLAINED]

3 min readNov 20, 2019

“Success is stumbling from failure to failure with no loss of enthusiasm.”
― Winston S. Churchill

Hello, fellow algorithm lovers. Recently I have been watching a lot of chess game recaps by grandmasters of the likes Magnus Carlsen, Anand, etc. I realized while watching one of their many games(if interested this game was called the game of the decade which was played amongst those two grandmasters) that there is a fascinating problem known as the N-Queen Problem that is taught to computer science students to better explain Backtracking in algorithms.

Understanding the meaning of backtracking

Backtracking is one of the many algorithmic paradigms. Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point while computing for the solution.

A space state tree is constructed for the computation of the solution. All the possible answers are computed and the feasible ones are added to the tree as a node one at a time(the node added is known as a promising node).

The famous N-Queen Problem

The problem statement goes something like this: There is an N*N chessboard and there are N queens. Each queen should be placed in such a way that none of the queens are attacked by the other queens.

Solution

We check for each column one by one and start placing one queen at a time. If we can find an optimal solution then we add it to the answer by marking that column number and row number. If we are not able to find an optimal solution then we backtrack to the previous state and if we can’t place the queen anywhere then return not possible or false.

Algorithm

1) Start in the leftmost column
2) If all queens are placed
    return true
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 the queen in [row, column] leads to
       a solution then return true.
    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.
3) If all rows have been tried and nothing worked,
   return false to trigger backtracking.