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.

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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1class Solution:
2    def solveNQueens(self, n: int) -> List[List[str]]:
3        def backtrack(row: int):
4            # When the row number equals 'n', it means all queens are placed successfully
5            if row == n:
6                # Save a solution by converting each row's list representation to a string
7                solution.append([''.join(row_state) for row_state in board])
8                return
9            # Iterate over columns to try placing a queen
10            for col in range(n):
11                # Check if placing a queen here violates no constraints
12                if column[col] + diagonal[row + col] + anti_diagonal[n - row + col] == 0:
13                    # Place the queen by updating the board and marking the corresponding constraints
14                    board[row][col] = "Q"
15                    column[col] = diagonal[row + col] = anti_diagonal[n - row + col] = 1
16                    # Move on to the next row
17                    backtrack(row + 1)
18                    # Backtrack: remove the queen and the constraints
19                    column[col] = diagonal[row + col] = anti_diagonal[n - row + col] = 0
20                    board[row][col] = "."
21
22        # Initialize solution list
23        solution = []
24        # Initialize board with dots representing empty spaces
25        board = [["."] * n for _ in range(n)]
26        # Prepare constraint lists to check the columns and diagonals/anti-diagonals
27        column = [0] * n
28        diagonal = [0] * (2 * n)
29        anti_diagonal = [0] * (2 * n)
30        # Start the backtracking algorithm from the first row
31        backtrack(0)
32        # Return the list of all the solutions after converting them to the expected output format
33        return solution
34

Java Solution

1import java.util.List;
2import java.util.ArrayList;
3import java.util.Arrays;
4
5public class Solution {
6    // The list that will contain all possible solutions
7    private List<List<String>> solutions = new ArrayList<>();
8  
9    // Arrays to mark if a column, diagonal, or anti-diagonal is occupied
10    private int[] columns;
11    private int[] diagonals;
12    private int[] antiDiagonals;
13  
14    // Chessboard representation
15    private String[][] board;
16  
17    // Size of the board
18    private int size;
19
20    // The public method to solve the N-Queens problem
21    public List<List<String>> solveNQueens(int n) {
22        this.size = n;
23        columns = new int[n];
24        diagonals = new int[2 * n];
25        antiDiagonals = new int[2 * n];
26        board = new String[n][n];
27      
28        // Initialize the board with empty strings
29        for (int i = 0; i < n; ++i) {
30            Arrays.fill(board[i], ".");
31        }
32      
33        // Begin the depth-first search from the first row
34        depthFirstSearch(0);
35        return solutions;
36    }
37
38    // The recursive method to place a queen on the board
39    private void depthFirstSearch(int row) {
40        // If all queens are placed
41        if (row == size) {
42            List<String> oneSolution = new ArrayList<>();
43            for (int i = 0; i < size; ++i) {
44                // Join the row to form the string
45                oneSolution.add(String.join("", board[i]));
46            }
47            // Add the current board configuration to the solutions list
48            solutions.add(oneSolution);
49            return;
50        }
51        // Iterate through each column for the current row
52        for (int col = 0; col < size; ++col) {
53            // Check if the current position is safe for placing a queen
54            if (columns[col] + diagonals[row + col] + antiDiagonals[size - row + col] == 0) {
55                // Place the queen
56                board[row][col] = "Q";
57                // Mark current column, diagonal, and anti-diagonal as occupied
58                columns[col] = diagonals[row + col] = antiDiagonals[size - row + col] = 1;
59                // Continue to place the next queen
60                depthFirstSearch(row + 1);
61                // Backtrack and remove the queen
62                columns[col] = diagonals[row + col] = antiDiagonals[size - row + col] = 0;
63                board[row][col] = ".";
64            }
65        }
66    }
67}
68

C++ Solution

1#include <vector>
2#include <string>
3#include <functional>
4
5class Solution {
6public:
7    std::vector<std::vector<std::string>> solveNQueens(int n) {
8        // Arrays to mark the columns and diagonals as occupied.
9        std::vector<int> col_occupied(n, 0);
10        std::vector<int> diag_occupied(2 * n, 0);
11        std::vector<int> anti_diag_occupied(2 * n, 0);
12      
13        // Answer array to store all possible configurations.
14        std::vector<std::vector<std::string>> solutions;
15      
16        // Temporary board to build one configuration at a time.
17        std::vector<std::string> board(n, std::string(n, '.'));
18      
19        // Lambda function for backtracking.
20        std::function<void(int)> backtrack = [&](int row) -> void {
21            // Base case: If we placed all queens, add the configuration to the solution.
22            if (row == n) {
23                solutions.push_back(board);
24                return;
25            }
26
27            // Try placing a queen in each column of the current row.
28            for (int column = 0; column < n; ++column) {
29                // Check if the column, diagonal, and anti-diagonal are not occupied.
30                if (!col_occupied[column] && !diag_occupied[row + column] 
31                    && !anti_diag_occupied[n - row + column]) {
32                    // Place the queen.
33                    board[row][column] = 'Q';
34                    // Mark the column and diagonals as occupied.
35                    col_occupied[column] = diag_occupied[row + column]
36                        = anti_diag_occupied[n - row + column] = 1;
37                  
38                    // Move to the next row.
39                    backtrack(row + 1);
40                  
41                    // Undo the move before backtracking.
42                    col_occupied[column] = diag_occupied[row + column]
43                        = anti_diag_occupied[n - row + column] = 0;
44                    board[row][column] = '.';
45                }
46            }
47        };
48
49        // Start the backtracking process from the first row.
50        backtrack(0);
51
52        // Return all possible valid boards.
53        return solutions;
54    }
55};
56

Typescript Solution

1function solveNQueens(n: number): string[][] {
2    // These arrays record if a column or diagonal is under attack
3    const columns: number[] = new Array(n).fill(0);
4    const diag: number[] = new Array(n * 2).fill(0);
5    const antiDiag: number[] = new Array(n * 2).fill(0);
6    // This is the solution set
7    const solutions: string[][] = [];
8    // Temporary matrix to build the current state
9    const board: string[][] = Array(n)
10        .fill(0)
11        .map(() => Array(n).fill('.'));
12  
13    // Depth-first search function
14    const dfs = (row: number) => {
15        // If all rows are filled, add the current board state to solutions
16        if (row === n) {
17            solutions.push(board.map(row => row.join('')));
18            return;
19        }
20      
21        // Iterate over columns in the current row
22        for (let col = 0; col < n; ++col) {
23            // Ensure the position is not under attack by checking the markers
24            if (columns[col] + diag[row + col] + antiDiag[n - row + col] === 0) {
25                // Place a queen and mark the column and diagonals as under attack
26                board[row][col] = 'Q';
27                columns[col] = diag[row + col] = antiDiag[n - row + col] = 1;
28                // Move to the next row
29                dfs(row + 1);
30                // Backtrack: remove the queen and remove the attack markers
31                columns[col] = diag[row + col] = antiDiag[n - row + col] = 0;
32                board[row][col] = '.';
33            }
34        }
35    };
36  
37    // Start DFS from the first row
38    dfs(0);
39  
40    return solutions;
41}
42

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.
😈
Become an
Algo Monster

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

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫