N 皇后问题_用回溯法解N皇后问题

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

class Solution {
private List<List<String>> res = new ArrayList<>();
private boolean[] col;    // false 代表竖方向没有皇后
private boolean[] dia1;   // false 代表 左下 到 上右 对角线没有皇后, 这条对角线所有元素横纵坐标和相同
private boolean[] dia2;   // false 代表 左上 到 下右 对角线没有皇后, 这条对角线所有元素横纵坐标差相同
public List<List<String>> solveNQueens(int n) {
if(n < 1)
return res;
col = new boolean[n];
dia1 = new boolean[2*n-1];  // 对角线条数
dia2 = new boolean[2*n-1];
LinkedList<Integer> row = new LinkedList<>();
putQueue(n, 0, row);
return res;
}
// 尝试在一个n皇后问题中，摆放第index行的皇后位置
public void putQueue(int n, int index, LinkedList<Integer> row){
if(index == n){
res.add(generateBoard(n ,row));
return ;
}
for(int i=0; i<n; i++)
if( !col[i] && !dia1[index+i] && !dia2[index-i+n-1]){   // index-i+n-1 ：将横纵坐标差值转换为数组坐标
row.addLast(i);
col[i] = true;
dia1[i+index] = true;
dia2[index-i+n-1] = true;
putQueue(n, index+1, row);
row.removeLast();
col[i] = false;
dia1[i + index] = false;
dia2[index-i+n-1] = false;
}
return ;
}
private List<String> generateBoard(int n, LinkedList<Integer> row){
assert(row.size() == n);
ArrayList<String> board = new ArrayList<>();
for(int i = 0 ; i < n ; i++){
char[] charArray = new char[n];
Arrays.fill(charArray, '.');
charArray[row.get(i)] = 'Q';
board.add(new String(charArray));
}
return board;
}
}