一、问题描述
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
二、解决思路
首先明确每一行只能放置一个棋子，那么每一行的放置位置假设为路径树的节点位置，从0行到i行，每一列代表一个可能的解，重而定义解空间
n皇后.png
限界函数则是判断当前位置，和已经放置节点的位置有没有冲突，如果没有冲突则代表可以放置，否则不能，这个问题是求解所有的解决算法，所以没有剪枝函数
三、代码
public class NQueen {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//记录所有的结果
List<List<Integer>> allResult = new ArrayList<>();
//记录当前流程节点状态
int[] currentValue = new int[n];
calc(allResult,currentValue,0,n);
System.out.println(allResult.toString());
}
/**
* 放旗子
*
* @param allResult
* @param currentValue
* @param i
*/
public static void calc(List<List<Integer>> allResult, int[] currentValue, int i, int n) {
// 搜索结束 i大于数组的长度
if (i > n - 1) {
//代表找到一种可能解加入到所有的解之中
allResult.add(Arrays.stream(currentValue).boxed().collect(Collectors.toList()));
}
/**
* 搜索过程 就是判断当前列是否能够存放
*/
for (int j = 0; j < n; j++) {
if (isOK(currentValue, i, j, n)) {
// 代表当前点可以放
currentValue[i] = j;
// 递归进行下一行的存放
calc(allResult, currentValue, i + 1, n);
}
}
}
/**
* 判断当前位置是否能够放置棋子
*
* @param currentValue
* @param i 当前棋子索引
* @param j 列
* @param n 总大小
* @return
*/
private static boolean isOK(int[] currentValue, int i, int j, int n) {
//找到是否和当前节点同列或者同斜线的 循环每一行
for (int k = 0; k < i; k++) {
//找同列
if (currentValue[k] == j) {
return false;
}
//获得第k行的l列 对角线左侧
int l = j - (i - k);
int r = j - l + j;
//判断是不是在一个横线上
if (currentValue[k] == l || currentValue[k] == r) {
return false;
}
}
return true;
}
}
