Sudoku Backtracking Algorithm

Sudoku Backtracking with Solution Counter

Thanks to this answer by Aziz Sonawalla, I think I figured it out.

The following implementation was able to solve the uniquely solveable sudoku given here. Also the algorithm is now able to solve sudokus with more than one solution (example) and recognize that there is more than one solution. If this is the case, the program will give only one of the possible solutions.

The code looks like this:

// Backtracking-Algorithm
public int[][] board2 = new int[GRID_SIZE][GRID_SIZE];

public int solver(int[][] board, int count) { // Starts with count = 0

    for (int i = 0; i < GRID_SIZE; i++) { //GRID_SIZE = 9

      for (int j = 0; j < GRID_SIZE; j++) {

        /*
         * Only empty fields will be changed
         */

        if (board[i][j] == EMPTY) { //EMPTY = 0

          /*
           * Try all numbers between 1 and 9
           */

          for (int n = 1; n <= GRID_SIZE && count < 2; n++) {

            /*
             * Is number n safe?
             */
            if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {

              board[i][j] = n;
              int cache = solver(board, count);
              if (cache > count) {
                count = cache;
                for (int k = 0; k < board.length; k++) {
                  for (int l = 0; l < board.length; l++) {
                    if (board[k][l] != EMPTY) {
                      board2[k][l] = board[k][l];
                    }

                  }
                }

                board[i][j] = EMPTY;

              } else {
                board[i][j] = EMPTY;
              }

            }
          }
          return count;
        }
      }
    }
    return count + 1;
}

The solution is saved in the array board2 now.

This implementation is working as intended (as far as I know). If you find any mistakes, please leave a comment.

Sudoku Backtracking Algorithm Solver raising a RecursionError

The issue with your code is that every time a change is made to the board in self.solve(), a new call to self.solve() is issued. self.solve() never returns a value to the parent self.solve() call, so none of the functions calls ever exit until the very end of the code.

I believe what you intended to do is make it so that each time a value is added, a new call to self.solve() is made. And each time a value is discovered to be invalid, some indicator (i.e. False) is returned to the previous call of self.solve(). In this implementation, there would be at most 81 recursive calls to self.solve(). In your current architecture, there could be as many as 9^81 recursive calls, hence the RecursionError as you quickly use up available space in the stack with each successive call.

To fix, I suggest modifying your code so that self.solve() returns True if there is a valid board combination and False otherwise, and make a recursive call to self.solve() every time a value is added. Based on this approach I think you need only one function (solve) and don't need a backtrack function.

Pseudocode:

def self.solve():
    # find the next unassigned square
    # for each value in range (1,9) assign that value to square and make recursive call to solve()
    # if all recursive calls return False, return False
    # if any call to solve() ever returns True, a valid solution to the board has been found

Backtracking algorithm for solving Sudoku

Just some side note, pure back-tracking for a sudoku problem will lead to an enormous time of execution in general.

Your problem is that you never reset a when finding a good solution. A solution might be to add a=1 at the end of the else of the while loop. Additionally, you use history.remove(history[n]) which delete the first item of history that is equal to history[n], leading to some error. You should replace it by del. Here is the corrected loop :

   while True:
        ## This line is to debug

        # p has value of True or False, and q has value of the correct integer if True, 0 if False
        [p, q] = conditions(a, empty_list[n][0], empty_list[n][1])

        if not p:
            # Removing the old 'correct' answer from the history list.
            del(history[n])
            # If p is false, we backtrack by shifting to the last empty box.
            n -= 1

            # a is the 'lower' input for conditions() function.
            a = history[n] + 1
            history[n]+=1

            board[y][x] = 0
            [x, y] = empty_list[n]

            # Since the 'correct' answer of previous box is not correct anymore, we are replacing it back with 0 (erasing it).

            ## This line is to debug.

        else:
            # If p is True, the 'correct' integer gets appended to the list.
            history[n]=q
            history.append(0)
            [x, y] = empty_list[n]

            # The correct answer is replacing the 0 (writing it on the empty box).
            board[y][x] = q
            n += 1

            # n increments by 1 to proceed to the next empty box.
            a=1 
        # When we run through the entire list of empty boxes, we break this loop.
        if n == len(empty_list):
            print("Done!")
            break

This lead to the output :

0 0 6 | 8 4 0 | 0 0 0 | 
2 0 1 | 0 6 0 | 0 0 7 | 
0 3 9 | 0 0 0 | 0 1 0 | 
-----------------------
0 0 0 | 0 9 8 | 3 0 0 | 
0 6 0 | 0 0 0 | 0 9 0 | 
0 0 7 | 3 2 0 | 0 0 0 | 
-----------------------
0 4 0 | 0 0 0 | 1 3 0 | 
7 0 0 | 0 1 0 | 8 0 4 | 
0 0 0 | 0 3 5 | 7 0 0 | 
-----------------------
Done!
5 7 6 | 8 4 1 | 9 2 3 | 
2 8 1 | 9 6 3 | 5 4 7 | 
4 3 9 | 2 5 7 | 6 1 8 | 
-----------------------
1 2 4 | 5 9 8 | 3 7 6 | 
3 6 8 | 1 7 4 | 2 9 5 | 
9 5 7 | 3 2 6 | 4 8 1 | 
-----------------------
6 4 5 | 7 8 9 | 1 3 2 | 
7 9 3 | 6 1 2 | 8 5 4 | 
8 1 2 | 4 3 5 | 7 6 9 | 
-----------------------

Which is the correct answer.

How does this Sudoku backtracking recursive algorithm trigger backtracking?

The backtracking happens when findEmtpy returns false. But as your code is not optimal, still many other options are tried while backtracking: none of the for loops that are pending in the recursion tree are interrupted, yet it is wasted effort to have them continue and calling checkValue as each of those calls will now return false. So, eventually all those for loops will end, and the recursion will backtrack, only to finish yet another loop and backtrack again, ...etc.

Here is an update of your main function to avoid some of that overhead that leads to no gain:

solve(puzzleString) {
    // Only call findEmpty once!
    let emptyCell = this.findEmpty(puzzleString);
    if (!emptyCell) return { solution: puzzleString.join('') }; // return the success object
    let [row, col, i] = emptyCell; // use destructuring assignment
    for (let num = 1; num < 10; num++) {
        if (this.checkValue(puzzleString, row, col, num)) {
            puzzleString[i] = num;
            let result = this.solve(puzzleString); // capture the return value
            if (result.solution) return result; // success: fast backtracking!
        }
    }
    puzzleString[i] = "."; // could not solve this spot
    // backtrack to possibly take a different route in previous decisions
    return { error: 'Puzzle cannot be solved' };
}

---

Related Topics