Given an integer n, find all the possible ways to position n queens on an n×n chessboard so that no two queens attack each other.

A queen in chess can move horizontally, vertically, or diagonally.

Do solve the problem using recursion first even if you see some non-recursive approaches.

Input: 4

Output:

[[

"--q-",

"q---",

"---q",

"-q--"

], [

"-q--",

"---q",

"q---",

"--q-"

]]

There are two distinct ways four queens can be positioned on a 4×4 chessboard without attacking each other. The positions may appear in the output in any order. So the same two positions in different order would be another correct output.

Input: 2

Output: [ ]

No way to position two queens on a 2×2 chessboard without them attacking each other - so empty array.

The function has one input argument: n.

Output: The function must return a two-dimensional array of strings representing the arrangements. Size of the array must be m×n where m is the number of distinct arrangements. Length of each string must be n and the strings’ characters may be either ‘q’ (for a queen) or ‘-’ (for an empty position on the chessboard). Valid arrangements may appear in the output in any order.

• 1 <= n <= 12

Let us start from a brute force idea and improve upon it.

If we generate every possible arrangement of n queens on the board, check every one of them and return those that satisfy the criteria, that will solve the problem. (None of the sample solutions we provided implement this brute force idea.)

We could be putting queens on the board one by one (incrementally generating candidate solutions or candidates for short) and checking if the newly put queen attacks any one already on board. If it does, the candidate we generated thus far (including the position of this last queen) cannot be a part of a solution, so we must abandon it (and “backtrack”). This is the essence of the general backtracking algorithm. All three sample solutions we provided use backtracking.

There cannot be more than one queen in one row, obviously. So as we generate candidate solutions we put exactly one queen per row: first queen we put onto the 0-th row, and so on. All three sample solutions do this.

Let us do a few steps of the backtracking algorithm for n=4 manually just to feel it:

We start by putting the first queen at (0, 0):

q - - -

? ? ? ?

? ? ? ?

? ? ? ?

First two positions in the second row attack the first queen so we put the second queen at (1, 2) initially:

q - - -

- - q -

? ? ? ?

? ? ? ?

At this point no position in the third row gets us a valid candidate, so we abandon (1, 2) position of the second queen (“backtrack”) and try the next one, (1, 3):

q - - -

- - - q

? ? ? ?

? ? ? ?

Third queen can then be put to (2, 1) only:

q - - -

- - - q

- q - -

? ? ? ?

No position in the last row gives a valid solution at this point, so we must backtrack. There’s nothing left to try for the second and third queens so long as the first queen is at (0, 0) so we backtrack all the way to the first queen and try (0, 1) for it:

- q - -

? ? ? ?

? ? ? ?

? ? ? ?

The only one option for the second queen now is (1, 3):

- q - -

- - - q

? ? ? ?

? ? ? ?

Similarly, the only one option for the third queen is (2, 0):

- q - -

- - - q

q - - -

? ? ? ?

Finally, the only option for the last queen, (3, 2), gives us a valid solution:

- q - -

- - - q

q - - -

- - q -

We should store it, backtrack, and keep generating candidates to possibly find more solutions. In this case we will backtrack all the way back to the first queen and try (0, 2) position for it. And so on.

In all sample solutions the function for checking that is called is_safe().

naive_backtracking_solution simply checks, before putting a queen to a particular position, if there is already a queen on the same column or on any of the diagonals with it. Time complexity of such one check is O(n).

optimized_backtracking_solution1 and optimized_backtracking_solution2 make use of the following observation to reduce the time complexity of is_safe() to O(1). It is easy to keep track of columns that already have a queen on them, we can use a vector of booleans: col_occupied[col]=true if there is a queen in column col. Can something similar be done for the diagonals (and in constant time, too)? Turns out each one of the “bottom-left to top-right” diagonals (we will call them the “slash” diagonals) have a constant sum of coordinates, in other words, (row+col) is constant for any two positions on the same “slash” diagonal. For example, here is a 4×4 matrix of (row+col) values:

0 1 2 3

1 2 3 4

2 3 4 5

3 4 5 6

Similarly, (row-col) is constant for any two positions on the same “backslash” diagonal. It is convenient to add (n-1) to normalize and make all these values non-negative (so they can be an index of a vector in our implementation). Here is a 4×4 matrix of (row-col+n-1) values:

3 2 1 0

4 3 2 1

5 4 3 2

6 5 4 3

Now any time we put a queen somewhere, we mark its column and both diagonals “occupied”:

col_occupied[col] = true;

slash_diagonal_occupied[row + col] = true;

backslash_diagonal_occupied[row - col + n - 1] = true;

For any position (x, y) we can now check in constant time “if (slash_diagonal_occupied[x+y]) { ... }” and so on.

Now we know how to incrementally generate candidate solutions by placing queens on the board one by one, we also know how to efficiently check if a candidate is valid (and we must continue) or not (and we must backtrack). How can we incrementally generate all the candidate solutions?

For that we use recursion. In all three sample solutions we provided there is a recursive function called find_all_arrangements_util(). It’s called with the candidate solution generated so far and index of the row where it should try to put a queen. Function find_all_arrangements_util() tries to put a queen in every column of that row (using is_safe() to check if it should really try) and calls itself to handle the next row when is_safe() returns true. If all the n queens have been placed (that’s the base condition for recursion), the current candidate solution is a complete solution and must be stored to return as part of the answer.

Finally, there is one difference between optimized_backtracking_solution1 and optimized_backtracking_solution2. optimized_backtracking_solution1 stores candidate and final solutions in the form of the vector of strings (using O(n^2) space per solution). optimized_backtracking_solution2 just uses a vector of n integers (O(n) space): because there is exactly one queen in each row, “candidate[row]=col” is enough to store a solution. This problem asks to output complete two-dimensional arrays, so this optimization of optimized_backtracking_solution2 won’t bring any real benefit. In some other cases, e.g. if we were asked to output just the positions of the queens (and not the complete redundant boards), this auxiliary space optimization could be significant. optimized_backtracking_solution2 uses generate_output() function to convert the vectors of integers into the vectors of strings.

Exponential for all three sample solutions.

Exponential for all three sample solutions.

Exponential for all three sample solutions.