1
\$\begingroup\$

I am working on a Java textbook chapter on recursion, and I am to implement an Eight Queens solution using recursion. Though I know that I am to post working code in Code Review, I do believe this code would work if I didn't run out of memory. I have walked through the debugger, and the queens seem to adjust position exactly like they should until there is a Stack Overflow.

My question really is this: After running into this Stack Overflow issue, my instincts are to either find a way to increase Stack memory (I have not found a way to do this) or reduce Stack memory usage. To reduce Stack memory usage, I do wonder if there might be a way to put some of the weight of the recursion on the heap instead. The most likely way to reduce Stack memory usage would likely be some clever refactoring, which is why I am posting in Code Review. What I feel the best answer for this is, is just to ditch as much recursion as I can, but if I am to follow the exercise instructions, I don't have that option.

This is what I have:

Queen.java

class Queen {
    private int row;
    private int col;
    private int qNum;

    Queen(){
        row = 0;
        col = 0;
    }

    int getRow() {
        return row;
    }

    int getCol() {
        return col;
    }

    void setQNum(int qNum){
        this.qNum = qNum;
    }

    // requires canAdvance check first
    void advance(){
        if (col == 7){
            ++row;
            col = 0;
        }
        else{
            ++col;
        }
    }
    void matchPosition(Queen previousQueen){
        if (previousQueen.getCol() == 7){
            row = previousQueen.getRow() + 1;
            col = 0;
        }
        else{
            row = previousQueen.getRow();
            col = previousQueen.getCol() + 1;
        }
    }

    boolean canAdvance(){
        return !(row == 7 && col == 7);
    }

    private boolean isAttacked(Queen attacker){
        return getRow() == attacker.getRow() ||
                getCol() == attacker.getCol() ||
                Math.abs(getRow() - attacker.getRow()) ==
                        Math.abs(getCol() - attacker.getCol());
    }

    boolean isSafe(Queen[] queens){
        for(int attIndex = 0; attIndex < qNum; ++attIndex){
            if(this.isAttacked(queens[attIndex])){
                return false;
            }
        }
        return true;
    }
}

Main.java

class Main{
    public static void main(String[] args){
        Queen[] queenArr = {
                new Queen(),
                new Queen(),
                new Queen(),
                new Queen(),
                new Queen(),
                new Queen(),
                new Queen(),
                new Queen()
        };

        // Storing array index numbers allow the code to be more readable.
        for(int i = 0; i < 8; ++i){
            queenArr[i].setQNum(i);
        }

        placeQueen(queenArr, 1);
        for(Queen queen : queenArr){
            System.out.printf("row = %d  col = %d%n", queen.getRow(), queen.getCol());
        }
    }

    private static void placeQueen(Queen[] queens, int index){
        if (queens[index].canAdvance()){
            queens[index].advance();
        }
        else{
            while(index > 0 && !queens[index].canAdvance()){
                --index;
            }
            placeQueen(queens, index);
        }

        if (queens[index].isSafe(queens)){
            if (index == 7){
                return;
            }
            else{
                // next queen is set to position of current queen
                queens[index + 1].matchPosition(queens[index]);
                ++index;
            }
        }
        placeQueen(queens, index);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you tried -Xss yet? \$\endgroup\$ – mdfst13 Mar 22 '18 at 9:36
2
\$\begingroup\$

I think the place where recursion is least appropriate is when you advance a queen until it is safe from all queens with a lower index (i.e. the last line of the method placeQueen(Queen[], int)). This doesn't really seem like a recursive process to me, but rather like something that calls for a loop.

private static void placeQueen(Queen[] queens, int index) {
    while (!queens[index].isSafe(queens) && queens[index].canAdvance()) {
        queens[index].advance();
    }

    if (!queens[index].canAdvance()
            && (!queens[index].isSafe(queens)
            || index != 7)) {
        while (index > 0 && !queens[index].canAdvance()) {
            --index;
        }
        queens[index].advance();
        placeQueen(queens, index);
    } else if (index != 7) {

        // next queen is set to position of current queen
        queens[index + 1].matchPosition(queens[index]);
        ++index;
        placeQueen(queens, index);
    }
}

This advances a queen until it is either safe or can no longer be advanced, which is basically what your code did, but here, this is achieved without recursion, saving a lot of stack memory.

\$\endgroup\$
2
\$\begingroup\$

Java doesn't handle boundless recursion well. To see how bad it is try running this simple program:

public static void main(String[] args) {
    recursionCounter(1);
}

public static void recursionCounter(int i){
    System.out.println(i);
    recursionCounter(++i);
}

For me, the last number it prints is 11402 meaning we can only go roughly 11k steps deep without putting any extra variables on the stack besides that counter.

I didn't actually count it, but my intuition tells me your implementation would need to go at least 10 trillion steps deep before getting anywhere near the solution.

Stingy already suggested a way to massively reduce the recursion steps with a simple loop already. I added a counter to his program which gave me a recursion depth of 3928 (maybe 1 more, didn't check if I started counting at correct depth).

This is a nice start but still doesn't scale all too well. If we were to modify the program to place 10 queens on a slightly bigger board it probably wont work either.


So how can we do better?

The first thing to do is find a good way to model the board. A huge optimisation here is if we start by saying that each row will only ever contain 1 queen. Solving the n-queens problem then changes from

"placing N queens on the board"

to

"for each row, find the column to put the queen of that row on".

The most intuitive way to represent this board now for me is to just store an array of ints.

int[] queens = new int[8];

The next major thing I would change to your aproach is to introduce backtracking. The general algorithm will look like this:

1) start by placing the queen on the first column.
2) if this queen is not attacking any of the queens on the previous rows and it's possible to solve for all the following queens (recursive step here) return true .
3) if the previous step was not possible, move the queen to the next column and go back to step 2.
4) no solution was found given the previous queen positions, return false. (backtracking happens here, we go back to the previous queen on the stack and go to step 3 on that one).

Or turning all that into code:

public static void main(String[] args) {
    int[] queens = new int[8];
    solve(queens, 0);
    prettyPrint(queens);
}

/**
 * try to find a valid column for the queen on row i and recursively call for all the next rows.
 */
private static boolean solve(int[] queens, int i) {
    if(i >= queens.length) {
        return true;
    }

    for(queens[i] = 0; queens[i] < queens.length ; queens[i]++) {
        if(!isAttacking(queens, i) && solve(queens, i+1)){
            return true;
        }
    }
    return false;
}

/**
 * check if the queen on the given row is attacking a queen on any of the previous rows
 */
private static boolean isAttacking(int[] queens, int row){
    //check same column
    for(int prevRow = 0; prevRow < row; prevRow++){
        if (queens[prevRow] == queens[row]) {
            return true;
        }
    }

    //check diagonals
    for(int prevRow = 0; prevRow < row; prevRow++) {
        if(Math.abs(prevRow - row) ==
                Math.abs(queens[prevRow] - queens[row])){
            return true;
        }
    }
    return false;
}

private static void prettyPrint(int[] queens){
    StringBuilder output = new StringBuilder();
    for (int row : queens) {
        for (int col = 0; col < queens.length; col++) {
            if (row == col) {
                output.append('Q');
            } else {
                output.append('_');
            }
            output.append('|');
        }
        output.append('\n');
    }
    System.out.println(output.toString());
}

I took the liberty to also provide a method to print out the solution as a grid.

Notice how there is no check needed for 2 queens attacking on the same row. The way we represented the board made this impossible from the start.

If you want to solve the NQueens for a different N, just increase the initial size of the array. Even for int[] queens = new int[20]; it should find a solution nearly instantly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.