Sudoku generator: Recursion not working

Question

What I'm trying to accomplish:

while(there are empty squares)
   get a random number of the remaining numbers
   if(the number hasn't been tried before)
      if(it fits)
        place it and remove from available
        next square
   if(all numbers have been tried)
       forget it
       move back a square and try a different number

This loop stops at availableNumbers = 64, and sometimes 37, and sometimes 81 etc. What stops it from going all the way? Why does it sometimes get stuck and sometimes backtrack?

while(availableNumbers.size()>0){
            rand = rn.nextInt(availableNumbers.size());
            number = availableNumbers.get(rand);
            if(number != triedNumbers[y][x][number-1]){    // If the number hasn't been tried in this square
                if(!checkConflict(number)){
                    squares[y][x].setText(""+number);
                    availableNumbers.remove(new Integer(number));
                    addedNumbers[y][x] = number;
                    triedNumbers[y][x][number-1] = number;
                    moveAhead();
                }
            }
            if(Arrays.equals(triedNumbers[y][x],refArray)){    // If all numbers have been tried in that square
                emptySquare();    // Forget all numbers tried in current square
                moveBack();
            }
}

emptySquare, moveBack, moveAhead and checkConflicts all work like they're supposed to (according to my tests). Here's a gist with them: https://gist.github.com/WQvist/ac4296fb3a86fdc3d713

EDIT: I finally solved it. Thanks for all the help. See my answer.

Answer 1

Solved it!

while(currentSquare<81){
            rand = rn.nextInt(availableNumbers.size());
            number = availableNumbers.get(rand);
            if(square[currentSquare].contains(number)){
                square[currentSquare].remove(new Integer(number));
                if(!checkConflict(number)){
                    squares[y][x].setText(""+number);
                    addedNumbers[y][x] = number;
                    availableNumbers.remove(rand);
                    moveAhead();
                    currentSquare++;
                }
            }
            if(currentSquare < 81){
                while(square[currentSquare].isEmpty()){
                    square[currentSquare].addAll(refList);
                    addedNumbers[y][x] = 0;
                    availableNumbers.addAll(refList);
                    moveBack();
                    if(currentSquare>=1){
                        currentSquare--;
                    }
                }
            }
        }

Answer 2

Your psudeocode is incorrect. It should be:

while(there are empty squares)
   get a random number of the remaining numbers
   if(the number hasn't been tried before)
      if(it fits)
        place it and remove from available
        next square
   while(all numbers have been tried)
       forget it
       move back a square
   try a different number

You sometimes have to go back more than one square to get to a square where you haven't tried all the numbers.