How to avoid stackoverflow error for n = 8 in N Rooks problem

Question

I want to solve N Rooks problem in N x N board using recursion with max N = 8. My code works fine for N = 2, 3, 4, 5, 6, 7. But when N = 8 it gives so many possible results starting with the first row of 1 0 0 0 0 0 0 0 then gives stackoverflow error before checking other possible results starting with the first row of 0 1 0 0 0 0 0 0.

I know about general recursion like fibonacci series, factorial, etc. and I can trace them down. Then I came across a new form of recursion called backtracking recursion. Then I sarted to learn the logic behind this form of recursion and read some pseudocode algorithms. Acually this form of recursion seemed to me a little bit harder to construct than normal recursion.

public class NRooks {
/**
 * In this code r = which row, c = which column.
 * lastY method just returns column c of last placed rook in
 * a given row r in order to remove it.
 * row.length, col.length, board.length have no special meaning. They all
 * equal to the dimension of board N.
 * main() method always initiates first row(r = 0). Therefore in main()
 * method r remains 0 and c changes as you can see in putRook(0, i). 
 * So solve() method always begins from second row(r = 1).
 */

private static int found = 0;
private static int[][] board;
private static int[] row;
private static int[] col;

public static void putRook(int r, int c) {
    board[r][c] = 1;
    row[r]  = 1;
    col[c]  = 1;
}

public static void removeRook(int r, int c) {
    board[r][c] = 0;
    row[r]  = 0;
    col[c]  = 0;
}

public static boolean isValid(int r, int c) {
    if (row[r] == 0 && col[c] == 0) return true;
    return false;
}

public static void showBoard() {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board.length; c++) {
            System.out.print(board[r][c] + " ");
        }
        System.out.println();
    }
    System.out.println();
}

public static int lastY(int r) {
    for (int j = 0; j < board.length; j++) {
        if (board[r][j] == 1) return j;
    }
    return -1;
}


public static boolean solve(int r, int c) {
    int last;

    if (r == 0) return false;

    if (r == col.length) {
        found++;
        /**
         * When I dont include below printline statement my code 
         * works fine until N = 7 then gives SO error.
         * But When I include this print statement in order
         * to print number of results my code works fine until
         * N = 6 then gives SO error
         */
        //System.out.println("Found: " + found);
        showBoard();
        r--;
        last = lastY(r);
        removeRook(r, last);
        c = last + 1;
    }

    for (int j = c; j < row.length; j++) {
        if (isValid(r, j)) {
            putRook(r, j);
            return solve(r + 1, 0);
        }
    }

    last = lastY(r - 1);
    removeRook(r - 1, last);
    return solve(r - 1, last + 1);
}

public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    board = new int[n][n];
    row = new int[n];
    col = new int[n];

    for (int i = 0; i < row.length; i++) {
        boolean finished; // not important
        putRook(0, i);
        finished = solve(1, 0);
        if (finished) System.out.println("============"); // ignore this too
    }
}
}

Stackoverflow points to the lines that contain recursive calls to solve() method.

Note: I know only C like syntax of java and basic data abstraction. I wrote this code with this level of my Java.

I want to solve this problem and N queens problem myself. Because there are so many solutions to these problems out there, both mathematically and algorithmically. And I am not interested in advanced Java data abstraction things right now.
I only want some advice about my code snippet above something like

Your backtracking algorithm is not efficient. (so straightfoward)
You need to use some Java data abstraction things to solve this problem efficiently.
You need to use another form of recursion like tail recursion (I heard about this too.)
....

eldar · Accepted Answer

The main issue why you're getting Stack Overflow error is the way your recursion is structured. The moment solve is invoked in the main method, it keeps recursing deeper and deeper; in fact, all of its invocations form a single several-thousand-calls-deep chain. For n=7, there are 3193 nested calls (I added a counter to check this). For n=8, it performs about 5k recursive calls before overflowing stack on my machine - I guess stack size is rather small by default.

Thus, to get this to work for higher values of n, you need to restructure your recursion in a way that doesn't perform all the recursive calls as a single chain. I could argue that your current solution isn't really backtracking because it never actually backtracks. Let me illustrate what backtracking means on a simpler problem. Let's say you want to print all binary strings of length n=3 ("000" through "111") programmatically, without relying on knowing the value of n. An implementation for this could be something like this:

def build_binary_string(current_prefix, chars_left):
  if chars_left == 0:
    print current_prefix
    return
  build_binary_string(current_prefix + 'a', chars_left - 1)
  build_binary_string(current_prefix + 'b', chars_left - 1)

build_binary_string("", 3)

The interesting thing (backtracking!) happens at the moment when build_binary_string is invoked with arguments ("00", 1):

build_binary_string("000", 0) is invoked, prints "000" and returns immediately
we are back into build_binary_string("00", 1) function call, right about to execute build_binary_string(current_prefix + 'b', chars_left - 1)
build_binary_string("001", 0) is invoked, prints "001" and returns immediately

That point when control flow returned from build_binary_string("000", 0) to build_binary_string("00", 1) and it chose to make another function call was backtracking. Note that the depth of recursion never exceeded 3.

How to avoid stackoverflow error for n = 8 in N Rooks problem

Answers (2)

Related Questions