Stuck in N-Queens java algorithm. (Backtracking)

Question

Can someone give me a hint or guidance on my java program? I am stuck on the backtracking idea. Here is the code. If you take a look at the method solve(), it recursively calls itself, however I am stuck at a point where it fails to place more queens and tries to backtrack.

public NQueens(int N)
{
    this.N = N;
    board = new boolean[N][N];
    solved = solve(N);
    if(solved == true)
    {
        System.out.println(N+"x"+N+" solution:");
        printBoard(N);
    }
    else
    {
        System.out.println("There is no solution for "+N+"x"+N+" board");
    }
}

public boolean solve(int waitingQueens)
{
    if(waitingQueens == 0) return true;

    for(int row = 0; row < N; row++)
    {

        for(int column = 0 ; column < N ; column++)
        {
            if(isValid(row, column))
            {
                board[row][column] = true;
                waitingQueens--;
                boolean solved = solve(waitingQueens);

                if(!solved)
                {
                    board[row][column] = false;

                    solved = solve(waitingQueens);
                }
                return solved;
            }

        }

    }

    return false;
}

public boolean isValid(int rowParam, int columnParam)
{
    for(int x = 0; x < N; x++)
    {
        for(int y = 0; y < N; y++)
        {
            if(board[x][y] == true) //find the already placed queens on the board and check if the queen about to be placed is on a valid position
            {
                if(x == rowParam) //check the validity of the row
                    return false;
                if(y == columnParam) //check the validity of the column
                    return false;
                if(Math.abs(x-rowParam) == Math.abs(y-columnParam)) //check the validity of the diagonals
                    return false;
            }
        }
    }
    return true;
}

public void printBoard(int printParam)
{
    for(int x1 = 0; x1 < printParam; x1++)
    {
        for(int y1 = 0; y1 < printParam; y1++)
        {
            if(board[x1][y1] == true)
            {
                System.out.print("Q ");
            }
            else{
                System.out.print("* ");
            }
        }
        System.out.println();
    }
    System.out.println();
}

Answer 1

I gather that this is the algorithm you're trying to implement: Assume you already have M queens on the board (it looks like M = N - waitingQueens or something). Then, you look for every empty square where you could place a queen. If it's valid to place a queen there, you set the square in board to true and then call solve recursively to see if you can place waitingQueens-1 more queens.

Your biggest problem lies in what happens if the recursive solve returns false. Say it's a 4x4 board and waitingQueens is 4. You'll place the first queen, then call solve with waitingQueens=3. But suppose it says there's no solution. You then do this:

            if(!solved)
            {
                board[row][column] = false;
                solved = solve(waitingQueens);
            }

This will set the square to false, which means the board is now empty again. But then you call solve(waitingQueens) with waitingQueens=3, which means your recursive solve will now look for a solution that has only 3 queens on the board. This can't be right. And re-incrementing waitingQueens back to 4 is going to lead to infinite recursion, since solve(4) will be calling solve(4) with the same empty board.

The thing here is, you're already in a double loop that will look for every square where you could put a queen. If you try to put a queen somewhere and it doesn't work out (the recursive call fails), you remove the queen, but then you let the double loop find the next valid square for you. You do not want to do another recursive call. So the above solve(waitingQueens) call should be removed.

Also, this needs to be fixed:

            waitingQueens--;
            boolean solved = solve(waitingQueens);

Decreasing waitingQueens is a bad idea, because if solve returns false, and you have to go back to the next loop iteration, waitingQueens will be one less than it was before, which is no good. You could restore it by saying waitingQueens++ in the if (!solved) branch, but why bother? Leave waitingQueens alone, and replace the above two lines with

            boolean solved = solve(waitingQueens-1);

I'm not sure if those two fixes will be enough to produce a correct answer, but they're a start. A couple other things I want to mention, although these are just optimizations: (1) Your loop in solve shouldn't even look at squares that aren't empty. The way you wrote it, isValid will return false if you give it a square that isn't empty, but it does so in a roundabout way. I'd probably check that the square is empty even before calling isValid. (2) Once you've placed M queens in rows 0 to M-1, your recursive call shouldn't even look at those rows, since we know you can't have two queens in the same row. And if you look through row M and don't find a solution, you can give up immediately, since we know that a correct solution must have a queen in every row. So you really only need a single loop in solve.