Recursive N-Queens : missing solutions

Question

I wrote a Java little algorithm of the N-Queens puzzle (with a c*c chessboard). You'll find the code of my recursive method bellow.

It doesn't find all the solutions.

What does my function

The idea is to make, in the main method, a first call to my function giving it the maximum number of queens until a solution is found, the chessboard without any queen and these new-queen's coordinates : x=0,y=0.

The function will go through the chessboard. For each square, it tests if the queen(0;0) can be placed (ie. : no threat). The queen(0;0) can be placed ? Well, we do it (modifying the chessboard) and we call the function (recursive call). This recursive call is done with : "maximum number of queens - 1", the modified chessboard, and the "new-queen's y + 1" (a bit more complicated).

Found solution with n=4 and c=4 (there are normally two solutions... !)

&&Q&

Q&&&

&&&Q

&Q&&

Recent code of my function

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) { // If there isn't any queen remaining, it means we found a solution
        drawChessboard(chessboard);
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i++) {
        for (int z = y; z < chessboard.get(i).size(); z++) {
            if(!canBePlaced(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i+1, 0, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}

Older code

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) {
        drawChessboard(chessboard); // Il n'y a plus de reine à placer => on dessine cette solution
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i++) {
        for (int z = y; z < chessboard.get(i).size(); z++) {
            if(!isAQueenAlreadyPresent(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i, (z+1 >= WIDTH) ? 0 : z+1, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}

Answer 1

Oh right, that's because how you call recursively, your doing setQueen(nb_queens-1, chessboard, i, z+1, solutions);. The z+1 part is the problem, it will always found solution at the right of the first queen you placed on the global board.

Edit: ah you found it before, nice.

So, the problem is that the for loop act as an if(z>=y) because it starts at y. It's alright when i = x (reading the first line), but not when i > x. So an easy fix is to put y = ( i == x ) ? y : 0 just after the first for loop.

There are even cleaner solution, like using a single index to go throught the whole chessboard.

I also suggest you rename your parameter as startX and startY (instead of x and y, the you can use x and y in the loop to be more clear).

Edit2: because of the rules of the games, there will never be a queen on the same line so ou can make a recursive call like setQueen(nb_queens-1, chessboard, i+1, 0, solutions); (i+1 because you start on the next line directly). Because of this, you can even remove the int y parameter from the setQueen method and always start the z loop at 0.