不知道简书搞什么。。刚才编辑了一下这个文章(原本是3.4写的)，结果更新之后URL失效了，怎么也找不到了。。还好之前备份过RAR。简书这一点让人有点不太让人放心了，看来要经常备份才行。
这题是dfs套路，按照常理想的话我们需要一个存储坐标的数据结构，但这题只要一个一维数组就够了，因为n皇后的横坐标正好是0~n-1，而且每个slot只会有一个皇后。那表，（row，col(row)）就代表Queen的坐标。
对于4皇后，前两次递归的样子是这样的：
首先，找到了row == 2的时候，发现每一个slot都不符合条件，咋办呢，不能继续DFS下去了，
结果集是(0,0) (1,2) (2,3) ____
col [] = {0,2,3,0} 第四个0是初始化的
这时候按理说应该结束上次DFS，然后去掉上次加进来的那个数字，
1000
0010
0001
0000
如果是这样的二维数组，就要把(2,3)的那个皇后拿走，置0，这样才能在第3行重新放一个皇后，但一维数组只有一个坑啊，回到row-1，再下来的时候，col[2]自然会被覆盖。所以不用remove操作。(我这里的理解可能有误。不需要remove的原因也许仅仅是因为 stack回到了上一个状态，那个状态下的数组col[row]还没有被插入)
下面的代码看似很长，其实dfs核心的部分很短，很大一部分是用来打印结果的。
我们知道DFS的套路，我自己总结一下大概是这样的：
- 终止条件
- 构造结果
- backtracking
- 恢复现场。
类似套路的题目有: LetterCombinationsOfAPhoneNumber、CombinationSum、Unique Binary Search Trees II 等等。
这题的终止条件里面顺便做了打印操作所以显得很长。这题不需要恢复现场现场（remove操作）。
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
if (n <= 0)
return res;
dfs(res, 0, n, new int[n]);
return res;
}
//columnVal横坐标表示Q所在行，纵坐标表示Q所在列
public void dfs(List<List<String>> result, int row, int n, int[] col) {
if (row == n) {
//col = [1,4,0,3];
List<String> cell = new ArrayList<>();
for (int i = 0; i < row; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < row; j++) {
if (col[i] == j) {
sb.append("Q");
} else {
sb.append(".");
}
}
cell.add(sb.toString());
}
result.add(new ArrayList<String>(cell));
return;
}
for (int i = 0; i < n; i++) {
col[row] = i;
if (checkValid(row, col)) {
dfs(result, row + 1, n, col);
}
}
}
public boolean checkValid(int row, int[] col) {
for (int i = 0; i < row; i++) {
if (col[i] == col[row] || Math.abs(i - row) == Math.abs(col[i] - col[row]))//同一列 || 斜线
{
return false;
}
}
return true;
}
