Java NQueens递归与枚举逻辑详解

Question

我正在做一些递归练习，遇到了 nQueens 问题 here。

我不确定我是否误解了递归发生的事情，但我不明白这段代码（下面）是如何打印问题的多个解决方案的。

例如，如果我运行程序有一个4皇后的解决方案，它会打印出：

* Q * * 
* * * Q 
Q * * * 
* * Q * 

* * Q * 
Q * * * 
* * * Q 
* Q * *

我也在踩，还是不太明白

这是我认为正在发生的事情：
1. isConsistent正在检查逻辑/在当前位置放置女王是否安全
2. printQueens 正在印刷电路板
3. enumerate(int[] q, int n) 正在递归地放置皇后以获得一个解决方案
4.（我猜）enumerate(int N) 是通过多板解决方案枚举的内容，但它只被调用一次。所以，那是不对的。所以，我的下一个想法是它只是一种调用递归枚举方法的方法。但是，这意味着一旦递归完成找到第一块板的解决方案，它就应该停止。所以，我回到原来的问题：

How/where是在计算板子的多解吗？

我知道这可能很容易，但即使使用调试器，我也无法理解正在发生的事情。如果有人能解释它从哪里开始计算板的第二个解决方案，我将不胜感激。

/******************************************************************************
 *  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);
    }

}

Answer 1

重要的部分是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);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

它将尽可能遍历整个解决方案 space。这意味着它会从没有进一步的解决方案可能出现的那一刻起中断，但它将继续到仍然可以走得更远的地方。

isConsistent方法确实是检查当前板是否仍然有效。（diagonals/column，行在递归中是隐含的）

当你遇到第N行时，当前的棋盘被打印出来。因为你的棋盘仍然有效，每行都有一个皇后。

查看 this simulation 以查看算法执行的步骤。

Java NQueens递归与枚举逻辑详解

Java NQueens Recursion and Enumeration Logic Explanation

java

recursion

n-queens