52. N-Queens II


Problem Description

The n-queens puzzle is a classic problem in computer science and math that involves placing 'n' queens on an 'n x n' chessboard in such a way that no two queens can attack each other. This means that no two queens can be in the same row, column, or diagonal. The challenge is to determine the total number of unique ways (distinct solutions) in which the 'n' queens can be placed on the board without threatening each other.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here are the steps to determine the appropriate algorithm:

Is it a graph?

  • No: The N-Queens problem is not typically viewed as a graph problem involving nodes and edges.

Need to solve for kth smallest/largest?

  • No: This problem is about placing queens on a chessboard, not about finding kth smallest or largest elements.

Involves Linked Lists?

  • No: The N-Queens problem does not involve linked lists.

Does the problem have small constraints?

  • Yes: The N-Queens problem usually involves a single integer ( n ), the size of the board, which can be considered as having relatively small constraints (commonly up to ( n=10 )).

Brute force / Backtracking?

  • Yes: Brute force or backtracking is a common approach for problems like N-Queens, where all possible configurations of placing queens must be considered, and constraints (no two queens attack each other) must be respected.

Conclusion: The flowchart suggests using a backtracking approach to explore all valid arrangements of queens on the board. This pattern is indeed the most frequent approach for solving the N-Queens problem, as the problem's constraints naturally lend themselves to a recursive method of placing queens one row at a time, backing up when a placement leads to a dead end.

Intuition

To solve the n-queens problem, we use a backtracking algorithm. Backtracking is a systematic way to iterate through all the possible configurations of the chessboard and to "backtrack" whenever placing a queen would lead to a conflict. For each row, we try to place a queen in a valid position and then move to the next row. If we find a row where we can't place a queen without causing a conflict, we backtrack to the previous row and try a different position for the queen.

Here are the steps in the solution approach:

  • Represent the chessboard using variables that indicate columns and diagonals that are "under attack" by queens already placed.
  • Use a depth-first search (DFS) algorithm. We start from the first row and move row by row to the next, trying to place a queen in a safe column.
  • Maintain three arrays cols, dg, and udg. cols tracks which columns have queens, dg tracks the "normal" diagonals and udg tracks the "anti-diagonals".
  • For each recursive call (dfs), check each column in the current row:
    • Calculate the indexes for the diagonals based on the current row and column.
    • Check if the current column or the diagonal paths are already containing a queen (cols[j], dg[a], or udg[b]). If they are, we skip this column and continue the loop.
    • If the current column and diagonals are free, place a queen there (marking the column and diagonals as "under attack") and call dfs for the next row.
  • When we reach a row beyond the last one (i == n), it means a valid configuration of queens has been placed, and we increment our solutions counter ans.
  • The backtracking happens when we return from a dfs call and we "remove" the queen from that row's column and diagonals (by unmarking cols[j], dg[a], and udg[b]) before going back to try the next column.
  • Once all possibilities have been explored, return ans, which holds the count of valid solutions.

This approach ensures that all potential board configurations are considered without violating the constraints of the n-queens problem. By the end of the recursive exploration, we'll have the total count of distinct solutions.

Learn more about Backtracking patterns.

Solution Approach

The solution approach involves using depth-first search (DFS) to explore all possible placements of queens row by row, while ensuring that no queen is placed in a position where it can attack or be attacked by another queen.

Here's how the algorithm and data structures are utilized:

  • Columns, Diagonals, and Anti-Diagonals Tracking: We use three arrays to keep track of the threats for each queen placement.

    • cols: A boolean array representing if a column is under attack by any queen (True if under attack, False otherwise).
    • dg: A boolean array representing the normal diagonals on the board. The index of a cell's normal diagonal can be obtained by i + j (row index plus column index).
    • udg: A boolean array representing the anti-diagonals on the board. The index of a cell's anti-diagonal can be obtained by i - j + n (row index minus column index with an offset of n).
  • Depth-First Search (DFS) Implementation: This function is implemented recursively. dfs(i) means trying to place a queen in the i-th row.

    • If i equals n, it indicates that queens have been successfully placed in all rows from 0 to n-1, hence a valid solution. We increment the answer counter ans to record this solution.
    • We then iterate over each column j of row i to check if we can place a queen there.
      • For each column j, we calculate the indexes a and b for the normal and anti-diagonals using the formulas i + j and i - j + n, respectively.
      • Check if column j or either of the diagonals indexed by a or b are under attack (cols[j], dg[a], or udg[b]). If they are, we skip to the next column in the current row.
      • If none is under attack, we place a queen by marking column j and the corresponding diagonals as True, effectively denoting them as "under attack".
    • After placing a queen, the DFS algorithm recursively moves to the next row by calling dfs(i + 1).
    • Once the DFS call returns (either a solution was found for that path or no solution), we backtrack by unmarking column j and the corresponding diagonals, thus removing the queen from the board. This opens up new possibilities for queen placements in subsequent iterations.
  • Solution Counter: We maintain an integer ans to count the number of distinct solutions found.

  • Application: We initialize the cols, dg, udg arrays with adequate sizes based on the maximum possible size of the chessboard (cols has n elements, dg and udg have 2n to cover all possible diagonals). We then call dfs(0) to start the algorithm from the first row and continue until valid placements are found for all rows.

  • Return Value: After the entire board is explored, dfs has been attempted from all possible columns for every row, and backtracking has occurred where possible. The variable ans holds the total number of valid solutions and is returned as the final result.

The use of DFS and backtracking is key in this algorithm, allowing the program to explore the entire solution space without repeating configurations or violating the constraints of the n-queens puzzle.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example of the n-queens problem for n = 4. We will place 4 queens on a 4x4 chessboard so that no two queens can attack each other. We'll use the steps outlined in the solution approach.

  • First, initialize the cols, dg, and udg arrays as empty boolean arrays sized for n = 4. This is as cols[4], dg[8], and udg[8].

  • Start with the first row (i = 0) and try to place a queen in each column (j = 0 to n-1), checking for conflicts with cols, dg, and udg.

  • Explore the first column (j = 0). None of the arrays are marked true, so it is safe to place a queen here.

    • Mark cols[0], dg[0+0 (i+j)], and udg[0-0+4 (i-j+n)] as true.
  • Move to the next row (i = 1) and iterate over the columns.

    • Skip column j = 0 because cols[0] is true.
    • For column j = 1, we check for diagonal attacks. dg[i+j (1+1)] and udg[i-j+n (1-1+4)] are not under attack, so we can place a queen here.
      • Mark cols[1], dg[1+1 (2)], and udg[1-1+4 (4)] as true.
  • Move to the third row (i = 2). Iterate over the columns again.

    • Skip column j = 0 and j = 1 as cols and udg are marked true, respectively.
    • Column j = 2 is safe, so place a queen, and mark the affected cols, dg, and udg.
  • Move to the fourth row (i = 3). All columns until j = 3 are under attack.

    • Place a queen in column j = 3 and mark the affected cols, dg, and udg.
  • Since placing a queen in the fourth row (i = 3) is successful and i now equals n, increment the solutions counter ans.

  • After the solution is recorded, we backtrack from this placement to explore other potential solutions:

    • Unmark cols[3], dg[3+3], and udg[3-3+4], and return to the third row (i = 2).
    • Since there are no other columns left to explore in row i = 2, unmark the respective cols, dg, and udg for the queen placed in column j = 2, and move back to row i = 1.
  • Repeat the process for all the rows:

    • This involves placing the queen in a new column when possible, marking the arrays again.
    • Recursively calling dfs(i + 1) for the next row.
    • Backtracking when no solution is found in the current path and unmarking arrays, then returning to the previous row.
  • Continue this recursive DFS and backtracking process for all rows and columns.

  • The final ans will be the total number of valid solutions after the algorithm explores all possible placements of queens on the 4x4 board.

Following the complete exploration using DFS and backtracking, we will find that there are 2 solutions to the 4-queens problem.

Solution Implementation

1class Solution:
2    def totalNQueens(self, n: int) -> int:
3        # DFS function to try placing a queen on each row
4        def dfs(row):
5            # If all queens are placed successfully, increment the solution count
6            if row == n:
7                nonlocal solution_count
8                solution_count += 1
9                return
10          
11            # Try placing a queen in each column of the current row
12            for col in range(n):
13                # Calculate indices for the diagonals
14                pos_diag = row + col
15                neg_diag = row - col + n
16              
17                # Check if the column or the diagonals have a queen already
18                if cols[col] or diag[pos_diag] or anti_diag[neg_diag]:
19                    continue  # Skip if there's a conflict
20              
21                # Place the queen and mark the places as attacked
22                cols[col] = diag[pos_diag] = anti_diag[neg_diag] = True
23                # Recursively place queen in the next row
24                dfs(row + 1)
25                # Backtrack and remove the queen from the current spot
26                cols[col] = diag[pos_diag] = anti_diag[neg_diag] = False
27
28        # Arrays to keep track of attacked columns and diagonals
29        cols = [False] * n  # Columns where the queens can attack
30        diag = [False] * (2 * n)  # Positive diagonals (index = row + col)
31        anti_diag = [False] * (2 * n)  # Negative diagonals (index = row - col + n)
32      
33        solution_count = 0  # Counter for number of valid solutions
34        # Start the DFS recursion from the first row
35        dfs(0)
36        # Return the total number of valid solutions found
37        return solution_count
38
1class Solution {
2    private int boardSize;
3    private int solutionsCount;
4    private boolean[] columnsInUse; // marks columns that are already occupied
5    private boolean[] positiveDiagonalsInUse; // marks positive diagonals that are already occupied
6    private boolean[] negativeDiagonalsInUse; // marks negative diagonals that are already occupied
7
8    public int totalNQueens(int n) {
9        this.boardSize = n;
10        this.columnsInUse = new boolean[n]; // assuming N will not exceed 10
11        this.positiveDiagonalsInUse = new boolean[2 * n]; // range of possible values for (row + col)
12        this.negativeDiagonalsInUse = new boolean[2 * n]; // range for possible values for (row - col + n)
13        this.solutionsCount = 0;
14        placeQueens(0);
15        return solutionsCount;
16    }
17
18    // Tries to place queens on the board, starting from row i
19    private void placeQueens(int row) {
20        // If we've placed queens in all rows, a solution has been found
21        if (row == boardSize) {
22            ++solutionsCount;
23            return;
24        }
25
26        // Attempt to place a queen in each column of the current row
27        for (int col = 0; col < boardSize; ++col) {
28            int positiveDiagonalIndex = row + col;
29            int negativeDiagonalIndex = row - col + boardSize;
30            if (columnsInUse[col] || positiveDiagonalsInUse[positiveDiagonalIndex] || 
31                negativeDiagonalsInUse[negativeDiagonalIndex]) {
32                continue; // can't place here as it's being attacked
33            }
34
35            // Place the queen by marking the column and diagonals as occupied
36            columnsInUse[col] = true;
37            positiveDiagonalsInUse[positiveDiagonalIndex] = true;
38            negativeDiagonalsInUse[negativeDiagonalIndex] = true;
39
40            // Move on to the next row
41            placeQueens(row + 1); 
42
43            // Backtrack: remove the queen, making the column and diagonals available again
44            columnsInUse[col] = false;
45            positiveDiagonalsInUse[positiveDiagonalIndex] = false;
46            negativeDiagonalsInUse[negativeDiagonalIndex] = false;
47        }
48    }
49}
50
1#include <bitset>
2#include <functional>
3
4class Solution {
5public:
6    // Entry point to solve the N-Queens II problem
7    int TotalNQueens(int n) {
8        std::bitset<10> columns;        // Tracks occupied columns
9        std::bitset<20> major_diagonals; // Tracks occupied major diagonals
10        std::bitset<20> minor_diagonals; // Tracks occupied minor diagonals
11        int solution_count = 0;          // Stores the number of valid solutions
12
13        // Lambda function to run depth-first search on rows
14        std::function<void(int)> depth_first_search = [&](int row) {
15            // Base case: all rows are filled, found a valid placement
16            if (row == n) {
17                ++solution_count;
18                return;
19            }
20            // Iterate through columns at the current row
21            for (int column = 0; column < n; ++column) {
22                // Calculate indices for the diagonals
23                int major_diag_index = row + column;
24                int minor_diag_index = row - column + n;
25
26                // Check if the current column or diagonals are occupied
27                if (columns[column] || major_diagonals[major_diag_index] || minor_diagonals[minor_diag_index]) {
28                    continue; // Skip to the next iteration if any are occupied
29                }
30              
31                // Mark the current column and diagonals as occupied
32                columns[column] = major_diagonals[major_diag_index] = minor_diagonals[minor_diag_index] = true;
33              
34                // Moves to the next row
35                depth_first_search(row + 1);
36              
37                // Reset the current column and diagonals back to unoccupied for the next iteration
38                columns[column] = major_diagonals[major_diag_index] = minor_diagonals[minor_diag_index] = false;
39            }
40        };
41
42        // Start the DFS from the first row
43        depth_first_search(0);
44
45        // Return the total count of valid solutions found
46        return solution_count;
47    }
48};
49
1// Use an array to track occupied columns, `true` indicates occupation
2const columns: boolean[] = new Array<boolean>(10).fill(false);
3
4// Track occupied diagonals ('true' indicates occupation)
5const majorDiagonals: boolean[] = new Array<boolean>(20).fill(false);
6const minorDiagonals: boolean[] = new Array<boolean>(20).fill(false);
7
8// Variable to store the number of valid solutions
9let solutionCount: number = 0;
10
11// Function to solve the N-Queens II problem given `n` (the size of the chessboard)
12function totalNQueens(n: number): number {
13    // Reset tracking arrays and solution count for each new problem instance
14    columns.fill(false);
15    majorDiagonals.fill(false);
16    minorDiagonals.fill(false);
17    solutionCount = 0;
18  
19    // Inner function to perform depth-first search starting from the first row
20    function depthFirstSearch(row: number) {
21        // Base case: all rows are filled, a valid placement is found
22        if (row === n) {
23            solutionCount++;
24            return;
25        }
26
27        // Iterate through columns at the current row
28        for (let column = 0; column < n; column++) {
29            // Calculate indices for the diagonals
30            let majorDiagIndex = row + column;
31            let minorDiagIndex = n - 1 - row + column;
32
33            // Check if the current column or diagonals are occupied
34            if (columns[column] || majorDiagonals[majorDiagIndex] || minorDiagonals[minorDiagIndex]) {
35                continue; // Skip if any are occupied
36            }
37          
38            // Mark the current column and diagonals as occupied
39            columns[column] = majorDiagonals[majorDiagIndex] = minorDiagonals[minorDiagIndex] = true;
40          
41            // Recursive call to try the next row
42            depthFirstSearch(row + 1);
43          
44            // Backtrack: unmark the current column and diagonals before the next iteration
45            columns[column] = majorDiagonals[majorDiagIndex] = minorDiagonals[minorDiagIndex] = false;
46        }
47    }
48
49    // Start the search from the first row
50    depthFirstSearch(0);
51
52    // Return the total count of valid solutions
53    return solutionCount;
54}
55

Time and Space Complexity

The given Python code is a solution to the N-Queens II problem which returns the number of distinct solutions for an n x n chessboard. The algorithm uses depth-first search (DFS) to traverse all possible board configurations and count valid placements of queens.

Time Complexity

The time complexity of the function is O(N!), where N is the input size of the chessboard (n x n). For each row, we attempt to place a queen in every column and use three arrays (cols, dg, udg) to check if the current cell is under attack. The DFS approach ensures that for the first queen, there are N possible columns to place it in, for the second queen there are N - 1 possibilities (excluding the column and diagonals of the first queen), and so on. This sequential reduction in possibilities leads to factorial time complexity. However, due to the aggressive pruning by the if cols[j] or dg[a] or udg[b]: continue condition, the actual run time is significantly less than N!. Nonetheless, the upper bound remains factorial in the worst case.

Space Complexity

The space complexity of the function is O(N). This includes:

  • The cols, dg, and udg arrays with fixed sizes 10, 20, and 20, respectively, which do not depend on the input size N. However, for larger boards these sizes would scale with N and the arrays would become O(N).
  • The system's call stack for the recursive function dfs. In the worst case, the recursion depth will be N, as dfs will be called once per row.

Notice that the nonlocal variable ans is used to count the solutions but does not increase the space complexity as it requires constant space.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.