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
, andudg
.cols
tracks which columns have queens,dg
tracks the "normal" diagonals andudg
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]
, orudg[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 counterans
. - The backtracking happens when we return from a
dfs
call and we "remove" the queen from that row's column and diagonals (by unmarkingcols[j]
,dg[a]
, andudg[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 byi + 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 byi - j + n
(row index minus column index with an offset ofn
).
-
Depth-First Search (DFS) Implementation: This function is implemented recursively.
dfs(i)
means trying to place a queen in thei-th
row.- If
i
equalsn
, it indicates that queens have been successfully placed in all rows from0
ton-1
, hence a valid solution. We increment the answer counterans
to record this solution. - We then iterate over each column
j
of rowi
to check if we can place a queen there.- For each column
j
, we calculate the indexesa
andb
for the normal and anti-diagonals using the formulasi + j
andi - j + n
, respectively. - Check if column
j
or either of the diagonals indexed bya
orb
are under attack (cols[j]
,dg[a]
, orudg[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 asTrue
, effectively denoting them as "under attack".
- For each column
- 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.
- If
-
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
hasn
elements,dg
andudg
have2n
to cover all possible diagonals). We then calldfs(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 EvaluatorExample 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
, andudg
arrays as empty boolean arrays sized forn = 4
. This is ascols[4]
,dg[8]
, andudg[8]
. -
Start with the first row (
i = 0
) and try to place a queen in each column (j = 0
ton-1
), checking for conflicts withcols
,dg
, andudg
. -
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)]
, andudg[0-0+4 (i-j+n)]
as true.
- Mark
-
Move to the next row (
i = 1
) and iterate over the columns.- Skip column
j = 0
becausecols[0]
is true. - For column
j = 1
, we check for diagonal attacks.dg[i+j (1+1)]
andudg[i-j+n (1-1+4)]
are not under attack, so we can place a queen here.- Mark
cols[1]
,dg[1+1 (2)]
, andudg[1-1+4 (4)]
as true.
- Mark
- Skip column
-
Move to the third row (
i = 2
). Iterate over the columns again.- Skip column
j = 0
andj = 1
ascols
andudg
are marked true, respectively. - Column
j = 2
is safe, so place a queen, and mark the affectedcols
,dg
, andudg
.
- Skip column
-
Move to the fourth row (
i = 3
). All columns untilj = 3
are under attack.- Place a queen in column
j = 3
and mark the affectedcols
,dg
, andudg
.
- Place a queen in column
-
Since placing a queen in the fourth row (i = 3) is successful and
i
now equalsn
, increment the solutions counterans
. -
After the solution is recorded, we backtrack from this placement to explore other potential solutions:
- Unmark
cols[3]
,dg[3+3]
, andudg[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 respectivecols
,dg
, andudg
for the queen placed in columnj = 2
, and move back to rowi = 1
.
- Unmark
-
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
, andudg
arrays with fixed sizes10
,20
, and20
, respectively, which do not depend on the input sizeN
. However, for larger boards these sizes would scale withN
and the arrays would becomeO(N)
. - The system's call stack for the recursive function
dfs
. In the worst case, the recursion depth will beN
, asdfs
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.
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
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.