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

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Dpm Maurya

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

Guest

It is indeed NOT required at all!

Guest

right, there is no need of int c here because it always going to be 0.

Guest

Can someone explain the backtracking procedure in this solution