title: Running out of heap when using recursive backtracking
body: <p>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.<br>
  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: </p>
  
  <pre><code>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 &lt; 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 &lt; subPieces.length; j++) {
                   if(j &gt;= 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 -&gt; go back
      return null;
  
  }
  </code></pre>
  
  <p>Well basically, this algorithm does what it should do - but unfortunately it only works for "small" board sizes (n &lt; 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.</p>
  
  <p>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?</p>
  
  <p>Thank your very much for you help in advance.</p>