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?

Answer 1

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

Answer 2

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