Running out of heap when using recursive backtracking

Question

I am currently studying the beautiful topic of recursive backtracking. I've already tried classical examples like finding the shortest path out of a maze, or the n-queens problem. But the problem I'm working on right now really keeps me confused: Actually I thought it might be an easy exercise to solve a simple jigsaw-puzzle: I have a board with the size of n = a * b and exactly that much (n) pieces.
In the end I want to have all the pieces to be put on the board in a certain order where they obey certain restrictions (like matching their neighbours). Fairly easy, I thought and I came up with the following algorithm:

public board recursiveSolve(Board board, Piece[] pieces, int position){
// base case
if(position  == board.getLength())
    return board;
else{ 
    // For each possible piece
    for(int i = 0; i < pieces.length; i++){
        // if the piece is placeable at that position
        // place it and search on recursively
        if(board.isValid(piece[i], position)){
            board.putPiece(pieces[i], position);

            // THIS IS THE FISHY PART!!
            // Now I need to pass a set of pieces to the function recursively 
            // that does not contain the current one (pieces[i])
            // But I fear my (following) approach is too heap-intensive

            Piece[] subPieces = new Piece[pieces.length - 1];

            // fill subPieces with all elements from pieces except from the one 
            // at position i
            for (int j = 0; j < subPieces.length; j++) {
                 if(j >= i)
                     subPieces[j] = pieces[j+1];
                 else
                     subPieces[j] = pieces[j];

            }

            if(recursiveSolve(board, subPieces, position + 1) != null)
                 return board;
            else
                 board.removePiece(position);
        }
    }
    // If this is reached, none of the pieces have worked -> go back
    return null;

}

Well basically, this algorithm does what it should do - but unfortunately it only works for "small" board sizes (n < 100). Because if I have a board like 10 x 10 squares and 100 pieces, the function searches and searches and just doesn't come to an end until JVM crashes due to insufficient heap space. I even tried setting eclipse's memory size limit up to 1.2g which made the function work longer but still was not enough.

So my question is: Is it possible to optimize the algorithm above to make it work for board sizes n > 100? What am I doing wrong? Or am I taking the entirely wrong approach?

Thank your very much for you help in advance.

Besides the language, this should work for n > 100 with no problems.. I see some weird things on your code, like you building subpieces everytime, and removing things of the board manually, that should be accomplish automatic by the backtracking.. maybe there is your problem? — gbianchi, Oct 21 '11 at 15:36

score 1 · Answer 1 · edited May 23 '17 at 12:12

1

Functional languages will help here by employing tail recursion which would save heap. Unfortunately, it seems JVM don't support tail recursion (at least, for Java), see this SO question

You can try to emulate tail recursion by hand.

edited May 23 '17 at 12:12

Community

1
1

answered Oct 21 '11 at 15:35

Victor Sorokin

11,878
2
35
51

Since tail recursion can be translated to a simple loop, which has a polynomial runtime, I don't believe you can transform this exponential algorithm into tail recursion. – amit Oct 22 '11 at 00:52
@amit I thought OP's problem is memory consumption (heap exhaustion due stack filled with parameters of recursive calls), not running time. Tail recursion can decrease memory consumption. – Victor Sorokin Oct 22 '11 at 07:02
True,but this recutsion in my opinion cannot be transformef to tsil recursion. – amit Oct 22 '11 at 07:50

score 1 · Answer 2 · answered Oct 21 '11 at 15:40

Since the board has a method to tell you whether piece[i] is valid in a position, doesn't it make more sense to iterate over the positions and try every (remaining) piece in that location before moving on? It wouldn't be using recursion (which would solve your heap space issue), but if you're after a recursive solution specifically it's obviously not a fit.

In order to do this more effectively I would suggest placing the pieces in a List however and remove a piece as you place it. Something like this:

List<Piece> remainingPieces = new ArrayList<Piece>(Arrays.asList(pieces));
int numberOfPositions = // I assume you have some way of finding this.
for (int position = 0; position < numberOfPositions; position++) {
    Iterator<Piece> it = remainingPieces.iterator();
    while (it.hasNext()) {
        Piece temp = it.next();
        if (board.isValid(temp, position)) {
            board.putPiece(temp, position);
            it.remove();
            break;
        }
    }
}

Ah right. I've misunderstood the result of board.isValid(...) then. I'm a bit busy right now, but I'll try to see if I can rethink my answer later with this in mind. — Vala, Oct 22 '11 at 08:58

amit · Accepted Answer · 2011-10-22T00:54:49.213

It seems the main heap usage in your program is indeed where you suspect: when initializing the new array of size pieces.length -1.
Note that you can indeed save a lot of space here! since you actually use only the 'deepest' set.

If you still want to use an array, you might want to pass an extra parameter: start, and implement swap(arr,i,k) which swaps the i'th and k'th elements in arr, and in each step, instead of allocating a new array, swap(pieces,start,i), and pass to the new function start+1 in the recursive step. note that since you always swap the last element, the next steps do no care of the swaps, becasue they are after the start position of the array. So basically, because the algorithm never 'looks back', you don't have any problems swapping these elements around...

Should look something like that:

public board recursiveSolve(Board board, Piece[] pieces, int position,int start){
if(position  == board.getLength())
    return board;
else { 
    //starting from start instead from 0
    for(int i = start; i < pieces.length; i++){
        if(board.isValid(piece[i], position)){
            board.putPiece(pieces[i], position);
            swap(pieces,start,i); //the swap() method I mentioned above        
            //sending start+1:
            if(recursiveSolve(board, subPieces, position + 1,start+1) != null) 
                 return board;
            else
                 board.removePiece(position);
        }
    }
    return null;
}

You are probably aware that backtracking algorithms are time-consuming [exponential!], so even with space-optimized version, the algorithm might run for a very long time until an answer is found.

Running out of heap when using recursive backtracking

3 Answers3