# LeetCode N-Queens I and II: Backtracking and DFS

## Overview

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.

## LeetCode N-Queens I and II

The *n*-queens puzzle is the problem of placing *n* queens on an *n* * *n* chessboard such that no two queens attack each other.

Given an integer *n*, return all distinct solutions to the *n*-queens puzzle.

Each solution contains a distinct board configuration of the *n*-queens’ placement, where `'Q'`

and `'.'`

both indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

(2)

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

## Analysis: Backtracking and DFS

Both could be solved by backtracking algorithm with pruning. When generating candidates, remove all the positions which obviously lead to conflicts (Queens attack). After all the n queens are placed, the final configuration is stored for I and the global count increases by 1 for II. The following code enumerates all the valid solutions for the N-Queens problem and could be adjusted a bit to solve the second one and it is accepted by LeetCode OJ to pass both N-Queens problems:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
public:
vector<vector<string>> results;
vector<string> board;
vector<int> cols;
void dfs(int k, int n) {
if (k == n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
board[i][j] = '.';
if (cols[i] == j) board[i][j] = 'Q';
}
}
results.push_back(board);
return ;
}
for (int j = 0; j < n; ++j) {
bool cand = true;
for (int i = 0; cand && i < k; ++i) {
if (cols[i] == j || abs(k - i) == abs(cols[i] - j)) {
cand = false;
}
}
if (cand) {
cols[k] = j;
dfs(k + 1, n);
}
}
}
vector<vector<string> > solveNQueens(int n) {
results.clear();
if (n == 1) {
vector<string> vec;
vec.push_back("Q");
results.push_back(vec);
return results;
}
if (n <= 3)
return results;
cols.resize(n);
fill(cols.begin(), cols.end(), -1);
board.resize(n);
for (int i = 0; i < n; ++i) board[i].resize(n);
dfs(0, n);
return results;
}
};

**Remarks:**

- For II, one might still save some time computation by the symmetric property. And for this classical N-Queens problem, n can’t be too large, when n = 14, it might take several minutes to solve.
- What about iterative implementation? Is it easier? You might also want to search the bit mask solution for any further reference

## Summary

LeetCode N-Queens I and II are the classic backtracking problems which could be solved by using DFS + Pruning to enumerate all the solutions.