**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?

## Advertisement

## 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.