回溯是一种通用的算法,把问题分步解决,在每一步都试验所有的可能,当发现已经找到一种方式或者目前这种方式不可能是结果的时候,退回上一步继续尝试其他可能。很多时候每一步的处理都是一致的。
当回溯用于树的时候,就是深度优先搜索。几乎所有可以用回溯解决的问题都可以表示为树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树,那么就叫它DFS。
class Solution {
public List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
// 下标表示行, 值表示存储在哪一列
int[] a = new int[n];
calNQueens(a, 0, n);
return result;
}
private void calNQueens(int[] a, int row, int n) {
// row = n代表n行都有皇后了
if (row == n) {
add(a);
return;
}
// 对当前行每一列进行判断
for (int column = 0; column < n; column++) {
if (isOk(a, row, column, n)) {
a[row] = column;
// 当当前列符合条件, 则进行下一行的判断
calNQueens(a, row + 1, n);
}
}
}
/**
* 判断在当前坐标放上棋子, 是否满足所有条件
*
* @param a 棋盘
* @param row 当前行
* @param column 当前列
* @param n 一共多少颗棋子
* @return 是否满足条件
*/
private boolean isOk(int[] a, int row, int column, int n) {
// l代表左上对角线, r代表右上对角线
// 上一行的左对角线所在点就是 column - 1, 右对角线 column + 1
int l = column - 1, r = column + 1;
// i代表行
for (int i = row - 1; i >= 0; i--) {
if (a[i] == column) return false;
// 判断对角线, a[i] == l 就代表在某一行的l列有皇后, 是处在对角线上的
if ((l >= 0 && a[i] == l) || (r < n && a[i] == r)) return false;
// 每次左对角线坐标都要减1, 右对角线加1
l--;
r++;
}
return true;
}
/**
* 把可以的排列添加到result列表里
*/
private void add(int[] a) {
List<String> list = new ArrayList<>();
for (int row = 0; row < a.length; row++) {
String cStr = "";
for (int c = 0; c < a.length; c++) {
cStr += a[row] == c ? "Q" : ".";
}
list.add(cStr);
}
result.add(list);
}
}