How to solve Sudoku by backtracking and recursion?

Question

the reason why I am creating this new thread instead of just reading the answers to this particular question that have been given before is that I feel I just don't fully understand the whole idea behind it. I can't seem to get my head around the whole backtracking concept. So I need to fully understand backtracking and then solve the particular sudoku problem.

What I understand so far is that backtracking is a technique to go back, in (e.g.) a recursive flow if one discovers that decisions made prior to the current state led to a dead end. So you go back try something else and continue again.

So in my sudoku example I pick the first empty cell and try to fill in a natural number out of {1...9} that doesn't conflict with the well know sudoku rules. Now I do the same thing with the next empty cell until I get to the point where no valid number may be inserted without conflicts. As of my understanding this should be the point where backtracking comes into play. But how? If I use recursion to go back to the last written cell the algorithm will fill in the number again, continue and end up stuck in an endless loop.

So I searched the Internet for hints and found this to be a quite well documented and frequently solved problem. Yet many solutions claim to use backtracking I don't see how or where they do it even if I have the source code right in front of me.

Examples are: Sudoku solver in Java, using backtracking and recursion or http://www.heimetli.ch/ffh/simplifiedsudoku.html

Here is my (not working) source code:

private boolean isSolvable( Sudoku sudoku, int row, int col ){

    //if the method is called for a row > 8 the sudoku is solved
    if(row > 8)
        return true;

    //calculate the next cell, jump one row if at last column
    int[] nextCell = (col < 8) ? new int[]{row,col+1} : new int[]{row+1,0};

    //check if the current cell isWritable() that is if it is not a given cell by the puzzle
    //continue recursively with the next cell if not writable
    if(!sudoku.isWritable(row, col))
        isSolvable(sudoku, nextCell[0], nextCell[1]);
    else{
        //set the current cell to the lowest possible not conflicting number
        for(int i=1; i< 10; i++){
            if(!conflictAt(sudoku, row, col, i)){
                sudoku.setValue(row, col, i);

                //continue recursively with the next cell
                isSolvable(sudoku, nextCell[0], nextCell[1]);
            }
        }
    }

    return false;
}

Now I don't know how to continue. How to implement the backtracking or did I already? This seems like a stupid question but I really don't see more backtracking going on in source codes mentioned in the links above.

EDIT: Final (working) version:

private boolean isSolvable( Sudoku sudoku, int row, int col ){

    //if the method is called for a row > 8 the Sudoku is solved
    if(row > 8)
        return true;

    //if the cell is not writable, get the next writable cell recursively
    if(!sudoku.isWritable(row,col))
        return isSolvable(sudoku, (col<8) ? row : row + 1, (col<8) ? col + 1 : 0);

    //brute forcing for solution
    for(int i=1; i<=9; i++){
        if(!conflictAt(sudoku, row, col, i)){
            sudoku.setValue(row, col, i);
            if(isSolvable(sudoku, (col<8) ? row : row + 1, (col<8) ? col + 1 : 0)) return true; 
        }
    }
    sudoku.setValue(row, col, 0);
    return false;
}

Indiscrimination

Instead of guessing for a solution, you could solve it directly using various strategies: github.com/cyrixmorten/sudoku. This also leaves the option to swap out strategies if hitting a dead end (like backtracking). You can check out the unit tests in the project to see an example of adding a new strategy in order to enable solving a difficult sudoku. This implementation has the added benefit of being able to give the user a reasoning of how the solution was found, step by step. – Megillah

Hi, I'm aware of the fact that there are better and more efficient ways of solving this problem. I am a Java novice and computer science student (first semester) and therefore need to understand this exact implementation. – Indiscrimination

Alright, I see, then you might want to look at my project when you need to consider basic software architecture :) Seems like a good and fairly advanced assignment for first semester. – Megillah

I probably will, thanks. :) – Indiscrimination

Answer 1

I am just going to give an explanation of what backtracking means.

Recursion means to call the function from within that same function. Now what happens is that when the function encounters a call to itself.. imagine that a new page opens up and control is transferred from the old page onto this new page to the start of the function, when the function encounters the call again in this new page, another page opens up beside it and in this way new pages keep popping up beside the old page.

The only way to go back is using return statement. When the function encounters it the control goes from the new page back to the old page on the same line from where it was called and starts executing whatever is below that line. This is where backtracking starts. In order to avoid issues like feeding data again when its filled up you need to put a return statement after every call to the function.

For e.g in your code

if(row > 8)
        return true;

This is the base case. When its true, the function starts backtracking i.e control goes back from the new page to the old page BUT it goes back to from wherever it was called. If for e.g it was called from this statement.

 for(int i=1; i< 10; i++){
            if(!conflictAt(sudoku, row, col, i)){
                sudoku.setValue(row, col, i);

                //continue recursively with the next cell
                isSolvable(sudoku, nextCell[0], nextCell[1]);  <------ here
            }

it will go back to this line and start doing whatever it should. This statement is inside the for loop and if i < 10 the loop will run and it will try to set values again. That's not what you want, you want it to keep backtracking till it exits the function because sudoku is filled up right? In order to do that you need to put a return statement after this call i.e return true; I haven't read your code so there might be many more mistakes like that.

Metalwork

Great answer, thanks! I think I grasped the concept now so I went back to Eclipse and improved/changed my code. I inserted it in my original post. Could you take a look at it? Thanks in advance. – Indiscrimination

One mistake i see is the if part in for loop. your comment says "skip this iteration" but i don't see any continue keyword to skip it. Other than that does it throw any errors/exceptions? – Metalwork

I don't think a "continue" is needed here as there is an if/else statement in the for loop with the if clause being empty. So whenever the if part is executed nothing happens and the iteration continues. Actually no errors or exceptions are thrown. It just returns true with the Sudoku somewhat solved but some zeros in it. – Indiscrimination

Oh yeah, my bad. I forgot it was in an if else. So its working? – Metalwork

It didn't work correctly but now I got it. The updated initial post now contains my solution. Thanks again for the input your answer really helped a lot with general understanding. – Indiscrimination

Answer 2

The easiest way to approach backtracking is to use a stack. Make your Sudoku board a class, including all the definite numbers and the possible numbers. Whenever you get to a point where you need to pick a number you create a copy of your board. One copy has the number you picked in that square marked unpickable (you don't want to pick it twice) and that copy you put on the stack. The second copy you pick the number and proceed as usual.

Whenever you come to a dead end, you throw away the board you are working on, take the top board off the stack and carry on with that board. This is the "backtracking" part: you go back to a previous state and try again down a different path. If you picked 1 before and it didn't work, then you try again from the same position but pick 2 instead.

If the Sudoku is solvable then you will eventually come to a board where you can fill in all the numbers. At that point you can throw away any part-boards left on the stack since you don't need them.

If you are just looking to generate solvable Sudokus, then you can cheat, see the answers to: How to generate Sudoku boards with unique solutions

Bocanegra

This is a nice approach and it helped my understanding. Thanks for that! However I am somewhat limited how to design my "Sudoku-datastructure" as it was given in the exercise. And it has just two attributes: "values" and "writable" both of which are two dimensional arrays. While "values" holds the numbers in the cells "writable" holds a boolean value for every cell whether or not one is allowed to write in the cell. – Indiscrimination

Either write a single wrapper class to hold both your given data structures, or else run two parallel stacks, one to hold each data class, and pop/push one of each when accessing the stacks. – Bocanegra

Answer 3

The way that I would think of the recursion and backtracking is as follows:

Calling isSolvable() should attempt to take the Sudoku handed as the first parameter, and solve it from a specific row and column (thereby assuming all previous values are determined and valid).

Working out the full solution of a sudoku would then be something like the following code. If I understand rossum correctly, this somewhat outlines the same idea:

// you are handed a sudoku that needs solving
Sudoku sudoku; 
for (int row=0; row <= 9; row++) {
    for (int col=0; col <= 9; col++) {
        for (int value_candidate = 1; value_candidate <= 10; value_candidate++) {

            // or any other type of deep-copy 
            Sudoku sudokuCopy = sudoku.clone(); 
            sudokuCopy.setValue(row, col, value_candidate);

            if (isSolvable(sudokuCopy, row, col)) { // (recursion)

                // only if the value_candidate has proven to allow the                  
                // puzzle to be solved, 
                // we persist the value to the original board

                sudoku.setValue(row, col, value_candidate);

                // and stop attempting more value_candidates for the current row and col 
                // by breaking loose of this for-loop
                continue;
            } else { // (backtracking)

                // if the value_candidate turns out to bring no valid solution
                // move on to the next candidate while staying put at 
                // the current row and col 
            }
        }
    }
}  

This of course only sketch an inefficient example of an outline of the code around the recursion. I however hope this shows a way of using recursion to investigate all possibilities (given a board and a state), while enabling backtracking in cases where the given state does not hold a solution.

Megillah