题目：在n阶棋盘上放n个皇后，皇后在横竖斜都不能重复。
分析：这是一道典型的回溯算法
算法：
1>如果当前的格子是可以放皇后执行2>不能放执行3>
2>往下一行找。
3>往下一列去找，如果这一行都没有，那么回溯到上一行找上一行的放皇后的下一列。
public static List<List<String>> solveNQueens(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = -1000;
}
int i = 0;
int j = 0;
List<List<String>> res = new ArrayList<>();
while (i < n) {
while (j < n) {
if (valid(a, i, j)) {
a[i] = j;
// 每次下一个都从第0列开始搜索。
j = 0;
break;
} else {
j++;
}
}
if (a[i] == -1000) {
if (i == 0) {
break;
} else {
--i;
j = a[i] + 1;
a[i] = -1000;
continue;
}
}
if (i == n - 1) {
res.add(transfer(a));
j = a[i] + 1;
a[i] = -1000;
continue;
}
++i;
}
return res;
}
private static boolean valid(int[] a, int i, int j) {
for (int k = 0; k < a.length; k++) {
if (a[k] == j || Math.abs(a[k] - j) == Math.abs(k - i)) {
return false;
}
}
return true;
}
private static List<String> transfer(int[] a) {
int len = a.length;
List<String> res = new ArrayList<>(len);
StringBuffer sb = new StringBuffer(len);
String mod = "";
for (int i = 0; i < len - 1; i++) {
sb.append('.');
}
mod = sb.toString();
for (int i = 0; i < len; i++) {
res.add(sb.insert(a[i], 'Q').toString());
sb.setLength(0);
sb.append(mod);
}
return res;
}
