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)

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:

```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:

1. 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.
2. 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.

Written on May 26, 2013