3

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)*/
        }       
    }
    }
}
}
6
  • 1
    you should tell people it's Java. That's a lot of code, by the way, think about breaking it down to functions. Are you sure solving a sudoku fits on the stack?
    – Kobi
    Dec 17, 2009 at 6:14
  • Sudoku code with a deadline. Homework? Dec 17, 2009 at 6:15
  • 1
    Unless T-9hrs is the name of a Terminator model ;)
    – user14554
    Dec 17, 2009 at 6:19
  • @Kobi - I'm quite sure it will fit on the stack. I've done this kind of excercise a few times before. Dec 17, 2009 at 6:23
  • 1
    Have you tried correcting the indentation before trying to spot errors? Dec 17, 2009 at 6:38

7 Answers 7

26

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.

2
  • 7
    +1 for not being an enabler and doing someone's work for them :) Dec 17, 2009 at 6:25
  • 1
    its less home work and more of a project. and yes I will comment I just tend to let that slide when I'm thrown by a problem. I've been at this class for the past 14+ hours and I couldn't be more frustrated. I'm just at a brick wall. I know where the program is screwing up. It fails to go back and fix bad number choices. It will get stuck in one cell and keep cycling and thats why the memory gets filled. I just need a way or at least a nudge in the right direction to make this freaking end. I really am a good student its just that my prof never taught us about recursion but expects us to use it
    – user233542
    Dec 17, 2009 at 8:56
3

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!

1
  • I tried to take that out, and it didn't help, but thanks. In terms of the helper methods, setCell assigns the "num" variable to the sudoku cell in question. needAtLoc returns and array list of the possible legal moves at that specified location
    – user233542
    Dec 17, 2009 at 12:09
1

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 :)

1

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.

0

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

0

I agree with Tom, but here is a hint.

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

0

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<Integer> 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<Integer> needR = new ArrayList<Integer>();
    needR=checkR(r);//
    needR.trimToSize();
    System.out.println(needR);//////////////
    ArrayList<Integer> needC=new ArrayList<Integer>();
    needC=checkC(c);
    needC.trimToSize();
    System.out.println(needC);/////////////
    ArrayList<Integer> needBl=new ArrayList<Integer>();
    needBl=this.board[br][bc].updateMissing(); //that method updates and returns an ArrayList
    needBl.trimToSize();
    ArrayList<Integer> poss=new ArrayList<Integer>();
    poss.clear();
    for(Integer e: needBl){
        if(needC.contains(e) && needR.contains(e)){
            poss.add(e);
        }
    }

    return poss;
}

//this method throws the StackOverflowError
public void play(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;
    }
    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);
        }       
        }
    }
    }
}
2
  • I find that sometimes you can gain alot by starting again (up to you though) I think your recursion call should only need occur once and that it would be simpler if you use a single index variable rather than two (r and c). Use one and work out the r and c from it. Recursive methods usually take the form: am I done yet? if yes then return. if not do something, recurse, possibly do something else and return. Try to make it this simple - otherwise you'll continue to get bitten. Dec 17, 2009 at 10:15
  • thanks, you guys are really helpful, I wish I wasn't in such a stressful mood because then this would be an enjoyable enlightening experience. Maybe i'll come back when I start modeling with FORTRAN
    – user233542
    Dec 17, 2009 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.