How do you solve N-Queens on LeetCode?

N-Queens (LeetCode #51) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n!) time complexity and O(n) space complexity. Key insight: Backtracking is essential for solving combinatorial problems efficiently.

What is the brute force solution for N-Queens?

The brute force approach for N-Queens is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries to place queens on the board in every possible configuration and checks if they are safe from each other. This method is simple but inefficient, as it explores many invalid configurations. The optimal Optimal Solution approach improves this to O(n!).

What algorithm or data structure is used to solve N-Queens?

N-Queens uses the following concepts: Array, Backtracking. The recommended patterns to study are: Backtracking, Recursion.

What are the interview tips for N-Queens?

Explain your thought process clearly; interviewers value understanding over speed. Practice writing clean and efficient code, as readability matters. Be prepared to discuss the trade-offs of different approaches.

What are common mistakes when solving N-Queens?

Not using backtracking effectively, leading to excessive checks. Failing to manage state (like columns and diagonals) properly.

#51

N-Queens

Hard

ArrayBacktrackingBacktrackingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n!)
Space	O(1)	O(n)

💡

Intuition

Time O(n!)Space O(n)

The optimal solution uses backtracking to efficiently explore valid configurations of queens while avoiding unnecessary checks. It systematically places queens and backtracks when a conflict arises, significantly reducing the number of configurations to check.

⚙️

Algorithm

4 steps

1Step 1: Use a recursive function to place queens row by row.
2Step 2: Maintain arrays to track columns and diagonals that are under attack.
3Step 3: If a valid position is found, place the queen and move to the next row.
4Step 4: If all queens are placed, record the solution.

solution.py25 lines

1# Full working Python code
2class Solution:
3    def solveNQueens(self, n: int):
4        def backtrack(row):
5            if row == n:
6                solutions.append(board[:])
7                return
8            for col in range(n):
9                if col not in cols and (row - col) not in diag1 and (row + col) not in diag2:
10                    board[row] = col
11                    cols.add(col)
12                    diag1.add(row - col)
13                    diag2.add(row + col)
14                    backtrack(row + 1)
15                    cols.remove(col)
16                    diag1.remove(row - col)
17                    diag2.remove(row + col)
18
19        solutions = []
20        board = [-1] * n
21        cols = set()
22        diag1 = set()
23        diag2 = set()
24        backtrack(0)
25        return ["." * i + "Q" + "." * (n - i - 1) for solution in solutions for i in solution]

ℹ

Complexity note: The time complexity is O(n!) because we are placing n queens and for each queen, we have n options, but we prune many branches due to the checks. The space complexity is O(n) due to the recursion stack and the board state.

1Backtracking is essential for solving combinatorial problems efficiently.
2Using sets to track attacked columns and diagonals reduces unnecessary checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.