My loop never ends

Question

i have a problem with my program, it should solve the sudoku and print when its done, but the problem is, the program looks like it never ends, after printing the solved sudoku it gets errors.

here is the loop which is the program is making: It also doesn't print field when it should, if i remove the System.out.print(f+"\n"); at start it prints nothing just errors. Code:

        public class Sudoku {


  public static void main(String[] args) throws SolvedException {
    Field field = new Field();
    field.fromFile("test1.txt");
    SudokuSolver solver = new SudokuSolver();

    solve(field, 0, 0, solver);

    System.out.println(field);

  }




public static void solve(Field f, int i, int j, SudokuSolver solver) {

    System.out.print(f+"\n");

    if ( j >= Field.SIZE) {

        //we are done (return true now!)
        solver.done=true;
        return;

    } 

    if (f.isEmpty(i, j)) {

        for (int val = 1; val <=9; val++) {

            if (f.tryValue(val, i, j)){

                if (j>=Field.SIZE-1){

                    solve (f, i+1, 0, solver);

                    if ( solver.done ) {

                        // This halts the loop here:
                        return;
                    }

                    f.clear(i, j);

                } else {

                    solve(f,i,j+1, solver);

                    if ( solver.done ) {

                        // This halts the loop here:
                        return;
                    }

                    f.clear(i, j);

                }

            }
        }

    } else if (j>=Field.SIZE-1) {

        solve(f,i+1,0, solver);

    } else {

        solve(f,i,j+1, solver);

    }
}
}

SudokuSolver

public class SudokuSolver{

    /* Set true when the solve is done */
    public boolean done;

}

errors:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 9
    at Field.isEmpty(Field.java:101)
    at Sudoku.solve(Sudoku.java:30)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:67)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:67)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:67)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:38)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:71)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.solve(Sudoku.java:50)
    at Sudoku.main(Sudoku.java:9)

Any ideas how could i stop the loop and print the right field? System.out.println(field) instead of this one in solve method?

Given `throws SolvedException` it's presumably supposed to `throw new SolvedException();` in the `// we are done` part. It's worth noting that it's a [bad idea to use exceptions to control the flow](http://softwareengineering.stackexchange.com/a/189225/254270) like that. Another note is the large amount of non-tail recursion could result in random stack overflow exceptions too. — Luke Briggs, Jan 07 '17 at 00:21
In short, recursion is where a function calls itself. Each time that happens, you get another 'stack frame' - basically all the local variables in use by the function are stored. If a function calls itself lots of times, the stack grows too big and 'overflows'. Tail recursion is an optimization where essentially the stack frame can get 'reused' because a compiler noticed the locals aren't in use anymore, allowing for infinite recursion to happen. See also [this answer](http://stackoverflow.com/a/33930/2873896) for a more in depth comparison. — Luke Briggs, Jan 07 '17 at 00:29
@Mercy do not remove the question body saying "please delete this question" after a good answer is posted and your problem is solved. If you edit in such way it will confuse other people. — taskinoor, Jan 07 '17 at 03:47
@Mercy then you shouldn't have posted the question in the first place. Please first get familiar with how this site works. — taskinoor, Jan 07 '17 at 04:14
I don't understand what you problem here is. taskinoor told you that you aren't allowed to remove important parts of your question and you keep doing that. I've flagged this question for a moderator to lock this question and prevent further manipulation from your side. — Tom, Jan 07 '17 at 16:48
**Moderator note**: Do not vandalise your post. If someone else were to copy this work to claim as their own, then that's *their problem*, not yours. — Martijn Pieters, Jan 07 '17 at 17:21

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

Recursion that never terminates

(In this case, it does terminate when it errors).

This part of your code needs to actually do something to indicate that it's done:

if ( j >= Field.SIZE) {

    //we are done

}

Otherwise that loop simply continues going, unaware that it should've stopped (shortened):

for (int val = 1; val <=9; val++) {

     ...
     
     solve (f, i+1, 0); // Maybe this call is 'done', but this loop will keep going

     ...
}

So, based on throws SolvedException your code should throw an exception there:

if ( j >= Field.SIZE) {

    //we are done
    throw new SolvedException();
    
}

But this is a Bad Idea. Exceptions are not for controlling code flow - they are for completely unexpected situations.

Signalling that it's done

Instead, we need to have some way of knowing when the code has reached that 'done' condition. In classic recursion, this is performed by returning something. As we want to know only if it's done or not, a bool handles that fine:

// Type changed to bool, removed throws:

public static bool solve(Field f, int i, int j) {

    System.out.print(f+"\n");

    if ( j >= Field.SIZE) {

        //we are done (return true now!)
        return true;

    } 

    if (f.isEmpty(i, j)) {
        
        for (int val = 1; val <=9; val++) {
            
            if (f.tryValue(val, i, j)){

                if (j>=Field.SIZE-1){
                    
                    if( solve (f, i+1, 0) ){
                        // This halts the loop here:
                        return true;
                    }

                    f.clear(i, j);
                    
                } else {
                    
                    if( solve(f,i,j+1) ){
                        // This halts the loop here:
                        return true;
                    }

                    f.clear(i, j);

                }

            }
        }
        
    } else if (j>=Field.SIZE-1) {
        
        // (Side note: This one is tail recursion)
        return solve(f,i+1,0);
        
    }
    
    // (Side note: This one is tail recursion)
    return solve(f,i,j+1);

}

In the callee, you also have this:

try {
  solve(field, 0, 0);
} 
catch (SolvedException e) { }

Which you would also swap out for:

if( solve(field, 0, 0) ){

    // It was solved!
    
}

Returning void instead

You mentioned that you'd still like to return void. Ok, so, we'll need to track that 'done' state somewhere else - e.g. inside some object which we'll call SudokuSolver:

public class SudokuSolver{
    
    /* Set true when the solve is done */
    public bool done;
    
}

Using that makes the code look more like this instead:

// Type changed to void, added our solver arg:

public static void solve(Field f, int i, int j, SudokuSolver solver) {
    
    System.out.print(f+"\n");

    if ( j >= Field.SIZE) {

        //we are done (return true now!)
        solver.done=true;
        return;
        
    } 
    
    if (f.isEmpty(i, j)) {
        
        for (int val = 1; val <=9; val++) {
            
            if (f.tryValue(val, i, j)){

                if (j>=Field.SIZE-1){
                    
                    solve (f, i+1, 0, solver);
                    
                    if ( solver.done ) {
                        
                        // This halts the loop here:
                        return;
                    }

                    f.clear(i, j);
                    
                } else {
                    
                    solve(f,i,j+1, solver);
                    
                    if ( solver.done ) {
                        
                        // This halts the loop here:
                        return;
                    }

                    f.clear(i, j);

                }

            }
        }
        
    } else if (j>=Field.SIZE-1) {
        
        solve(f,i+1,0, solver);
        
    } else {
        
        solve(f,i,j+1, solver);
        
    }
    
}

With the call site now looking like this:

SudokuSolver solver=new SudokuSolver();

solve(field, 0, 0, solver);

if ( solver.done ) {
    // It was solved!
}

@Mercy That's more likely because the actual algorithm doesn't do what you want it to - this answer just focuses on stopping the loop :) — Luke Briggs, Jan 07 '17 at 01:04
@Mercy I've made a few more edits - see the part at the bottom (also `throws new ..` should've been `throw new`, but *please avoid using that* as mentioned in the answer). — Luke Briggs, Jan 07 '17 at 01:09
@Mercy are you using it to learn Java? In which case, all the more reason to avoid bad techniques :) — Luke Briggs, Jan 07 '17 at 01:21
@Mercy I've added a technique where it still returns void - as it's for school, don't use an exception :) — Luke Briggs, Jan 07 '17 at 01:32
@Mercy Java classes must always go in their own file, so it's probably that - I haven't tested it though (I don't have your `Field` class, so I can't); it's more just a demonstration of the common techniques :) — Luke Briggs, Jan 07 '17 at 01:50
@Mercy I still see your original error, in which case it could be that `i` goes out of range too (so maybe it should be `if ( j >= Field.SIZE || i>= Field.SIZE ) {` but I don't know what your algorithm is supposed to be solving). — Luke Briggs, Jan 07 '17 at 02:08
@Mercy Great no problem :) "Unreachable catch block" - because nothing is being thrown (which is what you want). Check `solver.done` to see if it solved or not (see the very end of this answer). Answers/ questions shouldn't be deleted because they're useful to other people :) — Luke Briggs, Jan 07 '17 at 02:55
@Mercy A question can't be deleted on those grounds unfortunately - that's not how StackOverflow works. There's a [whole bunch](https://encrypted.google.com/search?hl=en&q=%22throws%20SolvedException%22) of [other variants](http://pastebin.com/0tcRjMx7) of it on the web already :) — Luke Briggs, Jan 07 '17 at 03:10
@Mercy It doesn't actually allow me to - there has to be a very good reason (e.g. the question is poor quality, but this one was fine). — Luke Briggs, Jan 07 '17 at 03:21

score 0 · Answer 2 · answered Jan 07 '17 at 00:25

0

somewhere trying to access the arrays upper element which does not exists. try to debug and find.

probably val is the key to look for.

I assume for (int val = 1; val <=9; val++) should be for (int val = 1; val <9; val++)

answered Jan 07 '17 at 00:25

zsair

31
2

seems you also using stackoverflow first time :). I would be happy if you selected my answer as solving one. So, I will collect my points ;) – zsair Jan 07 '17 at 00:51
I have no time to help you with your whole task but I solved your error. – zsair Jan 07 '17 at 01:20

My loop never ends

2 Answers2

Recursion that never terminates

Signalling that it's done

Returning void instead