Problem with recursive backtracking - Sudoku Solving Example

Question

recently I've been trying to teach myself a bit of recursion to understand the process better. While I understand basic recursion techniques, I still struggle quite a bit with the idea of recursive backtracking. In order to help this, I've attempted to program a method that solves a sudoku solver when given a 2D array and and two ints, r and c, which are meant to represent the current column and row.

I have everything set up properly I believe, yet I can't quite figure out how to handle the "unraveling", or what happens after my initial method calls reach the eventual base case.

As of right now, when I run this method, it just returns a board that's empty, (unless there was previously a value there before, in which case it remains unchanged). I feel like the "board[r][c] = 0" that I have at the end of the method might have something to do with that.

The method "digitsValid" corresponds to a method that checks to make sure the current location on the board is a valid move within the row, column, and 3x3 subgrid.

Any help would be much appreciated.

private boolean sudokuSolver(int[][] board, int r, int c) {

    if(c > 8) {
        c = 0;
        r = r + 1;
    }

    if(r > 8) {
        return true;
    }

    if(board[r][c] != 0) {
        sudokuSolver(board, r, c + 1);
    } else {
        for(int i = 1; i <= 9; i++) {
            if(digitsValid(board, r, c)) {
                board[r][c] = i;    
                if(sudokuSolver(board, r, c + 1)) {
                    return true;
                }
            }
        }
    }

    board[r][c] = 0;
    return false;
}

Answer 1

I think your original assessment is correct. Recursive methods sound confusing but think of them like this:

public class RecursiveTest{

public static void main(String[] args){
    int x = 5;
    recursiveMethod(x);
}


public static void recursiveMethod(int i){
    System.out.println("Method just started for i = " + i);
    if(i > 0)
        recursiveMethod(i - 1);
    System.out.println("Method just ended for i = " + i);
}
}

Yields the following output:

Method just started for i = 5
Method just started for i = 4
Method just started for i = 3
Method just started for i = 2
Method just started for i = 1
Method just started for i = 0
Method just ended for i = 0
Method just ended for i = 1
Method just ended for i = 2
Method just ended for i = 3
Method just ended for i = 4
Method just ended for i = 5

Explanation

A recursive method is not all that different from any other method. It executes some code, at some point calls a method, runs that method and then continues running the rest of the code and finishes where any other method would finish.

The only difference is that method call is a call to itself. This would work the same as if you had copy-pasted that same method 5 times and named it all something different and then "daisy chained" them together.

In the example above, the original value is 5, it prints out that it started the for i=5, then ran the same method with the value of 4. Printed that, then ran 3 etc. Once it reached the final value where i = 0 the if statement failed and therefore it stopped the recursive calls. The method we are currently in (i = 0) finishes by writing Method just ended for i = 0 then it returns to the calling method when i = 1 and back tracks the same way it went in.

Your Code

I'm not quite sure what you have going on here. Does your example work? I'd like to see the isValid() method, but the following code you have:

for(int i = 1; i <= 9; i++) {   // Runs the following code 9 times.
    if(digitsValid(board, r, c)) {   // if true once, true every time
        board[r][c] = i;    
        if(sudokuSolver(board, r, c + 1)) {  // this is a totally separate method
            return true;
        }
    }
}

Your loop runs 9 times. The if statement following it never changes. The values within are not edited within the loop, so if it evaluates to true when i = 1 then it's going to evaluate to true on all 9 iterations of the for loop. This means the value at board[r][c] is going to end on 9.

From the looks of it, the only way this will ever return false, is if there is an invalid digit already stored in the array at the time of calling the method.