Java N 皇后的回溯程序：StackOverFlow 错误

Question

我目前正在上一门教授各种编程难题的在线课程。本周的题目是N-Queen问题，给出的代码写在Python。如下：

python

def can_be_extended_to_solution(perm):
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm, n):
    if len(perm) == n:
        print(perm)
        exit()

    for k in range(n):
        if k not in perm:
            perm.append(k)

        if can_be_extended_to_solution(perm):
            extend(perm, n)

        perm.pop()

extend(perm = [], n = 25)

由于我是编程新手，我唯一会一点的语言是Java，所以我在Java中重写了整个代码来练习。然而，重写的代码在执行时导致了 Whosebug 错误。如下：

java

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Please insert N in a N x N chessboard");
    int n = scanner.nextInt();
    ArrayList<Integer> perm = new ArrayList<>();
    extend(perm, n);
    scanner.close();
}

public static boolean can_be_extended_to_solution(ArrayList<Integer> perm) {
    int i = perm.size() - 1;
    int[] range = new int[i];
    for (int k = 0; k < range.length; k++) {
        range[k] = k;
    }
    for (int j : range) {
        if (i - j == Math.abs(perm.get(i) - perm.get(j))) {
            return false;
        }
    }
    return true;
}

public static void extend(ArrayList<Integer> perm, int n) {

    if (perm.size() == n) {
        for(int i = 0; i < perm.size(); i++) {
            System.out.println(perm.get(i));
            return;
        }
    }

    int[] range = new int[n];
    for (int i = 0; i < range.length; i++) {
        range[i] = i;
    }

    for (int k : range) {
        if (perm.contains(k)) {
        }
        else {
            perm.add(k);
        }
        if (can_be_extended_to_solution(perm)) {
            extend(perm, n);
        }
        perm.remove(perm.size() - 1);
    }
}

}

这是 Eclipse 控制台中的错误消息：

Please insert N in a N x N chessboard
7
Exception in thread "main" java.lang.WhosebugError
    at java.lang.Integer.equals(Unknown Source)
    at java.util.ArrayList.indexOf(Unknown Source)
    at java.util.ArrayList.contains(Unknown Source)
    at test.extend(test.java:51) // if (perm.contains(k)) {
    at test.extend(test.java:57) // extend(perm, n);
    at test.extend(test.java:57)
    at test.extend(test.java:57)
    at test.extend(test.java:57)
    at test.extend(test.java:57)
    at test.extend(test.java:57)

这两个代码看起来和我很相似，我不明白为什么我的 Java 代码会导致 Whosebug 错误，而 Python 代码却完全没有问题。

谁能告诉我我的代码有什么问题？

Answer 1

我很确定该错误存在于两种形式的代码中。将 Python 更改为：

def can_be_extended_to_solution(perm):
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm, n):
    if len(perm) == n:
        print(perm)
        exit()

    for k in range(n):
        if k not in perm:
            perm.append(k)

            if can_be_extended_to_solution(perm):
                extend(perm, n)

            perm.pop()

extend(perm = [], n = 25)

出问题的是你会看到可以添加一些 k，然后调用 extend 你会回来，尝试添加 k，找到在那里，发现 perm 仍然可以扩展，然后再次调用 `extend。这会在一个循环中发生，然后你会得到无限递归。

在新版本中，只有在向 perm 添加内容时才会递归。

Java N 皇后的回溯程序：StackOverFlow 错误

Java backtracking program for N queen: a StackOverFlow error

python

java

algorithm

n-queens