n 皇后问题 研究的是如何将 n
个皇后放置在 n × n
的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n
,返回 n 皇后问题 不同的解决方案的数量。
问题解析
经典的递归回溯算法,尝试向下去放下一步棋,不行就回溯
代码如下:
主方法调用
arr代表对应行的几号位下了棋
eg:arr[8] = 8,代表在第8行的第8列下了棋
public int totalNQueens(int n) {
arr = new int[n];
max = n;
count = 0;
check(0);
System.out.println(count);
return count;
}
递归下棋,如果n==max代表得到一次答案,如果没有走到max就进行循环判断,对当前行的每一个位置进行判断,如果这一个位置可以下棋,就递归到下一行继续判断,如果整行都不满足,就会自动回溯.
public void check(int n) {
if (n == max) {
count++;
return;
} else {
for (int i = 0; i < max; i++) {
arr[n] = i;
if (judge(n)) {
check(n + 1);
}
}
}
}
判断
private boolean judge(int n) {
for (int i = 0; i < n; i++) {//判断和之前的皇后是否冲突,n代表现在这行,i代表之前放好的行
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {//判断是否是同一列或者是斜线上
return false;
}
}
return true;
}