這題是dfs套路俄讹，按照常理想的話我們需要一個存儲坐標(biāo)的數(shù)據(jù)結(jié)構(gòu)哆致，但這題只要一個一維數(shù)組就夠了，因為n皇后的橫坐標(biāo)正好是0~n-1患膛，而且每個slot只會有一個皇后摊阀。那表，（row踪蹬，col(row)）就代表Queen的坐標(biāo)胞此。
對于4皇后，前兩次遞歸的樣子是這樣的：
首先跃捣，找到了row == 2的時候漱牵，發(fā)現(xiàn)每一個slot都不符合條件，咋辦呢疚漆，不能繼續(xù)DFS下去了酣胀，
結(jié)果集是(0,0) (1,2) (2,3) ____
col [] = {0,2,3,0} 第四個0是初始化的
這時候按理說應(yīng)該結(jié)束上次DFS，然后去掉上次加進(jìn)來的那個數(shù)字愿卸，
1000
0010
0001
0000
如果是這樣的二維數(shù)組灵临，就要把(2,3)的那個皇后拿走，置0趴荸，這樣才能在第3行重新放一個皇后儒溉，但一維數(shù)組只有一個坑啊，回到row-1发钝，再下來的時候顿涣，col[2]自然會被覆蓋。所以不用remove操作酝豪。
下面的代碼看上去很長涛碑，其實dfs函數(shù)的部分只有底下的遞歸是核心，上面的if是用來打印結(jié)果的孵淘。
這題就是典型的for循環(huán)里面進(jìn)行遞歸的問題蒲障。在dfs條件不滿足的時候
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橫坐標(biāo)表示Q所在行，縱坐標(biāo)表示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;
}
