51. N-Queens

Problem Description

The n-queens puzzle is a classic problem of placing n queens on an n x n chessboard in a way that no queens can attack each other. This means two queens can't be in the same row, column, or diagonal. The challenge is to find all the possible arrangements of the n queens where these conditions are met.

Intuition

To solve the n-queens puzzle, we can use a method called Depth-First Search (DFS), which is a type of backtracking algorithm. The idea is to place queens one by one in different columns, starting from the leftmost column and moving to the right. If we find a placement for a queen that does not lead to a conflict, we then move on to place the next queen in the next column. If at any step we cannot place a queen without a conflict, we backtrack and move the previous queen to a new position.

The efficiency of this backtracking algorithm can be drastically improved by keeping track of the columns, diagonals, and anti-diagonals that are already under attack by existing queens:

• To mark the columns that are occupied, an array called col is used, with a length equal to the number of columns (n).
• For the diagonals (dg), an array of size 2n is used, because there are 2n - 1 possible diagonals on the board. A diagonal's index can be calculated by the sum of the row and column indices of a cell.
• For the anti-diagonals (udg), an array with the same size as the diagonals is used. The anti-diagonal's index is obtained by the difference between the column index and the row index, plus n to avoid negative indices.

Each time a queen is placed, we mark the corresponding column, diagonal, and anti-diagonal as occupied. We unmark them when we backtrack. This way, we ensure no two queens threaten each other, and we generate all valid solutions for the problem.

Learn more about Backtracking patterns.

Solution Approach

The solution approach to the n-queens puzzle involves implementing a recursive Depth-First Search (DFS) that tries to place queens one by one across each row. The given Python code defines a recursive function dfs which attempts to place a queen in every row – the i parameter corresponds to the current row index where the function tries to place a queen.

Here's a step-by-step explanation of the algorithm, along with the corresponding aspects of the provided code:

1. Initialization:

   • Create a list ans to store the solutions.
   • Initialize a 2D list g with n lists, each filled with a string of n periods ("."). This represents the chessboard where a "." is an empty space and will be replaced by a "Q" when a queen is placed.
   • Initialize col, dg, and udg arrays which represent the columns, diagonals, and anti-diagonals that are already attacked by queens.

2. Recursive DFS Function dfs(i):

   • The base case is when i == n, meaning all rows have been visited, and thus a valid configuration of the n-queens has been found. At this point, the current configuration is added to ans.
   • In each call of the dfs function, iterate through every column j in row i to try and place a queen.

3. Checking Conditions for Placing a Queen:

   • For each column j, check the safety by ensuring that there's no existing queen attacking the position (i, j). This is done by ensuring col[j] + dg[i + j] + udg[n - i + j] == 0. If this condition holds, it means placing a queen at position (i, j) will not result in an attack.

4. Placing a Queen and Marking the Attacks:

   • When a safe spot is found, place the queen by setting g[i][j] = "Q" and mark the column col[j], diagonal dg[i + j], and anti-diagonal udg[n - i + j] as attacked by setting them to 1.

5. Recursive Call for the Next Row:

   • Call dfs(i + 1) to attempt to place a queen in the next row.

6. Backtracking:

   • If placing the next queen leads to a dead-end (no further valid placements), or after recording a valid setup when reaching the base case, the function will backtrack by resetting the queen's position and unmarking the attacked paths. This is done by setting g[i][j] = ".", and resetting col[j], dg[i + j], and udg[n - i + j] back to 0.

7. Starting the DFS:

   • Initially call dfs(0) to start the process of attempting to place queens starting from the first row.

By applying DFS and backtracking effectively, this solution traverses the decision tree by trying different queen positions and backtracks whenever it encounters a conflict, ensuring that all possible valid arrangements of the queens on the board are found.

The elegance of this strategy lies in its ability to avoid checking for queen attacks for every placement, which would result in a slower, brute-force algorithm. Instead, the state is managed by strategically using arrays, decreasing the time complexity significantly. This makes the solution smart and efficient.

Example Walkthrough

Let's illustrate the solution approach using a small 4x4 board example for the n-queens puzzle. Our goal is to place 4 queens on this board so that no two queens can attack each other.

1. Initialization:

   • We start with an empty solution list ans and an empty 4x4 chessboard g represented by:

     1[".", ".", ".", "."],
     2[".", ".", ".", "."],
     3[".", ".", ".", "."],
     4[".", ".", ".", "."]

   • We also initialize the arrays col, dg, and udg to track attacked columns, diagonals, and anti-diagonals. Since the board is 4x4, col will have 4 elements, and dg and udg will each have 7 elements (since 2n - 1 = 7 for n = 4).

2. Recursive DFS Function dfs(0):

   • We start the DFS by calling dfs(0), indicating that we're trying to place a queen in row 0.

3. Checking Conditions for Placing a Queen:

   • We try to place the first queen in row 0, column 0. To check for safety, we ensure that no queen attacks position (0, 0) by confirming col[0] + dg[0 + 0] + udg[4 - 0 + 0] == 0. This is true, as all arrays are initialized with zeros.

4. Placing a Queen and Marking the Attacks:

   • We place the queen at (0, 0):

     1["Q", ".", ".", "."],
     2[".", ".", ".", "."],
     3[".", ".", ".", "."],
     4[".", ".", ".", "."]

   • Mark the attacks by setting col[0], dg[0 + 0], and udg[4 - 0 + 0] to 1.

5. Recursive Call for the Next Row dfs(1):

   • Now we call dfs(1) to try to place a queen in the next row.

6. Backtracking and Continuing the Search:

   • In row 1, the first column is attacked, so we try column 1. Position (1, 1) is safe, so we place the queen there and proceed to dfs(2).
   • In row 2, columns 0 and 1 are attacked. We find that (2, 2) is also under attack, but (2, 3) is safe, so we place the queen there and call dfs(3).
   • In row 3, columns 0, 1, and 3 are under attack. We find that placing a queen at (3, 2) is safe.
   • We have now successfully placed queens on all rows which give us one valid solution:

     1["Q", ".", ".", "."],
     2[".", "Q", ".", "."],
     3[".", ".", ".", "Q"],
     4[".", ".", "Q", "."]

   • We then record this solution and backtrack to find more. We remove the queen from (3, 2), unmark the attacks, and go back to row 2 to find a new position for a queen.
     • Trying to place another queen in row 2 finds no valid position, causing further backtracking to row 1.
     • We try a new position for the queen in row 1, and if possible, proceed to row 2 again.
     • We continue this process of backtracking and searching until all possible placements have been tried for all rows.

By following these steps, the recursive DFS algorithm ensures that all the conditions of the n-queens puzzle are respected, and thus all valid solutions are found. For the 4x4 board, there are two solutions, and both will be included in the ans list.

Solution Implementation

Time and Space Complexity

The given Python code is a solution for the N-Queens problem, where the objective is to place n queens on an n x n chessboard so that no two queens threaten each other.

Time Complexity

The time complexity of the solution is determined primarily by the number of valid queen placements that are possible on the board. The DFS function dfs(i: int) is called recursively for every row (where i is the row index), and in each call, it attempts to place a queen in each column of the current row.

• The main time complexity comes from the potential number of recursive calls in the depth-first search (DFS). For each row, we attempt to place a queen in every column, yielding a branching factor of n.
• However, due to the constraint checks (col[j], dg[i + j], udg[n - i + j]), the actual number of recursive calls will be less than n for subsequent rows.
• The upper bound complexity can be represented by O(n!), since there are n possibilities for the first row, n - 1 for the second, and so on until the base case is reached.
• The average complexity is hard to determine due to the constraint checks pruning the recursion tree, but it is significantly less than the upper bound.

Space Complexity

The space complexity accounts for the storage required for the recursive calls, the grid g, and the arrays for maintaining column, diagonal, and anti-diagonal checks (col, dg, udg).

• The grid g consumes O(n^2) space as it is a 2D matrix.
• The arrays col, dg, udg consume O(n), O(2n) (or O(n)) and O(2n) (or O(n)) space respectively, since there are 2n - 1 possible diagonals and anti-diagonals on an n x n chessboard. Scaled down, they contribute O(n) to the space complexity.
• The depth of the recursion stack is O(n) because there can be at most n recursive calls (one for each row) at any given time.

Hence, the space complexity is O(n^2) from the grid g, which dominates the space complexity relative to the recursive call stack and additional arrays.

In summary:

• The time complexity is O(n!) as an upper bound.
• The space complexity is O(n^2) due to the grid used to store intermediate solutions.

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