Java backtracking program for N queen: a StackOverFlow error

Question

I am currently taking an online course that teaches various programming puzzles. This week's puzzle was N-Queen problem, and the presented code was written in Python. It is the following:

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)

Since I am very new to programming and the only language I know a bit is Java, I re-wrote the entire code in Java to practice. However, the re-written code caused a StackOverFlow error when it was executed. It is the following:

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

}

And this is the error message in the Eclipse console:

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)

The two codes seem similar to me, and I don't understand why my Java code is causing a StackOverFlow error while the Python code is facing no problem at all.

Can anyone tell me what's wrong in my code?

Answer 1

I'm pretty sure that the bug is in both forms of the code. Change the Python to this:

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)

What was going wrong is that you'd see that some k can be added, then call extend You'd come back in, try to add k, find it was there, find that perm still could be extended, and call `extend again. Which would happen in a loop, and you then get infinite recursion.

With the new version, you only recurse when you've added something to perm.