Sudoku Backtracking with Solution Counter

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

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.