N Queen Problem Problem Statement

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.

Example One

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

Example Two

{
"n": 2
}

Output:

[
]

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

Notes

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

optimizedbacktrackingsolution1.py and optimizedbacktrackingsolution2.py 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 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 optimizedbacktrackingsolution1.py and optimizedbacktrackingsolution2.py.

optimizedbacktrackingsolution1.py stores candidate and final solutions in the form of the list of strings (using O(n²) space per solution).

optimizedbacktrackingsolution2.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 optimizedbacktrackingsolution2.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. optimizedbacktrackingsolution2.py uses generate_output() function to convert the lists of integers into the lists of strings.

naivebacktrackingsolution.cpp

Time Complexity

Exponential for all three sample solutions.

Auxiliary Space Used

Exponential for all three sample solutions.

Space Complexity

Exponential for all three sample solutions.

Code For N Queen Problem Solution 1: Naive Backtracking

/*
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;
}

N Queen Problem Solution 2: 1St Optimized Backtracking

Code For N Queen Problem Solution 2: 1St Optimized Backtracking

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

N Queen Problem Solution 3: 2Nd Optimized Backtracking

Code For N Queen Problem Solution 3: 2Nd Optimized Backtracking

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