CODEWITHSUNDEEP
javarecursionstack-overflow
user145296
user145296

Reputation: 11

Optimizing N Queens code to avoid stack overflow

i've been trying to write a java class to solve the n queens problem using some sort of stacking and recursion, the answers are stored in grids(two dimensionnal arrays), but i've hit a dead wall which is stack overflow for recursion at n=8 (max recursion depth reached 2298) So i've been wondering if there is some way to bypass this dead by doing something complex like allocating more heap space in java(if possible?) or using multi thread(point me out to a tutorial/examples)... or please do advice on how to optimize the code... Thanks in advance

    public void resoudre(){

        this.gridPile.push(copyGrid(grid));
        try{
            int row = gridPile.size()-1;
            if(gridPile.size()==0)row = 0;
            chooseGridSpace(this.grid, locateFirstAvailable(grid, row));
            if(gridPile.size() == this.taille){
                gridSolutions.push(copyGrid(grid));
                grid = gridPile.pop();
                boolean erronous = true;
                while(erronous){
                    try{
                        MakeNextUnavailable(grid, gridPile.size());
                        erronous = false;
                    }
                    catch(UnavailabilityException r1){
                        try{
                            grid = gridPile.pop();
                        }
                        catch(java.util.EmptyStackException r2){
                            return;
                        }
                    }
                }
            }

        }
        catch(InvalidPositionException e1){
            this.grid = gridPile.pop();
            boolean error = true;
            while(error){
                try{
                    MakeNextUnavailable(grid, gridPile.size());
                    error = false;
                }
                catch(UnavailabilityException er){
                    try{
                        this.grid = gridPile.pop();
                    }
                    catch(java.util.EmptyStackException err){
                        return;
                    }
                }
            }
        }
        catch(java.lang.ArrayIndexOutOfBoundsException e2){
            return;
        }
        this.resoudre();
    }

    private static void chooseGridSpace(int[][] grid, Position a){
        grid[a.getLigne()][a.getColonne()] = 1;
        fillNotAvailable(grid, a);
    }

Upvotes: 1

Views: 1961

Answers (4)

vog
vog

Reputation: 25607

Direct answer: There's no need to push whole grids onto the stack, and you might want to represent the grid as array of 8 integers denoting the Queen position at each row.

Real problem: Your code is too long and too complicated. Keep it simple! The queen's problem is usually solved by 2 functions of <10 lines each. Is is as simple as:

public static boolean isSolution(final int[] board)
{
    for (int i = 0; i < board.length; i++) {
        for (int j = i + 1; j < board.length; j++) {
            if (board[i] == board[j]) return false;     // same column "|"
            if (board[i]-board[j] == i-j) return false; // diagonal "\"
            if (board[i]-board[j] == j-i) return false; // diagonal "/"
        }
    }
    return true;
}

public static void solve(int depth, int[] board)
{
    if (depth == board.length && isSolution(board)) {
        outputSolution(board);
    }
    if (depth < board.length) {  // try all positions of the next row
        for (int i = 0; i < board.length; i++) {
            board[depth] = i;
            solve(depth + 1, board);
        }
    }
}

Add some output code and a main program, and you're finished! 

public static void outputSolution(final int[] board)
{
    System.out.println("--- Solution ---");
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i]; j++) System.out.print(" ");
        System.out.println("Q");
    }
}

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

Upvotes: 4

ripper234
ripper234

Reputation: 230058

No reason to reach stack depth of 2298 for N = 8!

The correct algorithm is to represent the queens by an array of 8 integers, each representing the row position of the ith queen (queen per column).

Your max stack size should be 8.

Upvotes: 0

Stephen C
Stephen C

Reputation: 718946

Reading the code, it looks like your program is using a Stack<..> and not Java recursion. Therefore it is probably running out of Java heap space rather than Java stack space. If that is the case, you can use the -Xms and -Xmx options to increase the initial and maximum heap sizes.

Upvotes: 0

Dan Lorenc
Dan Lorenc

Reputation: 5394

In Java, the commands -ss and -oss can both be used to change the stack size. 

$java -ss156k (native) 
$java -oss600k (Java)

The argument is the stack size you would like in kbytes or mbytes. Experiment with some increased values until you don't overflow.

Upvotes: -3

Related Questions