LC address：N-Queens I and N-Queens 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.."]
]
Analysis:
这是一道特别经典的CSP（Constraint Satisfaction Problem）问题，其根本是一种searching问题，可以用DFS，BFS等等，基本都是要利用回溯进行遍历搜索从而得到所有答案。
由于这道题的特殊性，我们可以简单的算一下这道题目的time complexity，假设我们使用最朴素的DFS，一行一行填充Queens，每一行从左到右检查可能可以投放Queen的位置，然后记录成表，以便回溯。一开始，第一行的Q可以放任意一个位置，n种选择，不妨假设是在(0, 0)这个位置；接下来考虑第二行，显然(1, 0)以及(1, 1)这两个位置已经不能再放置Q，所以第二行有n-2个可能的位置，依次往下考虑。假设第n行的选择可能是f(n)，那么我们可知，通常有 f(n) – 3 <= f(n+1) <= f(n)，而且一定存在f(n) <= n。所以大致上来说，复杂度会在O(n!)左右。（其实这个只是一个上界，因为通常f(n) < n)
其实我们也发现了，根据之前的定义，f(n+1) = f(n) – k，这个k通常是一个非负整数，而k的值越大，对搜索效率越有利。基于这个想法，我们想尽可能的剪枝，并且对于“下一步”的选择更加慎重，因为我们想尽量从选项少的“那一行”开始我们的下一步，同时又希望每一步的选择可以为我们更好地排除余下的选项。为了说明清楚，我决定用个例子来表示这种策略。
e.g. A = {a1, a2, a3}, B = {b1, b2} 假设在某一时刻，我们要从每个集合中选取某一个元素来代表这个集合。而我们又知道，元素下标奇偶性相同的是冲突选项，比如我选了a1代表A，那么我之后就不能选b1代表B而只能选b2代表B。在这个规则下，a1, b2就是一种组合。根据我们的策略，面对这种情况，我们优先从B中选取元素，因为B的选择性更小；而在B中我们又会选择b1作为预选，因为b1可以帮助我们删除a1和a3两个选项，优于b2的效果。
回到这道题目上来说，因为我们是要找到所有的组合，而不是找到一个，所以从选项少的“那一行”开始我们的下一步比较重要，而另一个原则不那么重要因为那一行所有的情况我们都需要遍历。
我的solution比较冗长，而且从LeetCode的考评上是35ms，只超过了2%的人；而另一个比较简单的DFS暴搜，不考虑CSP的剪枝优先，反而只需要8ms。但是这并不说明那个DFS的暴搜比较好，因为测试所用的n非常小，而我自己做的测试，在n=10的时候，我的用时是另一个solution的5倍，当n=15的时候，我与另一个solution的用时是一样的；若n更大，显然我的算法的复杂度会更低。这里贴上DFS暴搜的算法的link，也是值得学习的，因为这个思路更加容易懂，更加容易想到，更轻简，也更容易实施。
Solution:
public class Solution {
public List<List<String>> solveNQueens(int n) {
// the list of the grids
List<List<String>> result = new ArrayList<>();
// chosen positions for Queens
List<Integer> chosenRows = new ArrayList<>();
List<Integer> chosenCols = new ArrayList<>();
// the original possible positions for searching
List<Set<Integer>> positions = initializePos(n);
// rowCounter counts the number of posible positions on each row
// rowCounter = [n, n, ..., n] (before searching)
int[] rowCounter = initializeCounter(n);
// sb = "........" n dots
StringBuilder dotsSB = initializeSB(n);
search(positions, rowCounter, chosenRows, chosenCols, result, dotsSB);
return result;
}
// search
private void search(List<Set<Integer>> positions, int[] rowCounter,
List<Integer> chosenRows, List<Integer> chosenCols,
List<List<String>> result, StringBuilder dotsSB) {
int minRow = findMin(rowCounter);
int numOfPositions = rowCounter[minRow];
// dead end
if (numOfPositions == 0) {
return;
}
// N Quees are settled
if (numOfPositions == Integer.MAX_VALUE) {
addGrid(result, dotsSB, chosenRows, chosenCols);
return;
}
// need further seaching
rowCounter[minRow] = Integer.MAX_VALUE;
Set<Integer> colSet = positions.get(minRow);
positions.set(minRow, new HashSet<>());
chosenRows.add(minRow);
for (Integer col : colSet) {
//update chosenCol
chosenCols.add(col);
// get deleted positions
List<Integer> deletedPos = checkConflict(positions, minRow, col);
// update rowCounter
for (int i = 0; i < deletedPos.size(); i += 2) {
rowCounter[deletedPos.get(i)] -= 1;
}
// recursively call search
search(positions, rowCounter, chosenRows, chosenCols, result, dotsSB);
// restore deletedPos
for (int i = 0; i < deletedPos.size(); i += 2) {
positions.get(deletedPos.get(i)).add(deletedPos.get(i + 1));
}
// restore rowCounter
for (int i = 0; i < deletedPos.size(); i += 2) {
rowCounter[deletedPos.get(i)] += 1;
}
// restore chosenCol
chosenCols.remove(chosenCols.size() - 1);
}
// restore other variables
rowCounter[minRow] = numOfPositions;
chosenRows.remove(chosenRows.size() - 1);
positions.set(minRow, colSet);
}
// find the row with min number of possible positions
private int findMin(int[] rowCounter) {
int idx = 0;
int temp = rowCounter[0];
for (int i = 1; i < rowCounter.length; i++) {
if (rowCounter[i] < temp) {
temp = rowCounter[i];
idx = i;
}
}
return idx;
}
// add new N-Queens grid to the result
private void addGrid(List<List<String>> result, StringBuilder dotsSB,
List<Integer> chosenRows, List<Integer> chosenCols) {
List<String> grid = new ArrayList<>();
for (int i = 0; i < chosenRows.size(); i++) {
grid.add(null);
}
for (int i = 0; i < chosenRows.size(); i++) {
dotsSB.replace(chosenCols.get(i), chosenCols.get(i) + 1, "Q");
String temp = dotsSB.toString();
grid.set(chosenRows.get(i), temp);
dotsSB.replace(chosenCols.get(i), chosenCols.get(i) + 1, ".");
}
result.add(grid);
}
// check the conflict when Queen is settled at selected position, return
// the deleted positions
private List<Integer> checkConflict(List<Set<Integer>> positions,
int row, int col) {
List<Integer> deletedPos = new ArrayList<>();
for (int i = 0; i < positions.size(); i++) {
Set<Integer> rowPos = positions.get(i);
if (rowPos.size() > 0) {
List<Integer> tempList = new ArrayList<>();
for (Integer cur_col : rowPos) {
if (cur_col == col || Math.abs(cur_col - col) == Math.abs(i - row)) {
deletedPos.add(i);
deletedPos.add(cur_col);
tempList.add(cur_col);
}
}
rowPos.removeAll(tempList);
}
}
return deletedPos;
}
// initialize the original possible positions
private List<Set<Integer>> initializePos(int n) {
List<Set<Integer>> pos = new ArrayList<>();
for (int i = 0; i < n; i++) {
Set<Integer> row = new HashSet<>();
for (int j = 0; j < n; j++) {
row.add(j);
}
pos.add(row);
}
return pos;
}
// initialize rowCounter
private int[] initializeCounter(int n) {
int[] counter = new int[n];
for (int i = 0; i < n; i++) {
counter[i] = n;
}
return counter;
}
// initialize stringbuilder
private StringBuilder initializeSB(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append('.');
}
return sb;
}
}
Solution code can also be found here: https://github.com/all4win/LeetCode.git
all4win78 