java - 使用递归解决 N Queens

Question

下面是我的代码，我不知道哪里错了 它编译得很好，但没有打印出正确的结果；；； 如果 N 是 4 ，结果应该是 2 4 1 3 但是，它打印了 1 3 0 0

我猜 for-loop 有问题，因为当我使用另一个值(如 5)时，它也只打印了两个数字 这是 N=5 的结果； 1 4 0 0 0

import java.util.Scanner;

public class NQueens{
    public static int N ;
    public static int [] cols;

    public static void printcols(){
        for(int i =1; i<=N; i++){
            System.out.print(cols[i] + " ");
        }
        System.out.print("\n");
    }

    public static boolean promising(int level){
        for(int i =1; i<level ; i++){
            if(cols[i] == cols[level]){
                return false;
            }else if(level-i == Math.abs(cols[level]- cols[i]))
                return false;
        }
        return true;
    }

    public static boolean queens(int level){
        if(!promising(level)){
            printcols();
            return false;
        }
        else if(level == N){
            printcols();
            return true;
        }
        for(int i =1; i<N; i++){
            cols[level+1] = i;
            if(queens(level+1)){
                return true;
            }
        }
        return false;
    }

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        cols = new int [N+1];
        queens(0);
    }
}

Answer 1

它不只是打印 1 3 0 0，而是打印每个回溯步骤，最后它没有找到任何解决方案。问题是您将基于 0 的索引和基于 1 的索引混合在一起，并最终出错。

在下一行中:

for(int i =1; i<N; i++){

您只迭代了 N-1 种可能性，将 i == N 排除在外。所以解决方法也只是允许相等:

for(int i =1; i<=N; i++){

通过此修改，程序按预期工作。