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, the solution requires that no two queens share the same row, column, or diagonal.

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

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

Note that the solution exists for all natural numbers n, except for n = 2 and n = 3.

Practice this problem

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

The algorithm can be implemented as follows in C, Java, and Python:

C


Download  Run Code

Java


Download  Run Code

Python


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 to the eight queens problem.

The time complexity of the above backtracking solution is exponential.

 
Optimizations: The time complexity of the above backtracking algorithm can be improved using Branch and Bound. In a backtracking solution, we backtrack on hitting 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.

 
References:

1. https://en.wikipedia.org/wiki/Eight_queens_puzzle
2. https://developers.google.com/optimization/cp/queens