Sudoku Backtracking with Solution Counter

Tags: , ,



Background

I’ve implemented a sudoku-solver algorithm (backtracking) that looks like this:

//Backtracking-Algorithm
public static boolean solver(int[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) {
                for (int n = 1; n < 10; n++) {
                    if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
                        board[i][j] = n;
                        if (!solver(board)) {
                            board[i][j] = 0;
                        } else {
                            return true;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

This solution is working fine (it can solve sudokus).

What I try to achieve

I now want to achieve that the algorithm tells me, whether there is only one solution or more solutions.

What I’ve tried

I tried to achieve my goal, by changing the return type to an int and count the possible solutions (stops at 2, because if there are two solutions, I can say there are “multiple” solutions). So basically, I just want to know whether there is no, one, or many solution(s):

// Backtracking-Algorithm
public int solver(int[][] board, int count) { //Starts with count = 0
  if (count < 2) {
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        /*
         * Only empty fields will be changed
         */
        if (board[i][j] == EMPTY) {
          /*
           * Try all numbers between 1 and 9
           */
          for (int n = 1; n <= GRID_SIZE; n++) {
            /*
             * Is number n safe?
             */
            if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
              board[i][j] = n;
              if (solver(board, count) > count) {
                count++;
              } else {
                board[i][j] = 0;
              }
            }
          }
          return count;
        }
      }
    }
    return count + 1;
  }
  return count;
}

The problem is that count always goes to “1” and then the algorithm stops.

Question

What changes in the code are necessary to make it work?

Answer

The issue with your code is that it stops after it finds the first solution – more specifically, your code will never change an assigned value to a cell unless it is wrong. This is standard backtracking that you’ve implemented. What you need to do is, once you find one solution, you need to force your code to use other values and see if it also returns a valid solution.

Let’s say this is the last row of your sudoku (where you’re missing the last value), and your count is currently 0 (i.e. no solution so far):

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |

Your code will try all values from 1-9 for that last cell, and once it finds out that 9 is the correct value, it will fill it in and make a recursive call.

On the recursive call, your code will not find any empty values so it will increment count by 1 (so count is now 1) and return, specifically this line: return count + 1;Because you’re not making any further recursive calls at this point, the incremented count will be passed up the recursive stack and and you’ll end up with a value of 1.

What you need to do is, once you’ve found one solution, you need to backtrack again and force increment one of the values. Your last line in the solution you found looks like this:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

You cannot increment the last cell because it’s already at 9, so you set it to 0 / EMPTY and go to the previous value. The previous value is 8, which can be incremented to 9, so you do that and then solve that board:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 0 |

Maybe this doesn’t return a solution, so you go back one more (setting the second last cell to 0 and increment the previous cell:

| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 0 | 0 |

Now see if this gives you a solution. And so on…

TLDR: once you find a solution, you need to feed it back to your code with tighter constraints (i.e. force increment one of the valid values and see if it still gives you another solution).



Source: stackoverflow