N-Queens

Q: What is the time complexity of N-Queens?

O(n!). Each queen must be placed in a different row and column, so the number of permutations is n!. The pruning of invalid diagonals reduces the search space but the worst-case complexity remains factorial.

Q: What pattern does N-Queens use?

The Pattern: Backtracking (State Restoration) The Heuristic: For constraint satisfaction problems like N-Queens, incrementally build partial solutions while pruning invalid states early, and always restore state after exploring each branch to enable exhaustive and correct search.

Hard Backtracking

Problem

Given an integer n, return all distinct solutions to the n-queens puzzle such that no two queens threaten each other on an n x n chessboard.

1 ≤ n ≤ 9

Example

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

The algorithm explores placing queens row by row. For n=4, it tries placing a queen in the first row at each column, checking if the position is safe by verifying columns and diagonals. When it reaches the last row and successfully places a queen without conflicts, it records the board configuration. The critical moment is when the algorithm backtracks after exploring all columns in a row, removing the queen and trying alternative placements, ensuring all valid solutions are found.

Approach

Straightforward Solution

A brute-force approach would try all possible placements of n queens on an n x n board, which is O(n^n) and infeasible for larger n due to the combinatorial explosion.

Core Observation

The fundamental truth is that no two queens can share the same column, positive diagonal, or negative diagonal. This reduces the problem to a constraint satisfaction problem where each row must have exactly one queen placed in a safe column.

Path to Optimal

The key insight is to build the solution incrementally, placing one queen per row and pruning invalid placements early by tracking columns and diagonals already occupied. This backtracking approach avoids exploring invalid branches, drastically reducing the search space from exponential to manageable for typical constraints.

Optimal Approach

Use backtracking to place queens row by row. Maintain sets to track occupied columns and diagonals. For each row, iterate over columns and skip those that conflict with existing queens. Place a queen, update tracking sets, recurse to the next row, and backtrack by removing the queen and updating sets. When all rows are processed, record the valid board configuration. This approach guarantees all solutions are found efficiently.

Time

O(n!)

Each queen must be placed in a different row and column, so the number of permutations is n!. The pruning of invalid diagonals reduces the search space but the worst-case complexity remains factorial.

Space

O(n^2)

The board requires O(n^2) space to store the current state. The recursion stack and sets for columns and diagonals use O(n) space each, which is dominated by the board storage.

Pattern Spotlight

Backtracking (State Restoration)

For constraint satisfaction problems like N-Queens, incrementally build partial solutions while pruning invalid states early, and always restore state after exploring each branch to enable exhaustive and correct search.

Solution

1class Solution:
  def solveNQueens(self, n: int) -> list[list[str]]:
      col = set()
      pos_diag = set() 
      neg_diag = set() 
6
      res = []
      board = [["."] * n for i in range(n)]
9
      def backtrack(r):
          if r == n:
              copy = ["".join(row) for row in board]
              res.append(copy)
              return
          
          for c in range(n):
              if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
                  continue
              
              col.add(c)
              pos_diag.add(r + c)
              neg_diag.add(r - c)
              board[r][c] = "Q"
24
              backtrack(r + 1)
26
              col.remove(c)
              pos_diag.remove(r + c)
              neg_diag.remove(r - c)
              board[r][c] = "."
      
      backtrack(0)
      return res

1import java.util.*;
2
3public class Solution {
  public List<List<String>> solveNQueens(int n) {
      Set<Integer> col = new HashSet<>();
      Set<Integer> posDiag = new HashSet<>();
      Set<Integer> negDiag = new HashSet<>();
8
      List<List<String>> res = new ArrayList<>();
      char[][] board = new char[n][n];
      for (int i = 0; i < n; i++) {
          Arrays.fill(board[i], '.');
      }
14
      backtrack(0, n, col, posDiag, negDiag, board, res);
      return res;
  }
18
  private void backtrack(int r, int n, Set<Integer> col, Set<Integer> posDiag, Set<Integer> negDiag, char[][] board, List<List<String>> res) {
      if (r == n) {
          List<String> copy = new ArrayList<>();
          for (int i = 0; i < n; i++) {
              copy.add(new String(board[i]));
          }
          res.add(copy);
          return;
      }
28
      for (int c = 0; c < n; c++) {
          if (col.contains(c) || posDiag.contains(r + c) || negDiag.contains(r - c)) {
              continue;
          }
33
          col.add(c);
          posDiag.add(r + c);
          negDiag.add(r - c);
          board[r][c] = 'Q';
38
          backtrack(r + 1, n, col, posDiag, negDiag, board, res);
40
          col.remove(c);
          posDiag.remove(r + c);
          negDiag.remove(r - c);
          board[r][c] = '.';
      }
  }
47}

1#include <vector>
2#include <string>
3#include <unordered_set>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<vector<string>> solveNQueens(int n) {
10        unordered_set<int> col;
11        unordered_set<int> pos_diag;
12        unordered_set<int> neg_diag;
13
14        vector<vector<string>> res;
15        vector<vector<char>> board(n, vector<char>(n, '.'));
16
17        backtrack(0, n, col, pos_diag, neg_diag, board, res);
18        return res;
19    }
20
21private:
22    void backtrack(int r, int n, unordered_set<int>& col, unordered_set<int>& pos_diag, unordered_set<int>& neg_diag, vector<vector<char>>& board, vector<vector<string>>& res) {
23        if (r == n) {
24            vector<string> copy;
25            for (int i = 0; i < n; ++i) {
26                copy.emplace_back(board[i].begin(), board[i].end());
27            }
28            res.push_back(copy);
29            return;
30        }
31
32        for (int c = 0; c < n; ++c) {
33            if (col.count(c) || pos_diag.count(r + c) || neg_diag.count(r - c)) {
34                continue;
35            }
36
37            col.insert(c);
38            pos_diag.insert(r + c);
39            neg_diag.insert(r - c);
40            board[r][c] = 'Q';
41
42            backtrack(r + 1, n, col, pos_diag, neg_diag, board, res);
43
44            col.erase(c);
45            pos_diag.erase(r + c);
46            neg_diag.erase(r - c);
47            board[r][c] = '.';
48        }
49    }
50};

1var solveNQueens = function(n) {
  const col = new Set();
  const posDiag = new Set();
  const negDiag = new Set();
5
  const res = [];
  const board = Array.from({ length: n }, () => Array(n).fill('.'));
8
  function backtrack(r) {
      if (r === n) {
          const copy = board.map(row => row.join(''));
          res.push(copy);
          return;
      }
15
      for (let c = 0; c < n; c++) {
          if (col.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) {
              continue;
          }
20
          col.add(c);
          posDiag.add(r + c);
          negDiag.add(r - c);
          board[r][c] = 'Q';
25
          backtrack(r + 1);
27
          col.delete(c);
          posDiag.delete(r + c);
          negDiag.delete(r - c);
          board[r][c] = '.';
      }
  }
34
  backtrack(0);
  return res;
37};

Step-by-Step Solution

Initialize Board and Tracking Sets for Backtracking

3col = set()
4pos_diag = set() 
5neg_diag = set() 
7res = []
8board = [["."] * n for i in range(n)]

Objective

To prepare the data structures that track queen placements and constraints before starting the recursive search.

Key Insight

Using sets for columns and diagonals allows O(1) checks for conflicts, which is critical for pruning invalid placements early. Representing the board as a 2D list of characters enables easy updates and final solution formatting. This setup lays the foundation for efficient backtracking.

Interview Quick-Check

Core Logic

Sets for columns and diagonals enable constant-time conflict detection, which is essential for pruning the search space.

Common Pitfalls & Bugs

Forgetting to initialize the board or tracking sets correctly leads to incorrect conflict checks and invalid solutions.

Place Queens Row-by-Row Using Backtracking with Conflict Checks

10def backtrack(r):
  if r == n:
      copy = ["".join(row) for row in board]
      res.append(copy)
  for c in range(n):
      if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
          continue
      col.add(c)
      pos_diag.add(r + c)
      neg_diag.add(r - c)
      board[r][c] = "Q"
      backtrack(r + 1)
      col.remove(c)
      pos_diag.remove(r + c)
      neg_diag.remove(r - c)
      board[r][c] = "."

Objective

To recursively place queens on the board, ensuring no conflicts in columns or diagonals, and backtrack when necessary.

Key Insight

Backtracking explores all valid queen placements by trying each column in the current row. Conflict checks against columns and diagonals prune invalid positions immediately. After placing a queen, the algorithm recurses to the next row. Upon returning, it restores the state by removing the queen and updating tracking sets, enabling exploration of alternative placements. This systematic exploration guarantees all solutions are found without redundant work.

Interview Quick-Check

Core Logic

The algorithm tries each column in the current row, skipping those that conflict with existing queens, and uses recursion to build solutions incrementally.

State & Boundaries

The base case occurs when all rows have queens placed, at which point the current board configuration is recorded.

Common Pitfalls & Bugs

Failing to remove queens and update tracking sets during backtracking leads to incorrect conflict detection and missed solutions.

Start Backtracking from the First Row and Return All Solutions

32backtrack(0)
33return res

Objective

To initiate the recursive search from the first row and return the collected valid board configurations.

Key Insight

Starting from row zero triggers the full exploration of the solution space. Returning the accumulated results after backtracking completes provides the final answer. This step connects the recursive search to the problem's output requirements.

Interview Quick-Check

Core Logic

The initial call to backtrack(0) begins the depth-first search for valid queen placements starting from the top row.

Complexity

The overall time complexity is dominated by the backtracking recursion exploring valid permutations.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 27 Critical

col.remove(c)

Remove the current column from the occupied set during backtracking.

This state restoration is critical; it ensures that after exploring one branch, the algorithm correctly resets the column occupancy to allow other branches to be explored without false conflicts.

Line 11 Critical

if r == n:

Check if all rows have been processed (base case).

When r equals n, a valid configuration has been found, signaling the recursion to record the solution and backtrack.

Line 17 Critical

if c in col or (r + c) in pos_diag or (r - c) in neg_diag:

Skip columns that are already occupied or conflict on diagonals.

This pruning step prevents invalid queen placements early, drastically reducing the search space and improving efficiency.

Line 25 Critical

backtrack(r + 1)

Recursively attempt to place queens in the next row.

This recursive call explores deeper levels of the solution space, building on the current partial placement.

Line 28 Critical

pos_diag.remove(r + c)

Remove the positive diagonal from the occupied set during backtracking.

Restoring the positive diagonal state is essential to correctly explore other queen placements without incorrect conflict detection.

Line 29 Critical

neg_diag.remove(r - c)

Remove the negative diagonal from the occupied set during backtracking.

Restoring the negative diagonal state is essential to correctly explore other queen placements without incorrect conflict detection.

Line 3 Core

col = set()

Initialize a set to track occupied columns.

Tracking columns in a set allows constant-time checks to ensure no two queens share the same column, which is essential for pruning invalid placements.

Line 4 Core

pos_diag = set()

Initialize a set to track occupied positive diagonals (r + c).

Positive diagonals are uniquely identified by the sum of row and column indices; tracking them prevents diagonal conflicts efficiently.

Line 5 Core

neg_diag = set()

Initialize a set to track occupied negative diagonals (r - c).

Negative diagonals are uniquely identified by the difference of row and column indices; tracking them prevents diagonal conflicts efficiently.

Line 12 Core

copy = ["".join(row) for row in board]

Create a copy of the current board configuration as a list of strings.

Copying the board state ensures the recorded solution is immutable and unaffected by future backtracking steps.

Line 20 Core

col.add(c)

Mark the current column as occupied by adding it to the set.

Updating the column tracking set reflects the placement of a queen, enabling conflict detection for subsequent rows.

Line 21 Core

pos_diag.add(r + c)

Mark the positive diagonal as occupied by adding (r + c) to the set.

Tracking the positive diagonal ensures no other queen can be placed on the same diagonal in future rows.

Line 22 Core

neg_diag.add(r - c)

Mark the negative diagonal as occupied by adding (r - c) to the set.

Tracking the negative diagonal ensures no other queen can be placed on the same diagonal in future rows.

Line 30 Core

board[r][c] = "."

Remove the queen from the board at position (r, c) during backtracking.

Resetting the board cell to '.' restores the board state for alternative placements, enabling exhaustive search.

Line 8 Core

board = [["."] * n for i in range(n)]

Create the n x n board initialized with '.' to represent empty cells.

Representing the board as a 2D list of characters allows easy updates when placing or removing queens and facilitates final solution formatting.

Line 13 Core

res.append(copy)

Append the copied board configuration to the results list.

Storing the solution here preserves it for final output after all recursive calls complete.

Line 18 Core

continue

Continue to next column if current position is invalid.

Skipping invalid positions avoids unnecessary recursive calls and backtracking on impossible states.

Line 23 Core

board[r][c] = "Q"

Place a queen on the board at position (r, c).

Updating the board state reflects the current partial solution and is necessary for final solution formatting.

Line 32 Core

backtrack(0)

Start the backtracking process from the first row (row 0).

Initiating the recursive search from the top row triggers the full exploration of all valid queen placements.

Line 10 Standard

def backtrack(r):

Define the recursive backtracking function to place queens starting from row r.

Encapsulating the recursive logic in a helper function enables clean state management and incremental solution building.

Line 16 Standard

for c in range(n):

Iterate over each column in the current row to try placing a queen.

Exploring all columns in the current row ensures exhaustive search for valid queen placements.

Line 33 Standard

return res

Return the list of all valid board configurations found.

Returning the accumulated results provides the final answer to the problem after exhaustive search.

Line 7 Standard

res = []

Initialize the result list to store valid board configurations.

This list accumulates all solutions found during backtracking, enabling the function to return all valid placements.

Test Your Understanding

Why is it necessary to track columns and both diagonals when placing queens?

Because queens attack vertically and diagonally, tracking columns and both positive and negative diagonals ensures no two queens threaten each other, enabling efficient pruning of invalid placements.

Don't just read it. Drill it.

Reconstruct N-Queens from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the N-Queens drill

or drill a free problem

1	`class Solution:`
2	`def solveNQueens(self, n: int) -> list[list[str]]:`
3	`col = set()`
4	`pos_diag = set()`
5	`neg_diag = set()`
6
7	`res = []`
8	`board = [["."] * n for i in range(n)]`
9
10	`def backtrack(r):`
11	`if r == n:`
12	`copy = ["".join(row) for row in board]`
13	`res.append(copy)`
14	`return`
15
16	`for c in range(n):`
17	`if c in col or (r + c) in pos_diag or (r - c) in neg_diag:`
18	`continue`
19
20	`col.add(c)`
21	`pos_diag.add(r + c)`
22	`neg_diag.add(r - c)`
23	`board[r][c] = "Q"`
24
25	`backtrack(r + 1)`
26
27	`col.remove(c)`
28	`pos_diag.remove(r + c)`
29	`neg_diag.remove(r - c)`
30	`board[r][c] = "."`
31
32	`backtrack(0)`
33	`return res`

1	`import java.util.*;`
2
3	`public class Solution {`
4	`public List<List<String>> solveNQueens(int n) {`
5	`Set<Integer> col = new HashSet<>();`
6	`Set<Integer> posDiag = new HashSet<>();`
7	`Set<Integer> negDiag = new HashSet<>();`
8
9	`List<List<String>> res = new ArrayList<>();`
10	`char[][] board = new char[n][n];`
11	`for (int i = 0; i < n; i++) {`
12	`Arrays.fill(board[i], '.');`
13	`}`
14
15	`backtrack(0, n, col, posDiag, negDiag, board, res);`
16	`return res;`
17	`}`
18
19	`private void backtrack(int r, int n, Set<Integer> col, Set<Integer> posDiag, Set<Integer> negDiag, char[][] board, List<List<String>> res) {`
20	`if (r == n) {`
21	`List<String> copy = new ArrayList<>();`
22	`for (int i = 0; i < n; i++) {`
23	`copy.add(new String(board[i]));`
24	`}`
25	`res.add(copy);`
26	`return;`
27	`}`
28
29	`for (int c = 0; c < n; c++) {`
30	`if (col.contains(c) \|\| posDiag.contains(r + c) \|\| negDiag.contains(r - c)) {`
31	`continue;`
32	`}`
33
34	`col.add(c);`
35	`posDiag.add(r + c);`
36	`negDiag.add(r - c);`
37	`board[r][c] = 'Q';`
38
39	`backtrack(r + 1, n, col, posDiag, negDiag, board, res);`
40
41	`col.remove(c);`
42	`posDiag.remove(r + c);`
43	`negDiag.remove(r - c);`
44	`board[r][c] = '.';`
45	`}`
46	`}`
47	`}`

1	`var solveNQueens = function(n) {`
2	`const col = new Set();`
3	`const posDiag = new Set();`
4	`const negDiag = new Set();`
5
6	`const res = [];`
7	`const board = Array.from({ length: n }, () => Array(n).fill('.'));`
8
9	`function backtrack(r) {`
10	`if (r === n) {`
11	`const copy = board.map(row => row.join(''));`
12	`res.push(copy);`
13	`return;`
14	`}`
15
16	`for (let c = 0; c < n; c++) {`
17	`if (col.has(c) \|\| posDiag.has(r + c) \|\| negDiag.has(r - c)) {`
18	`continue;`
19	`}`
20
21	`col.add(c);`
22	`posDiag.add(r + c);`
23	`negDiag.add(r - c);`
24	`board[r][c] = 'Q';`
25
26	`backtrack(r + 1);`
27
28	`col.delete(c);`
29	`posDiag.delete(r + c);`
30	`negDiag.delete(r - c);`
31	`board[r][c] = '.';`
32	`}`
33	`}`
34
35	`backtrack(0);`
36	`return res;`
37	`};`

3	`col = set()`
4	`pos_diag = set()`
5	`neg_diag = set()`
7	`res = []`
8	`board = [["."] * n for i in range(n)]`

1	`#include <vector>`
2	`#include <string>`
3	`#include <unordered_set>`
4
5	`using namespace std;`
6
7	`class Solution {`
8	`public:`
9	`vector<vector<string>> solveNQueens(int n) {`
10	`unordered_set<int> col;`
11	`unordered_set<int> pos_diag;`
12	`unordered_set<int> neg_diag;`
13
14	`vector<vector<string>> res;`
15	`vector<vector<char>> board(n, vector<char>(n, '.'));`
16
17	`backtrack(0, n, col, pos_diag, neg_diag, board, res);`
18	`return res;`
19	`}`
20
21	`private:`
22	`void backtrack(int r, int n, unordered_set<int>& col, unordered_set<int>& pos_diag, unordered_set<int>& neg_diag, vector<vector<char>>& board, vector<vector<string>>& res) {`
23	`if (r == n) {`
24	`vector<string> copy;`
25	`for (int i = 0; i < n; ++i) {`
26	`copy.emplace_back(board[i].begin(), board[i].end());`
27	`}`
28	`res.push_back(copy);`
29	`return;`
30	`}`
31
32	`for (int c = 0; c < n; ++c) {`
33	`if (col.count(c) \|\| pos_diag.count(r + c) \|\| neg_diag.count(r - c)) {`
34	`continue;`
35	`}`
36
37	`col.insert(c);`
38	`pos_diag.insert(r + c);`
39	`neg_diag.insert(r - c);`
40	`board[r][c] = 'Q';`
41
42	`backtrack(r + 1, n, col, pos_diag, neg_diag, board, res);`
43
44	`col.erase(c);`
45	`pos_diag.erase(r + c);`
46	`neg_diag.erase(r - c);`
47	`board[r][c] = '.';`
48	`}`
49	`}`
50	`};`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Board and Tracking Sets for Backtracking

Place Queens Row-by-Row Using Backtracking with Conflict Checks

Start Backtracking from the First Row and Return All Solutions

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.