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.

I don't know if it's the problem, but why do you wrap `number` in a new `Integer`? — Evan Knowles, Jan 14 '16 at 07:22
Because I want to remove that specific number, not the index. availableNumbers is a list of all numbers that will go onto the board. — Sinatra, Jan 14 '16 at 07:24
@guy That is incorrect. Since collections work on a 0-based index, the range is actually 0 to `availableNumbers.size()-1`. — Calvin P., Jan 14 '16 at 07:39
I don't know if this is the problem but `random.nextInt` is [exclusive](http://stackoverflow.com/a/363692/5168011) the top value, i.e. if `availableNumbers.size()` is 9 `number` will be in range 0 - 8. In `triedNumbers` you use `[number-1]` so you are missing a column. — Guy, Jan 14 '16 at 07:42
@Sinatra From what I can see, the number should be removed properly. However you could try removing the element at index `rand` in `availableNumbers` instead, since that is how you grabbed the number to begin with. — Calvin P., Jan 14 '16 at 07:45
@guy I think I understand what you mean, but my triedNumbers is a very ugly way of keeping track of which numbers I've tried in that square. if triedNumbers[y][x][0] = 1, it means I've tried putting a 1 there. Therefore, it needs to be number-1, since it starts at 0. — Sinatra, Jan 14 '16 at 08:00
@CalvinP. That seems a lot more reasonable. Although it didn't make a difference. — Sinatra, Jan 14 '16 at 08:00
@Sinatra I thought as much. Was worth a shot tho. As for keeping track of tried numbers, couldn't you just have an arraylist that is redefined each time you move to a new square? I don't particularly see a need to pass the grid coordinates along with it each time. — Calvin P., Jan 14 '16 at 08:15
@CalvinP. I tried it along with a simple currentSquare counter, and I think it made it a bit easier. It still doesn't work though. I still get stuck on 60-something and 30-something. I'm starting to think there's something else going on. — Sinatra, Jan 14 '16 at 08:49
Don't mark your question with `[SOLVED]`: add your solution as an answer, and accept it. — Sébastien Le Callonnec, Jan 14 '16 at 10:51

score 1 · Answer 1 · answered Jan 14 '16 at 08:11

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.

I see what you mean, and I implemented it. Still doesn't work. Thank you. — Sinatra, Jan 14 '16 at 08:50

score 0 · Accepted Answer · answered Jan 14 '16 at 10:59

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--;
                    }
                }
            }
        }

Sudoku generator: Recursion not working

2 Answers2