- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在做一些递归练习,遇到了 nQueens 问题 here .
我不确定我是否误解了递归发生的情况,但我不明白这段代码(如下)如何打印问题的多个解决方案。
例如,如果我使用 4 皇后解决方案运行程序,则会打印出:
* Q * *
* * * Q
Q * * *
* * Q *
* * Q *
Q * * *
* * * Q
* Q * *
我也在逐步解决,但还是不太明白。
我认为正在发生的事情是这样的:
1. isConstant正在检查逻辑/在当前位置放置皇后是否安全
2. printQueens 正在打印棋盘
3. enumerate(int[] q, int n) 递归地为一个解决方案放置皇后
4.(我猜)enumerate(int N)是通过多板解决方案枚举的,但它只被调用一次。所以,这不可能是正确的。所以,我的下一个想法是,它只是一个调用递归枚举方法的方法。但是,这意味着一旦递归完成找到第一 block 板的解决方案,它就应该停止。所以,我回到原来的问题:
如何/在哪里计算电路板的多个解决方案?
我知道这可能很容易,但即使使用调试器,我也很难了解正在发生的事情。如果有人可以解释它从哪里开始计算董事会的第二个解决方案,我将不胜感激。
/******************************************************************************
* Compilation: javac Queens.java
* Execution: java Queens N
*
* Solve the 8 queens problem using recursion and backtracing.
* Prints out all solutions.
*
* Limitations: works for N <= 25, but slows down considerably
* for larger N.
*
* Remark: this program implicitly enumerates all N^N possible
* placements (instead of N!), but the backtracing prunes off
* most of them, so it's not necessarily worth the extra
* complication of enumerating only permutations.
*
*
* % java Queens 3
*
* % java Queens 4
* * Q * *
* * * * Q
* Q * * *
* * * Q *
*
* * * Q *
* Q * * *
* * * * Q
* * Q * *
*
* % java Queens 8
* Q * * * * * * *
* * * * * Q * * *
* * * * * * * * Q
* * * * * * Q * *
* * * Q * * * * *
* * * * * * * Q *
* * Q * * * * * *
* * * * Q * * * *
*
* ...
*
******************************************************************************/
public class Queens {
/***************************************************************************
* Return true if queen placement q[n] does not conflict with
* other queens q[0] through q[n-1]
***************************************************************************/
public static boolean isConsistent(int[] q, int n) {
for (int i = 0; i < n; i++) {
if (q[i] == q[n]) return false; // same column
if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
}
return true;
}
/***************************************************************************
* Print out N-by-N placement of queens from permutation q in ASCII.
***************************************************************************/
public static void printQueens(int[] q) {
int N = q.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) StdOut.print("Q ");
else StdOut.print("* ");
}
StdOut.println();
}
StdOut.println();
}
/***************************************************************************
* Try all permutations using backtracking
***************************************************************************/
public static void enumerate(int N) {
int[] a = new int[N];
enumerate(a, 0);
}
public static void enumerate(int[] q, int n) {
int N = q.length;
if (n == N) printQueens(q);
else {
for (int i = 0; i < N; i++) {
q[n] = i;
if (isConsistent(q, n)) enumerate(q, n+1);
}
}
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
enumerate(N);
}
}
最佳答案
重要的部分是enumerate
方法。它保存一个整数数组,表示每行的列索引。
例如:
* Q * *
* * * Q
Q * * *
* * Q *
q
看起来像:
q[0] = 1
q[1] = 3
q[2] = 0
q[3] = 2
它确实是递归的,但不仅仅是一种解决方案。它将使用回溯而不是重新计算所有内容。
例如,对于 N=4
,代码的运行等效于以下内容:
public static void enumerate(int[] q, int n) {
for(int a0=0;a0<4;a0++){
q[0]=a0;
if(isConsistent(q, 0)){
for(int a1=0;a1<4;a1++){
q[1]=a1;
if(isConsistent(q, 1)){
for(int a2=0;a2<4;a2++){
q[2]=a2;
if(isConsistent(q, 2)){
for(int a3=0;a3<4;a3++){
q[3]=a3;
if(isConsistent(q, 3)){
printQueens(q);
}
}
}
}
}
}
}
}
}
它将尽可能遍历整个解决方案空间。这意味着从行无法进一步解决问题的那一刻起,它将中断,但它将继续到仍然可以进一步解决的地方。
isConstant
方法确实在检查当前棋盘是否仍然有效。 (对角线/列,行在递归中隐式)
当前棋盘会在您遇到第 N 行时打印出来。因为你的棋盘仍然有效,每行都有一个皇后。
查看this simulation查看算法执行的步骤。
关于Java NQueens递归和枚举逻辑讲解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34258009/
在用 values-list 解决了我的错误并能够运行我的程序直到结束后,我发现我的对角线检查似乎有逻辑错误。我的输入如下: (威胁?'(1 3)'((1 0)(2 4)(3 0)(4 0)(5 0)
我是 JAVA 新手。下面是我的 NQueens 问题的代码。结果是 [[Ljava.lang.String;@123a439b, [Ljava.lang.String;@7de26db8]。 有人可
我编写了一种使用递归和回溯来找到 N 皇后问题的解决方案的方法。我现在要做的是修改这个方法,让它找到所有可能的解决方案。我假设我需要使用一个二维整数数组来存储所有的解决方案,并且还添加一个计数器,每次
我的 NQueens isSafeMove() 函数不断返回 false,我不明白为什么。我相信这可能与我的 checkLeft、checkUpperDiag 或 checkLowerDiag 有关,
我正在用 open mp 解决 n Queens 问题, (最初的八皇后问题包括试图找到一种方法将八个皇后放在棋盘上,这样没有皇后会攻击任何其他皇后。表达该问题的另一种方式是将八个“任何东西”放在一个
前几天我问了一个关于我的 nQueens 问题的问题,并收到了很多很好的答案,所以我想我会再问一次,因为我非常接近完成这个威胁功能。我的职责是确定水平、垂直或对角线上的威胁。我的输入是这样的: (威胁
我是一名优秀的程序员,十分优秀!