How to solve Sudoku by returning and recursing?

Question

the reason why I create this new thread instead of just reading the answers to this specific question that was given earlier is because I feel that I just do not fully understand the whole idea behind it. It seems like I can't look back at the whole concept of reverse tracking. So I need to fully understand the rollback, and then solve the specific sudoku problem.

What I understand so far is that backtracking is a way to go back (for example) to a recursive thread if you find that decisions made before the current state led to a deadlock. So, you will return to something else and continue again.

So, in my Sudoku example, I select the first empty cell and try to fill in a natural number from {1 ... 9}, which does not contradict the well-known Sudoku rules. Now I do the same with the next empty cell until I reach the point where a valid number cannot be inserted without conflicts. In my understanding, this should be the point at which the rollback occurs. But how? If I use recursion to return to the last recorded cell, the algorithm will fill in the number again, continue and end the jam in an infinite loop.

So, I searched the Internet for tips and found that this is a pretty well documented and often solved problem. However, many solutions claim to use backtracking. I don’t see how and 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 do not know how to proceed. How to implement backtracking or am I already? This seems like a silly question, but I really don't see any more digressions in the 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; } 

Answer 1

I will just give an explanation of what the return trip means.

Recursion means calling a function from the same function. Now it happens that when a function encounters a call to itself ... imagine that a new page is opened, and control is transferred from the old page to this new page before the function starts, when the function encounters a call in this new page, another page opens nearby, and thus new pages appear next to the old page.

The only way to return is to use the return . When a function encounters this, the control jumps from the new page back to the old page on the same line from where it was called, and starts to do everything below that line. This is where the countdown begins. To avoid the problems associated with data submission when they are filled, you need to put a return statement after each function call.

For example, in code

 if(row > 8) return true; 

This is a basic case. When its value is true, the function starts the countdown, i.e. Management returns from the new page to the old page, but it returns to where it was called from. If, for example, is 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 } 

he will return to this line and begin to do whatever he needs. This statement is inside the for loop, and if i < 10 loop will run and it will try to set the values ​​again. This is not what you want, you want it to keep backing down until it exits the function, because sudoku is filling in correctly? To do this, you need to put the return after this call ie return true; I have not read your code, so there may be many errors.

Answer 2

The easiest way to get closer to the rollback is to use the stack. Make your sudoku board a class, including all the specific numbers and possible numbers. Whenever you get to the point where you need to select a number, you create a copy of your board. One copy has the number that you selected on this square marked unforgettable (you do not want to select it twice) and you put this copy on the stack. The second instance you select the number and perform as usual.

Whenever you come to a standstill, you throw away the board you are working on, take the top board from the stack, and continue with that board. This is part of the "backtracking": you will return to the previous state and try again in a different way. If you selected 1 earlier and this did not work, try again from the same position, but select 2 instead.

If sudoku is solvable, you will eventually come to the blackboard where you can fill in all the numbers. At this point, you can throw away any boards remaining on the stack, since you do not need them.

If you just want to create a solvable Sudokus, then you can cheat, see the answers to: How to create sudokus boards with unique solutions

Answer 3

The way I think about recursion and return is as follows:

The isSolvable () call should try to take Sudoku as the first parameter and solve it from a specific row and column (thereby assuming that all previous values ​​are defined and valid).

Developing a complete sudoku solution will 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 sketches an ineffective example of the code path around recursion. However, I hope that this shows the way to use recursion to explore all the possibilities (taking into account the board and state), while the possibility of returning in cases where this state does not support the solution.