使用Java(OpenJDK14)解决:描述 使用回溯技术改进递归算法,边递归边进行check。 请你统计N皇后问题解的数量。 输入 一个正整数N(N <= 13) 输出 1个整数,代表N皇后问题解的数量;若无解,输出“No Solution!”
时间: 2024-10-24 17:18:41 浏览: 17
在Java中,我们可以利用回溯法(Backtracking)来解决N皇后问题,这是一个经典的递归问题,涉及在一个N×N的棋盘上放置N个皇后,使得任意两个皇后都不在同一行、同一列,以及同一条对角线上。以下是使用OpenJDK 14实现的一个简化版的解决方案:
```java
import java.util.ArrayList;
import java.util.List;
public class NQueens {
private static int n;
private static boolean[][] isSafe; // 存储是否安全的二维布尔数组
private static int solutions = 0; // 计数器
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
if (n > 13) {
System.out.println("No Solution!");
} else {
isSafe = new boolean[n][n];
solveNQueens(0);
System.out.println(solutions);
}
}
// 回溯函数
private static void solveNQueens(int row) {
if (row == n) { // 所有皇后都放好,计数并结束当前路径
solutions++;
return;
}
for (int col = 0; col < n; col++) { // 尝试每一列
if (isValid(row, col)) { // 检查当前位置是否安全
isSafe[row][col] = true; // 标记为安全
solveNQueens(row + 1); // 继续下一行
isSafe[row][col] = false; // 取消标记,准备尝试下一个位置
}
}
}
// 判断位置是否安全
private static boolean isValid(int row, int col) {
// 检查同一列、同一行和对角线是否有冲突
return !isSafe[row][col] && !isOffDiagonalConflict(row, col);
}
// 对角线冲突检查
private static boolean isOffDiagonalConflict(int row, int col) {
int dr = Math.abs(row - col), dc = Math.abs(n - row - col);
return isSafe[dr][dc];
}
}
```
这个程序首先读取用户输入的N值,然后通过`solveNQueens`函数递归地尝试在每一行放置皇后,并检查是否违反了规则。如果找到一个解决方案,就会增加`solutions`计数。如果没有找到合法方案,最终会输出"No Solution!"。
阅读全文