Translate 8 queens problem from python to java : need help

Question

I just begin to learn java (today),

To exercise me, I would like to translate the following "8 Queens" algorithm written in python into Java :

BOARD_SIZE = 8

def under_attack(col, queens):
    left = right = col
    for r, c in reversed(queens):
        left, right = left-1, right+1
        if c in (left, col, right):
            return True
    return False

def solve(n):
    if n == 0: return [[]]
    print n
    smaller_solutions = solve(n-1)
    return [solution+[(n,i+1)] for i in range(BOARD_SIZE) for solution in smaller_solutions if not under_attack(i+1, solution)]

sols = solve(BOARD_SIZE)
for answer in sols:
    print answer

For translation, I want to use exactly the same algorithm : recursive and use of "lists of lists of tuple" like in python (I know I should think "java", but for now, it's just for fun)

I wrote this :

import java.util.ArrayList;

class Queens {


    public static boolean under_attack(int col, ArrayList<Integer[]> queens) {
        int left = col, right = col;
        for(int i=queens.size()-1;i>=0;i--) {
            int r = queens.get(i)[0];
            int c = queens.get(i)[1];
            left--;
            right++;
            if ( c==left || c==col || c==right)  {
                return true;
            } 
        }
        return false;
    }

    public static ArrayList<ArrayList<Integer[]>> solve(int n){
        ArrayList<ArrayList<Integer[]>> new_solutions = new ArrayList<ArrayList<Integer[]>>();
        if ( n==0 ) {
            return new_solutions;
        }
        ArrayList<ArrayList<Integer[]>> smaller_solutions = solve(n-1);

        for (int i=0;i<8;i++) {
            for (ArrayList<Integer[]> solution : smaller_solutions) {
                if ( ! under_attack(i+1,solution) ) {
                   ArrayList<Integer[]> bigger_solution = (ArrayList<Integer[]>) solution.clone();
                   Integer [] tuple = new Integer [2];
                   tuple[0] = n;
                   tuple[1] = i+1;                   
                   bigger_solution.add(tuple);
                   new_solutions.add(bigger_solution);
                }
            }
        }
        return new_solutions;

    }

    public static void main(String[] args) {
        System.out.println("Résolution du problème des 8 reines");
        ArrayList<ArrayList<Integer[]>> solutions;
        solutions = solve(8);
        System.out.format("Nb solutions : %d%n",solutions.size());
        for (ArrayList<Integer[]> solution : solutions) {
            System.out.print("(");          
            for(Integer[] i:solution) {
                System.out.format("[%d,%d],",i[0],i[1]);            
            }
            System.out.println(")");        
            System.out.println("==============================");       
        }       
    }    
}

But this does not work : no answers is found

Do you have an idea why ?

Answer 1

The correction needed to your code to run identicaly to the python program is the following. At the begining of the solve() function instead of:

    if ( n==0 ) {
        return new_solutions;
    }

you should write:

    if ( n==0 ) {
        ArrayList<Integer[]> empty = new ArrayList<Integer[]>();
        new_solutions.add(empty);
        return new_solutions;
    }

The reason is that the artifact [[]] in python is not an empty list, right? It is a list containing as it's only element the empty list. This is exactly the correction in the java code! Otherwise the recursion doesn't work and the under_attack() function is never called (as you can verify adding a diagnostic message at its first line)

Happy coding...and java learning