# 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.

## Java

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 backtracking 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:

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 🙂

Subscribe
Notify of
Guest
Bismeet

Can someone explain the backtracking procedure in this solution

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!

Guest
AllergicToBitches

Dude it is required. Check the solution again!!

Guest
HIAHIA

It is indeed NOT required at all!