# Yet another Java solution

• Hi guys!

In my recursive solution I tried to not simply pick all possible values for an empty cell but to make two optimisations:

1. We pick only valid values that are not violating the constraints of a row, column and box.

2. We choose as the next cell to fill the one with the minimum number of possible values.

Check it out below.

``````public class Solution {

/* Auxiliary class for empty cells with the set of possible values. */
private static class Cell {
public final int x, y;
public final Set<Integer> possibilities;
public Cell(int x, int y, Set<Integer> possibilities) {
this.x = x; this.y = y; this.possibilities = possibilities;
}
}

/* Returns all possible values for the given cell. */
private static Set<Integer> getPossibilities(char[][] board, int x, int y) {
Set<Integer> res = new HashSet<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
for (int i = 0; i < 9; i++) {
res.remove(board[x][i] - '0');
res.remove(board[i][y] - '0');
res.remove(board[3*(x/3) + i/3][3*(y/3) + i%3] - '0');
}
return res;
}

/* Returns the cell with the minimum number of possible values. */
private static Cell findBestEmptyCell(char[][] board) {
Cell res = null;
int minPos = Integer.MAX_VALUE;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == '.') {
Set<Integer> pos = getPossibilities(board, i, j);
if (pos.size() < minPos) {
res = new Cell(i, j, pos);
minPos = pos.size();
}
}
}
}
return res;
}

/*
* 1. Finds the best empty cell with its' possible values.
* 2. Checks if the best cell is with 0 possible values.
*    If so then the current board is not solvable
*    and backtracks with false return value.
* 3. If the board is solvable tries all possible values for the best cell
*    and makes further recursive calls.
*/
public static boolean recSolve(char[][] board) {
Cell best = findBestEmptyCell(board);
if (best != null) {
if (!best.possibilities.isEmpty()) {
for (int p : best.possibilities) {
board[best.x][best.y] = (char) (p + '0');
if (recSolve(board)) return true;
}
board[best.x][best.y] = '.';
}
return false;
}
return true;
}

public void solveSudoku(char[][] board) {
recSolve(board);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.