Print all possible solutions to N Queens problem

The N queens puzzle is the problem of placing N chess queens on an N × N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.


 
For example, for standard 8 × 8 chessboard below is one such configuration –

Q – – – – – – –
– – – – Q – – –
– – – – – – – Q
– – – – – Q – –
– – Q – – – – –
– – – – – – Q –
– Q – – – – – –
– – – Q – – – –

Note that the solution exist for all natural numbers n with the exception of n = 2 and n = 3.
 


 

We can solve this problem with the help of backtracking. The idea very simple. We start from the first row and place Queen in each square of the first row and recursively explore remaining rows to check if they leads to the solution or not. If current configuration doesn’t result in a solution, we backtrack. Before exploring any square, we ignore the square if two queens threaten each other.

 
C++ implementation –
 

Download   Run Code

Output:

Q – – – – – – –
– – – – Q – – –
– – – – – – – Q
– – – – – Q – –
– – Q – – – – –
– – – – – – Q –
– Q – – – – – –
– – – Q – – – –

Q – – – – – – –
– – – – – Q – –
– – – – – – – Q
– – Q – – – – –
– – – – – – Q –
– – – Q – – – –
– Q – – – – – –
– – – – Q – – –

and 90 other distinct solutions eight queens problem.

 
The time complexity of above backtacking solution is exponential.

 
Optimizations: The time complexity of above backtracking algorithm can be improved by using Branch and Bound. In backtracking solution we backtrack when we hit a dead end but in branch and bound, after building a partial solution, we figure out that there is no point going any deeper as we are going to hit a dead end. N Queen branch and bound solution is discussed here.

References:
https://en.wikipedia.org/wiki/Eight_queens_puzzle
https://developers.google.com/optimization/puzzles/queens
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Dpm Maurya
Guest
Dpm Maurya

Hey, any body run this code? i dont think
void nQueen(char mat[][N], int r, int c)
int c is required in above code!

AllergicToBitches
Guest
AllergicToBitches

Dude it is required. Check the solution again!!

wpDiscuz