分支限界算法求解八皇后问题java
时间: 2023-07-26 14:11:49 浏览: 120
八皇后问题是指在 8x8 的棋盘上放置 8 个皇后,使得每个皇后都无法攻击到其他皇后(即不在同一行、同一列、同一对角线上)。分支限界算法是一种常用于解决搜索问题的算法,可以用来解决八皇后问题。
以下是使用 Java 实现八皇后问题的分支限界算法的代码:
```
public class EightQueens {
private static int[] solution = new int[8]; // 存储每行皇后的位置
public static void main(String[] args) {
solve(0); // 从第一行开始搜索
}
private static void solve(int row) {
if (row == 8) { // 找到一组解
printSolution();
return;
}
for (int col = 0; col < 8; col++) {
if (isValid(row, col)) { // 判断当前位置是否合法
solution[row] = col;
solve(row + 1); // 递归搜索下一行
}
}
}
private static boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
int diff = Math.abs(solution[i] - col);
if (diff == 0 || diff == row - i) { // 判断是否在同一列或同一对角线上
return false;
}
}
return true;
}
private static void printSolution() {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (solution[i] == j) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println();
}
}
```
在 `solve` 方法中,每次搜索一行时循环遍历该行的所有列,判断当前位置是否合法。如果合法,将该位置存储到 `solution` 数组中,并递归搜索下一行。如果搜索到最后一行,说明找到了一组解,调用 `printSolution` 方法打印出解。
在 `isValid` 方法中,判断当前位置是否在同一列或同一对角线上。如果在同一列,返回 false;如果在同一对角线上,差的绝对值等于行数之差,则返回 false。
在 `printSolution` 方法中,打印出每个皇后的位置,用 "Q" 表示皇后,"." 表示空格。
运行该程序,可以得到八皇后问题的所有解。
阅读全文
相关推荐















