Jobs

Interviews

Discussions

N-Queens II

Hard

Asked by:

More companies

73 views

Topics:

ArraysRecursionBacktracking

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 9

Try coding it in LeetCode

N-Queens II

Hard

Asked by:

73 views

Topics:

ArraysRecursionBacktracking

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 9

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `n`? Are there any constraints on the size of the board?
Is 'distinct solutions' defined as unique board configurations, or are rotations/reflections of the same configuration considered distinct?
If n is 0, should I return 1 (representing an empty board as a solution) or 0 (representing no possible placement)?
Can I assume that the input `n` will always be a non-negative integer?
Could you provide a small example (e.g., n=3 or n=4) and the corresponding expected output to clarify the problem further?

Brute Force Solution

Approach

The brute force approach tries every single possible arrangement of queens on the board. We systematically explore each configuration, and if a configuration is valid (no queens attack each other), we count it. This approach guarantees finding all solutions, but it's very inefficient.

Here's how the algorithm would work step-by-step:

Start by placing a queen in the first column, trying every possible row in that column.
For each position of the first queen, try placing a queen in the second column, again trying every possible row.
Continue this process column by column, placing one queen per column.
Before placing a queen, always check if the current queen placement conflicts with any previously placed queens (i.e., if they attack each other).
If there is a conflict, skip that placement and try the next row in the current column.
If you reach the last column and successfully place a queen without any conflicts, you have found one valid arrangement. Increment the solution counter.
After exploring one possibility fully, backtrack. This means removing the queen from the last column and trying the next row in that column. Continue until all possible arrangements have been checked in the last column.
Repeat the backtracking process for all columns to explore all combinations of queen placements.
The final count of valid arrangements represents the total number of solutions.

Code Implementation

def total_n_queens(n):
    number_of_solutions = 0
    queens_positions = []

    def is_safe(row_index, column_index):
        for previous_row_index, previous_column_index in enumerate(queens_positions):
            if column_index == previous_column_index or \
               abs(column_index - previous_column_index) == abs(row_index - previous_row_index):
                return False
        return True

    def solve_n_queens_recursive(row_index):
        nonlocal number_of_solutions

        # Base case: all queens are placed
        if row_index == n:
            number_of_solutions += 1
            return

        for column_index in range(n):
            # Check if this position is safe
            if is_safe(row_index, column_index):

                # Place the queen
                queens_positions.append(column_index)

                # Recursively solve for the next row
                solve_n_queens_recursive(row_index + 1)

                # Backtrack: remove the queen
                queens_positions.pop()

    # Initiate the recursive process
    solve_n_queens_recursive(0)

    return number_of_solutions

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach explores all possible placements of n queens on an n x n board. In the first column, there are n possible rows to place a queen. In the second column, there are also n possible rows, and so on, for each of the n columns. This leads to n * n * ... * n (n times) = n^n possible arrangements. The conflict check (checking if the queens attack each other) can be done in O(n) time in each placement. However, the dominant factor is the exploration of all possible arrangements, which is n^n, but this isn't tight. A better, although less precise, estimate is O(n!). Since after picking the first row, the number of choices decreases. The first row will have n possible choices, the next row can have at most n-1 choices, and so on. Therefore the complexity is approximately O(n!).

Space Complexity

O(N) – The space complexity is dominated by the recursion depth, which can go as deep as N, where N is the size of the board. In each recursive call, we're essentially exploring placing a queen in each column. The recursion stack stores the state of each call (row placements). Therefore, the auxiliary space used by the call stack is proportional to the board size N. Also, we can consider that the approach described in the problem description could be implemented using data structures to track placed queens which would contribute to O(N) space. Therefore, the space complexity is O(N).

Optimal Solution

Approach

We want to find the number of ways to place queens on a board so they don't attack each other. The efficient way is to explore possible queen placements one row at a time and stop exploring a path as soon as we find an attack.

Here's how the algorithm would work step-by-step:

Start with an empty board.
Try placing a queen in the first available column of the first row.
Check if this placement creates any conflicts (i.e., if the new queen is attacked by any existing queen).
If there's a conflict, try placing the queen in the next available column of the same row.
If there's no conflict, move to the next row and repeat the queen placement process.
If you reach the last row and have successfully placed a queen without conflicts, you've found one valid solution; record it.
After recording a solution (or if you run out of valid columns to try in a row), backtrack. This means you remove the queen from the current row and go back to the previous row to try placing its queen in a different column.
Keep exploring all possible paths until you've exhausted all options in the first row. The total number of valid solutions recorded is the answer.

Code Implementation

def total_n_queens(number_of_queens):
    solution_count = 0

    def is_safe(row_position, column_position, queen_positions):
        for row_index in range(row_position):
            column_index = queen_positions[row_index]
            if column_index == column_position or \
               abs(column_index - column_position) == row_position - row_index:
                return False
        return True

    def solve_n_queens(row_position, queen_positions):
        nonlocal solution_count

        if row_position == number_of_queens:
            solution_count += 1
            return

        # Iterate through columns in current row
        for column_position in range(number_of_queens):
            # Check if queen can be placed here
            if is_safe(row_position, column_position, queen_positions):

                queen_positions[row_position] = column_position
                # Move to the next row to place a queen
                solve_n_queens(row_position + 1, queen_positions)

    # Initialize array to track queen positions
    queen_positions = [0] * number_of_queens
    # Start placing queens from the first row
    solve_n_queens(0, queen_positions)

    return solution_count

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores possible queen placements row by row. In the first row, there are n possible columns to place a queen. In the second row, there are potentially n possible columns again, and so on. In the worst case, we might explore almost every possible configuration before backtracking, leading to a decision tree with a branching factor of up to n at each level for n levels. This results in a time complexity roughly proportional to n * n * n... (n times), or n^n. However, with backtracking, we don't explore all n^n possibilities, because conflicts prune the search space. While backtracking prunes the search space, in the worst-case scenario, it still explores a large portion of the search space, closer to O(n!) than O(n^n), reflecting the factorial increase in possible permutations as n grows. Therefore, the time complexity is O(n!).

Space Complexity

O(N) – The algorithm uses recursion, and in the worst case, the recursion depth can go up to N, where N is the size of the board. Each recursive call adds a new frame to the call stack, which stores information about the function's local variables and the return address. Additionally, we would likely use auxiliary data structures like arrays or sets of size N to represent the column placements and keep track of attacked positions, resulting in auxiliary space usage proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
n = 0 (Empty board)	Return 1, as there is one way to place zero queens (do nothing).
n = 1 (Single cell board)	Return 1, as a single queen can be placed on the cell.
n = 2 or n = 3 (No solutions)	Return 0, as no valid arrangement of queens exists for these board sizes.
Large n (e.g., n = 12+)	Ensure the algorithm scales reasonably well, using techniques like bit manipulation for representation to improve performance or memoization of smaller subproblems to reduce computations.
Integer overflow when calculating solution count for large n (language-specific)	Use a data type that can accommodate the number of solutions (e.g., long in Java/C++, or arbitrary precision integers if necessary).
Deep recursion calls with large n causing stack overflow.	If recursion depth becomes an issue, switch to an iterative approach using a stack to simulate the recursive calls, or implement memoization if possible.
Negative input for n	Throw an IllegalArgumentException or return 0 (invalid input).
n is a non-integer value	Type checking or conversion to integer with appropriate error handling if necessary.

n = 0 (Empty board)

How to Handle:

Return 1, as there is one way to place zero queens (do nothing).

n = 1 (Single cell board)

How to Handle:

Return 1, as a single queen can be placed on the cell.

n = 2 or n = 3 (No solutions)

How to Handle:

Return 0, as no valid arrangement of queens exists for these board sizes.

Large n (e.g., n = 12+)

How to Handle:

Ensure the algorithm scales reasonably well, using techniques like bit manipulation for representation to improve performance or memoization of smaller subproblems to reduce computations.

Integer overflow when calculating solution count for large n (language-specific)

How to Handle:

Use a data type that can accommodate the number of solutions (e.g., long in Java/C++, or arbitrary precision integers if necessary).

Deep recursion calls with large n causing stack overflow.

How to Handle:

If recursion depth becomes an issue, switch to an iterative approach using a stack to simulate the recursive calls, or implement memoization if possible.

Negative input for n

How to Handle:

Throw an IllegalArgumentException or return 0 (invalid input).

n is a non-integer value

How to Handle:

Type checking or conversion to integer with appropriate error handling if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `n`? Are there any constraints on the size of the board?
Is 'distinct solutions' defined as unique board configurations, or are rotations/reflections of the same configuration considered distinct?
If n is 0, should I return 1 (representing an empty board as a solution) or 0 (representing no possible placement)?
Can I assume that the input `n` will always be a non-negative integer?
Could you provide a small example (e.g., n=3 or n=4) and the corresponding expected output to clarify the problem further?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by placing a queen in the first column, trying every possible row in that column.
For each position of the first queen, try placing a queen in the second column, again trying every possible row.
Continue this process column by column, placing one queen per column.
Before placing a queen, always check if the current queen placement conflicts with any previously placed queens (i.e., if they attack each other).
If there is a conflict, skip that placement and try the next row in the current column.
If you reach the last column and successfully place a queen without any conflicts, you have found one valid arrangement. Increment the solution counter.
After exploring one possibility fully, backtrack. This means removing the queen from the last column and trying the next row in that column. Continue until all possible arrangements have been checked in the last column.
Repeat the backtracking process for all columns to explore all combinations of queen placements.
The final count of valid arrangements represents the total number of solutions.

Code Implementation

def total_n_queens(n):
    number_of_solutions = 0
    queens_positions = []

    def is_safe(row_index, column_index):
        for previous_row_index, previous_column_index in enumerate(queens_positions):
            if column_index == previous_column_index or \
               abs(column_index - previous_column_index) == abs(row_index - previous_row_index):
                return False
        return True

    def solve_n_queens_recursive(row_index):
        nonlocal number_of_solutions

        # Base case: all queens are placed
        if row_index == n:
            number_of_solutions += 1
            return

        for column_index in range(n):
            # Check if this position is safe
            if is_safe(row_index, column_index):

                # Place the queen
                queens_positions.append(column_index)

                # Recursively solve for the next row
                solve_n_queens_recursive(row_index + 1)

                # Backtrack: remove the queen
                queens_positions.pop()

    # Initiate the recursive process
    solve_n_queens_recursive(0)

    return number_of_solutions

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty board.
Try placing a queen in the first available column of the first row.
Check if this placement creates any conflicts (i.e., if the new queen is attacked by any existing queen).
If there's a conflict, try placing the queen in the next available column of the same row.
If there's no conflict, move to the next row and repeat the queen placement process.
If you reach the last row and have successfully placed a queen without conflicts, you've found one valid solution; record it.
After recording a solution (or if you run out of valid columns to try in a row), backtrack. This means you remove the queen from the current row and go back to the previous row to try placing its queen in a different column.
Keep exploring all possible paths until you've exhausted all options in the first row. The total number of valid solutions recorded is the answer.

Code Implementation

def total_n_queens(number_of_queens):
    solution_count = 0

    def is_safe(row_position, column_position, queen_positions):
        for row_index in range(row_position):
            column_index = queen_positions[row_index]
            if column_index == column_position or \
               abs(column_index - column_position) == row_position - row_index:
                return False
        return True

    def solve_n_queens(row_position, queen_positions):
        nonlocal solution_count

        if row_position == number_of_queens:
            solution_count += 1
            return

        # Iterate through columns in current row
        for column_position in range(number_of_queens):
            # Check if queen can be placed here
            if is_safe(row_position, column_position, queen_positions):

                queen_positions[row_position] = column_position
                # Move to the next row to place a queen
                solve_n_queens(row_position + 1, queen_positions)

    # Initialize array to track queen positions
    queen_positions = [0] * number_of_queens
    # Start placing queens from the first row
    solve_n_queens(0, queen_positions)

    return solution_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0 (Empty board)	Return 1, as there is one way to place zero queens (do nothing).
n = 1 (Single cell board)	Return 1, as a single queen can be placed on the cell.
n = 2 or n = 3 (No solutions)	Return 0, as no valid arrangement of queens exists for these board sizes.
Large n (e.g., n = 12+)	Ensure the algorithm scales reasonably well, using techniques like bit manipulation for representation to improve performance or memoization of smaller subproblems to reduce computations.
Integer overflow when calculating solution count for large n (language-specific)	Use a data type that can accommodate the number of solutions (e.g., long in Java/C++, or arbitrary precision integers if necessary).
Deep recursion calls with large n causing stack overflow.	If recursion depth becomes an issue, switch to an iterative approach using a stack to simulate the recursive calls, or implement memoization if possible.
Negative input for n	Throw an IllegalArgumentException or return 0 (invalid input).
n is a non-integer value	Type checking or conversion to integer with appropriate error handling if necessary.

n = 0 (Empty board)

How to Handle:

Return 1, as there is one way to place zero queens (do nothing).

n = 1 (Single cell board)

How to Handle:

Return 1, as a single queen can be placed on the cell.

n = 2 or n = 3 (No solutions)

How to Handle:

Return 0, as no valid arrangement of queens exists for these board sizes.

Large n (e.g., n = 12+)

How to Handle:

Ensure the algorithm scales reasonably well, using techniques like bit manipulation for representation to improve performance or memoization of smaller subproblems to reduce computations.

Integer overflow when calculating solution count for large n (language-specific)

How to Handle:

Use a data type that can accommodate the number of solutions (e.g., long in Java/C++, or arbitrary precision integers if necessary).

Deep recursion calls with large n causing stack overflow.

How to Handle:

If recursion depth becomes an issue, switch to an iterative approach using a stack to simulate the recursive calls, or implement memoization if possible.

Negative input for n

How to Handle:

Throw an IllegalArgumentException or return 0 (invalid input).

n is a non-integer value

How to Handle:

Type checking or conversion to integer with appropriate error handling if necessary.