Программа возврата Java для N Queen: ошибка 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 для практики,Однако переписанный код вызвал ошибку StackOverFlow при его выполнении.Это следующее:

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.StackOverflowError
    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-код вызывает ошибку StackOverFlow, в то время как код 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 все еще может быть расширено, и снова вызвать `extended Что произойдет в цикле, и вы получите бесконечную рекурсию.

С новой версией вы рекурсивны, только когда добавили что-то к perm.