Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given an integer `n`

, find **all** 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.

```
{
"n": 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.

```
{
"n": 2
}
```

Output:

```
[
]
```

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

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.

Each string must be n characters long,
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.

Constraints:

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

How can we check if the queens attack each other?

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

.

**N Queen Problem Solution 1: Naive Backtracking** 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 backtrackingsolution1.py** and

`is_safe()`

to O(1). It is easy to keep track of columns that already have a queen on them, we can use a list of boolean values:
`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 list 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 backtrackingsolution1.py and optimizedbacktrackingsolution2.py**.

optimized*backtracking*solution1.py stores candidate and final
solutions in the form of the list of strings (using O(n^{2}) space per solution).

optimized*backtracking*solution2.py just uses a list of `n`

integers (using 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.py 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.py uses `generate_output()`

function to convert the lists of integers into the lists of strings.

Exponential for all three sample solutions.

Exponential for all three sample solutions.

Exponential for all three sample solutions.

```
/*
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
*/
const char queen = 'q';
const char no_queen = '-';
/*
Checking if we can place a queen at position [row][col]
without attacking other queens already on the board.
We place queens from top (0-th row) down, so we only
check for existing queens above the current one.
*/
bool is_safe(vector<string> &candidate, int row, int col, int n)
{
// Check the "backslash" diagonal.
int cur_row = row, cur_col = col;
while (cur_row >= 0 && cur_col >= 0)
{
if (candidate[cur_row--][cur_col--] == queen)
{
return false;
}
}
// Check column.
cur_row = row;
while (cur_row >= 0)
{
if (candidate[cur_row--][col] == queen)
{
return false;
}
}
// Check the "slash" diagonal.
cur_row = row, cur_col = col;
while (cur_row >= 0 && cur_col < n)
{
if (candidate[cur_row--][cur_col++] == queen)
{
return false;
}
}
return true;
}
// The recursive function.
void find_all_arrangements_util(vector<vector<string>> &solutions,
vector<string> &candidate, int n, int row)
{
// If all n queens are placed (is_safe() returned true for each queen),
// this is one of the solutions.
if (row == n)
{
// push_back() makes a (deep) copy; that is what we need.
solutions.push_back(candidate);
return;
}
// Try to place a queen in every column of current row:
for (int col = 0; col < n; col++)
{
if (is_safe(candidate, row, col, n))
{
// Place a queen at (row, col).
candidate[row][col] = queen;
// Try to place any more queens (from the next row down).
find_all_arrangements_util(solutions, candidate, n, row + 1);
// We have explored all the solutions with current value of "candidate";
// now we need to reset it in order to try the next candidate:
candidate[row][col] = no_queen;
}
}
}
vector<vector<string>> find_all_arrangements(int n)
{
vector<vector<string>> solutions;
string chessboard_empty_row(n, no_queen); // zero queens in a row.
vector<string> candidate(n, chessboard_empty_row); // zero queens on a board.
// Start with an empty board from the 0th row:
find_all_arrangements_util(solutions, candidate, n, 0);
return solutions;
}
```

```
"""
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
"""
QUEEN = 'q'
NO_QUEEN = '-'
def find_all_arrangements(n):
# list<string> for candidate arrangements; initially "empty board".
# This instance will be modified by the recursive function to try all possible arrangements.
candidate = [[NO_QUEEN] * n for _ in range(n)]
# list<string> for collecting valid arrangements, solutions.
solutions = []
# All three "occupied" vectors are initially initialized to false since the board is empty:
# n columns for n rows
col_occupied = [False] * n
# for n * n board there are 2*n-1 slash diagonals
slash_diagonal_occupied = [False] * (2*n-1)
# ... and 2*n-1 backslash diagonals.
backslash_diagonal_occupied = [False] * (2*n-1)
# Returns True if we can place a queen at position candidate[row][col].
def is_safe(row, col):
return not (col_occupied[col] or
slash_diagonal_occupied[row+col] or
backslash_diagonal_occupied[row-col+n-1])
# The recursive function.
def find_all_arrangements_util(candidate, row):
if row == n:
# make a deep copy and append to solutions
solutions.append([''.join(x) for x in candidate])
return
for col in range(0, n):
if is_safe(row, col):
candidate[row][col] = QUEEN
# mark the column and both diagonals as occupied
col_occupied[col] = True
slash_diagonal_occupied[row+col] = True
backslash_diagonal_occupied[row-col+n-1] = True
# Try to place any more queens (from the next row down).
find_all_arrangements_util(candidate, row+1)
# We have explored all the solutions with current value of "candidate";
# now we need to reset it in order to try the next candidate:
candidate[row][col] = NO_QUEEN
col_occupied[col] = False
slash_diagonal_occupied[row+col] = False
backslash_diagonal_occupied[row-col+n-1] = False
# Start with an empty board from the 0th row:
find_all_arrangements_util(candidate, 0)
return solutions
```

```
"""
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
"""
def find_all_arrangements(n):
"""
Any candidate solution or complete solution will have exactly
one queen in each row, so we can store the entire solution in
a one-dimensional vector of integers. For example, the following grid
--q-
q---
---q
-q--
has queens at positions (1, 2), (1, 0), (2, 3), (3, 1).
Using a vector, this can be represented as
candidate[0] = 2,
candidate[1] = 0,
candidate[2] = 3,
candidate[3] = 1
Initialized as "empty board", candidate instance will be modified
by the recursive function to try all possible arrangements.
"""
candidate = [None] * n
# For collecting valid arrangements; same format as candidates.
solutions = []
# All three "occupied" vectors are initially initialized to false since the board is empty:
# n columns for n rows
col_occupied = [False] * n
# for n * n board there are 2*n-1 slash diagonals
slash_diagonal_occupied = [False] * (2*n-1)
# ... and 2*n-1 backslash diagonals.
backslash_diagonal_occupied = [False] * (2*n-1)
# Returns True if we can place a queen at position (row, col).
def is_safe(row, col):
return not (col_occupied[col] or
slash_diagonal_occupied[row+col] or
backslash_diagonal_occupied[row-col+n-1])
# Converts solutions from list<int> into list<string>.
def generate_output(solutions):
output = []
for arr in solutions:
o = [['-'] * len(arr) for _ in range(len(arr))]
for r, c in enumerate(arr):
o[r][c] = 'q'
output.append([''.join(row) for row in o])
return output
# The recursive function.
def find_all_arrangements_util(candidate, row):
if row == n:
# make a copy and append to solutions
solutions.append([x for x in candidate])
return
for col in range(0, n):
if is_safe(row, col):
candidate[row] = col
# mark the column and both diagonals as occupied
col_occupied[col] = True
slash_diagonal_occupied[row+col] = True
backslash_diagonal_occupied[row-col+n-1] = True
# Try to place any more queens (from the next row down).
find_all_arrangements_util(candidate, row+1)
# We have explored all the solutions with current value of "candidate";
# now we need to reset it in order to try the next candidate:
col_occupied[col] = False
slash_diagonal_occupied[row+col] = False
backslash_diagonal_occupied[row-col+n-1] = False
# Start with an empty board from the 0th row:
find_all_arrangements_util(candidate, 0)
return generate_output(solutions)
```

We hope that these solutions to n queen problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given an integer `n`

, find **all** 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.

```
{
"n": 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.

```
{
"n": 2
}
```

Output:

```
[
]
```

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

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.

Each string must be n characters long,
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.

Constraints:

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

How can we check if the queens attack each other?

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

.

**N Queen Problem Solution 1: Naive Backtracking** 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 backtrackingsolution1.py** and

`is_safe()`

to O(1). It is easy to keep track of columns that already have a queen on them, we can use a list of boolean values:
`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 list 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 backtrackingsolution1.py and optimizedbacktrackingsolution2.py**.

optimized*backtracking*solution1.py stores candidate and final
solutions in the form of the list of strings (using O(n^{2}) space per solution).

optimized*backtracking*solution2.py just uses a list of `n`

integers (using 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.py 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.py uses `generate_output()`

function to convert the lists of integers into the lists of strings.

Exponential for all three sample solutions.

Exponential for all three sample solutions.

Exponential for all three sample solutions.

```
/*
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
*/
const char queen = 'q';
const char no_queen = '-';
/*
Checking if we can place a queen at position [row][col]
without attacking other queens already on the board.
We place queens from top (0-th row) down, so we only
check for existing queens above the current one.
*/
bool is_safe(vector<string> &candidate, int row, int col, int n)
{
// Check the "backslash" diagonal.
int cur_row = row, cur_col = col;
while (cur_row >= 0 && cur_col >= 0)
{
if (candidate[cur_row--][cur_col--] == queen)
{
return false;
}
}
// Check column.
cur_row = row;
while (cur_row >= 0)
{
if (candidate[cur_row--][col] == queen)
{
return false;
}
}
// Check the "slash" diagonal.
cur_row = row, cur_col = col;
while (cur_row >= 0 && cur_col < n)
{
if (candidate[cur_row--][cur_col++] == queen)
{
return false;
}
}
return true;
}
// The recursive function.
void find_all_arrangements_util(vector<vector<string>> &solutions,
vector<string> &candidate, int n, int row)
{
// If all n queens are placed (is_safe() returned true for each queen),
// this is one of the solutions.
if (row == n)
{
// push_back() makes a (deep) copy; that is what we need.
solutions.push_back(candidate);
return;
}
// Try to place a queen in every column of current row:
for (int col = 0; col < n; col++)
{
if (is_safe(candidate, row, col, n))
{
// Place a queen at (row, col).
candidate[row][col] = queen;
// Try to place any more queens (from the next row down).
find_all_arrangements_util(solutions, candidate, n, row + 1);
// We have explored all the solutions with current value of "candidate";
// now we need to reset it in order to try the next candidate:
candidate[row][col] = no_queen;
}
}
}
vector<vector<string>> find_all_arrangements(int n)
{
vector<vector<string>> solutions;
string chessboard_empty_row(n, no_queen); // zero queens in a row.
vector<string> candidate(n, chessboard_empty_row); // zero queens on a board.
// Start with an empty board from the 0th row:
find_all_arrangements_util(solutions, candidate, n, 0);
return solutions;
}
```

```
"""
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
"""
QUEEN = 'q'
NO_QUEEN = '-'
def find_all_arrangements(n):
# list<string> for candidate arrangements; initially "empty board".
# This instance will be modified by the recursive function to try all possible arrangements.
candidate = [[NO_QUEEN] * n for _ in range(n)]
# list<string> for collecting valid arrangements, solutions.
solutions = []
# All three "occupied" vectors are initially initialized to false since the board is empty:
# n columns for n rows
col_occupied = [False] * n
# for n * n board there are 2*n-1 slash diagonals
slash_diagonal_occupied = [False] * (2*n-1)
# ... and 2*n-1 backslash diagonals.
backslash_diagonal_occupied = [False] * (2*n-1)
# Returns True if we can place a queen at position candidate[row][col].
def is_safe(row, col):
return not (col_occupied[col] or
slash_diagonal_occupied[row+col] or
backslash_diagonal_occupied[row-col+n-1])
# The recursive function.
def find_all_arrangements_util(candidate, row):
if row == n:
# make a deep copy and append to solutions
solutions.append([''.join(x) for x in candidate])
return
for col in range(0, n):
if is_safe(row, col):
candidate[row][col] = QUEEN
# mark the column and both diagonals as occupied
col_occupied[col] = True
slash_diagonal_occupied[row+col] = True
backslash_diagonal_occupied[row-col+n-1] = True
# Try to place any more queens (from the next row down).
find_all_arrangements_util(candidate, row+1)
# We have explored all the solutions with current value of "candidate";
# now we need to reset it in order to try the next candidate:
candidate[row][col] = NO_QUEEN
col_occupied[col] = False
slash_diagonal_occupied[row+col] = False
backslash_diagonal_occupied[row-col+n-1] = False
# Start with an empty board from the 0th row:
find_all_arrangements_util(candidate, 0)
return solutions
```

```
"""
Asymptotic complexity in terms of the number of queens \`n\`:
* Time: Exponential, i.e. O(C^n) where C is a constant.
* Auxiliary space: Exponential.
* Total space: Exponential.
"""
def find_all_arrangements(n):
"""
Any candidate solution or complete solution will have exactly
one queen in each row, so we can store the entire solution in
a one-dimensional vector of integers. For example, the following grid
--q-
q---
---q
-q--
has queens at positions (1, 2), (1, 0), (2, 3), (3, 1).
Using a vector, this can be represented as
candidate[0] = 2,
candidate[1] = 0,
candidate[2] = 3,
candidate[3] = 1
Initialized as "empty board", candidate instance will be modified
by the recursive function to try all possible arrangements.
"""
candidate = [None] * n
# For collecting valid arrangements; same format as candidates.
solutions = []
# All three "occupied" vectors are initially initialized to false since the board is empty:
# n columns for n rows
col_occupied = [False] * n
# for n * n board there are 2*n-1 slash diagonals
slash_diagonal_occupied = [False] * (2*n-1)
# ... and 2*n-1 backslash diagonals.
backslash_diagonal_occupied = [False] * (2*n-1)
# Returns True if we can place a queen at position (row, col).
def is_safe(row, col):
return not (col_occupied[col] or
slash_diagonal_occupied[row+col] or
backslash_diagonal_occupied[row-col+n-1])
# Converts solutions from list<int> into list<string>.
def generate_output(solutions):
output = []
for arr in solutions:
o = [['-'] * len(arr) for _ in range(len(arr))]
for r, c in enumerate(arr):
o[r][c] = 'q'
output.append([''.join(row) for row in o])
return output
# The recursive function.
def find_all_arrangements_util(candidate, row):
if row == n:
# make a copy and append to solutions
solutions.append([x for x in candidate])
return
for col in range(0, n):
if is_safe(row, col):
candidate[row] = col
# mark the column and both diagonals as occupied
col_occupied[col] = True
slash_diagonal_occupied[row+col] = True
backslash_diagonal_occupied[row-col+n-1] = True
# Try to place any more queens (from the next row down).
find_all_arrangements_util(candidate, row+1)
# We have explored all the solutions with current value of "candidate";
# now we need to reset it in order to try the next candidate:
col_occupied[col] = False
slash_diagonal_occupied[row+col] = False
backslash_diagonal_occupied[row-col+n-1] = False
# Start with an empty board from the 0th row:
find_all_arrangements_util(candidate, 0)
return generate_output(solutions)
```

We hope that these solutions to n queen problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart