How do I fix this stack overflow error?

Question

So I have what I think is pretty good code for a sudoku solver in java but I need some help with this method. It gives me a stack overflow when I embed it in a main method. The problem is that my method doesn't know how to turn around and fix its mistakes. I need a boolean flag (one that, unlike the one used in the code below, actually works preferably) or something to let it know when it should turn back and when it can again go forwards and continue solving the game. Thanks for any help you can give

public void play(int r, int c){//this method throws the StackOverflowError
    if(needAtLoc(r,c).size()==9){
        int num=1+generator.nextInt(9);
        setCell(r,c,num,this);

    if(c<8){
 System.out.println(this);///////////////
 play(r, c+1);
    }
    else{
 play(r+1, 0);
    }
}
else{
    if(needAtLoc(r,c).size()==0){//no possible moves THIS IS THE PROBLEM LINE!!!
 if(c>0){
     play(r, c-1);//play last cell, in column to left
 }
 else{
     if(r==0){
  play(r,c);//first square, so must play again (can't go back)
     }
     else{
  play(r-1, 8);/*first cell of row so must go to previous row and 
          the end column*/
     }
 }
    }

    else{//if there are possible moves
 int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size()));
 setCell(r,c,num,this);//set the value of the cell
 System.out.println(this);//////////////
 if(r==8 && c==8){//the end of the cell has been reached so must end recursive call
  return;
 }
 else{
     if(c<8){
  play(r, c+1);//normal, next cell
     }
     else{
  play(r+1, 0);/*last cell in row so we go to next one 
          in the first column ("return" button)*/
     }  
 }
    }
}
}

Answer 1

Rather than solve this for you I would make a few suggestions in how to tackle this. 9 hours is ample.

1) Your code is hard to read. Try to space it out a bit. Give your variables meaningful names that are clear (this helps you and other people read your code). You may have made a simple mistake and clean code will make these easier to spot. Try to break it into smaller methods since this will make it more readable and more maintainable.

2) Stack overflows are caused (generally I believe) when you make too many nested method calls and are typical in recursive code. Therefore make your recursion clear. Make sure you have a base case that will terminate.

Sorry to not give you "the answer" but since this sounds like homework I think there's more value in learning how to solve this yourself. Hope that seems fair.

Answer 2

I think u are calling play() recursively .Try to check if there is a stopping condition to ur recursive call.

Answer 3

Your code is throwing stack over flow exception because you never reach a terminating condition that ends your recursion, or at least it is not obvious you to see you have a recursion terminating condition by reading your code.

Your code is not well structure, hence you will have a hard time debugging it. Try to restructure your code, it will help you rethink the problem. Also, please comment your code :)

Answer 4

I agree with Tom, but here is a hint.

There is no condition and return statement to end the recursive calls.

Answer 5

You are recursively calling play without ever returning and it looks as if you are initialising a new set of variables each time at the top of the function.

Try splitting out the initialisation from the recursive part. You also need a clear end condition to end the recursion e.g. (if(isBoardFilled()==true)) return.

Also structure it so that you add a number to the board, test it against the contraints and if it passes add another number (recurse) or backtrack by removing the last number and try again.

Answer 6

I've managed to be more concise and more clear but it still won't run... I just need a push over the edge and I'm home free. I've dumped so many wasted hours into this project:

public ArrayList needAtLoc(int r, int c){ int bc=c/3;//the column within the SudokuBoard int blc; /The two posibilities for the column within each SudokuBlock:/ if(c>=0 && c<3) {blc=c;} else {blc=c%3;} int br=r/3;//the row within the SudokuBoard int blr; /The two possiblities for the row within each SudokuBlock:/ if(r>=0 && r<3) {blr=r;} else {blr=r%3;} ArrayList needR=new ArrayList(); needR=checkR(r);// needR.trimToSize(); System.out.println(needR);////////////// ArrayList needC=new ArrayList(); needC=checkC(c); needC.trimToSize(); System.out.println(needC);///////////// ArrayList needBl=new ArrayList(); needBl=this.board[br][bc].updateMissing();//that method updates and returns an ArrayList needBl.trimToSize(); ArrayList poss=new ArrayList(); poss.clear(); for(Integer e: needBl){ if(needC.contains(e) && needR.contains(e)){ poss.add(e); } } return poss; }

public void play(int r, int c){//this method throws the StackOverflowError
int bc=c/3;//the column within the SudokuBoard
int blc;
/*The two posibilities for the column within each SudokuBlock:*/
if(c>=0 && c<3) {blc=c;}
else {blc=c%3;}
int br=r/3;//the row within the SudokuBoard
int blr;
/*The two possiblities for the row within each SudokuBlock:*/
if(r>=0 && r<3) {blr=r;}
else {blr=r%3;}
if(needAtLoc(r,c).size()==9){
    int num=1+generator.nextInt(9);
    this.board[br][bc].setValue(blr, blc, num);
    if(c<8){
 System.out.println(this);///////////////
 play(r, c+1);
    }
    else{
 play(r+1, 0);
    }
}
else{
    if(needAtLoc(r,c).size()==0){//no possible moves
 if(c>0){
     bc=(c-1)/3;
     if(c>0 && c<4) {blc=c-1;}
     else {blc=(c-1)%3;}
     this.board[br][bc].setValue(blr, blc, 0);
     play(r, c-1);
 }
 else{
     blc=0;
     bc=0;
     if(r==0){
  blr=0;
  br=0;
  this.board[br][bc].setValue(blr, blc, 0);
  play(r,c);
     }
     else{
  br=(r-1)/3;
  if(r>0 && r<4) {blr=r-1;}
  else {blr=(r-1)%3;}
  this.board[br][bc].setValue(blr, blc, 0);
  play(r-1, 8);
     }
 }
    }

 else{//if there are possible moves
     int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size()));
     this.board[br][bc].setValue(blr, blc, num);
     System.out.println(this);//////////////
     if(r==8 && c==8){
  return;
     }
     else{
  if(c<8){
      play(r, c+1);
  }
  else{
      play(r+1, 0);
  }  
     }
 }
    }
}

Answer 7

I think your problem is where you have:

if(r==0)
{
    play(r,c);//first square, so must play again (can't go back)
}

That's because you don't seem to modify any state here and you pass the same values in that made you come to this step in the first place. Seems like infinite recursion for me.

Also please align your code correctly as it is too hard to read when it is misaligned and maybe provide some clues what the other methods do. Good luck!