Java: Sudoku solver

Question

I'd like a review on anything including optimizations, corrections, suggestions for robustness, adherence to good coding practices, etc.

I also request verification of the complexity: O(nⁿ), where n is the row length or column length.

public final class Sudoku {
 private Sudoku() {}
 private static void printSolution (int[][] board) {
 for (int i = 0; i < board.length; i++) {
 for (int j = 0; j < board[0].length; j++) {
 System.out.print(board[i][j] + " : ");
 }
 System.out.println();
 }
 }
 private static Set<Integer> getNumber(int[][] board, int row, int col) {
 final Set<Integer> intsToAvoid = new HashSet<Integer>();
 // check - row
 for (int i = 0; i < board[0].length; i++) {
 if (board[row][i] > 0) {
 intsToAvoid.add(board[row][i]);
 }
 }
 // check - col
 for (int i = 0; i < board.length; i++) {
 if (board[i][col] > 0) {
 intsToAvoid.add(board[i][col]);
 }
 }
 // check - cube
 int lowerRowIndex = (row / 3) * 3;
 int lowerColumnIndex = (col / 3) * 3;
 for (int i = lowerRowIndex; i < lowerRowIndex + 3; i++) {
 for (int j = lowerColumnIndex; j < lowerColumnIndex + 3; j++) {
 if (board[i][j] > 0) {
 intsToAvoid.add(board[i][j]);
 }
 }
 }
 final Set<Integer> candidateInts = new HashSet<Integer>();
 for (int i = 1; i <= board.length; i++) {
 if (!intsToAvoid.contains(i)) { 
 candidateInts.add(i);
 }
 }
 return candidateInts;
 }
 private static boolean solveSudoku (int[][] board, int row, int col) {
 // traversing the matrix.. go to next row once all columns in current row are traversed.
 if (col == board[0].length) {
 row++;
 if (row == board.length) {
 printSolution(board);
 return true;
 }
 col = 0;
 }
 if (board[row][col] > 0) {
 return solveSudoku(board, row, col + 1);
 } else {
 for (int i : getNumber(board, row, col)) {
 board[row][col] = i;
 if (solveSudoku(board, row, col + 1)) return true;
 board[row][col] = 0;
 }
 }
 return false;
 }
 /**
 * Expects an n * n matrix and returns true and prints sudoku solution for valid input.
 * 
 * @param sudoku the n*n matrix to solve
 * @return true or false, true indicating the solution to solve.
 */
 public static boolean solve (int[][] sudoku) {
 return solveSudoku(sudoku, 0, 0);
 }
 public static void main(String[] args) {
 int[][] board = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
 {5, 2, 0, 0, 0, 0, 0, 0, 0},
 {0, 8, 7, 0, 0, 0, 0, 3, 1},
 {0, 0, 3, 0, 1, 0, 0, 8, 0},
 {9, 0, 0, 8, 6, 3, 0, 0, 5},
 {0, 5, 0, 0, 9, 0, 6, 0, 0},
 {1, 3, 0, 0, 0, 0, 2, 5, 0},
 {0, 0, 0, 0, 0, 0, 0, 7, 4},
 {0, 0, 5, 2, 0, 6, 3, 0, 0}};
 System.out.println(solve (board));
 }
}

Answer 1

Private constructor

It is considered good style throw an error in a constructor if they are not supposed to be called, even not from within the class where a private instructor could be invoked from:

private Sudoko() {
 throw new AssertionError();
}

Use the for-each loop instead of explicit iteration

For example:

private static void printSolution(int[][] board) {
 for (int[] row : board) {
 for (int value : row) {
 System.out.print(value + " : ");
 }
 System.out.println();
 }
}

This is true for all other loops in your application. Specifically for the above iteration: Did you really want to only iterate over row 1?

It is better object-oriented style to use instances instead of implement static delegates

You could consider an API like that:

int[][] grid = { ... };
SolvedSudoku solvedSudoku = new SudokuSolver(grid).solve();
solvedSudoku.printResult(System.out);
int[][] solvedSudokuGrid = solvedSudoku.getSolvedGrid();

where you provide rich information and better adapt changes in the future. It would further allow you to change functionality by overriding methods in the future. Moreover, it makes your program more readable.

Consider using an enum type

It might be a little awkward in the beginning, but an enum type would increase your application's type safety. Consider this:

1. Use of int: Your grid contains a value of 19 or -7. Your program can at best throw an exception at runtime.
2. Use of an enum: Your compiler will prevent a grid with a value of 19 from being compiled. You could have a enum SudokuValue { ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, UNDEFINED }. This would also allow you to implement methods for these values such as for example SudokuValue#isDefined(). As another benefit, enums can be stored in EnumSets quite efficiently what is not true for your boxing Set<Integer>.

Further, this would increase the readability of your code.

Consider implementing a type for your board / grid

This would allow you to define methods such that instead of

getNumber(board, row, col)

you could write:

board.getNumber(row, col)

This would again improve the readability of your code. Also, you could prevent the construction of invalid grids where different rows were for example of different size. Also, you would allow the implementation of other grid implementations as for example a lazy grid that loads values on demand, since you would only require a certain type which would not necessarily need to be represented by an array.

Use immutability as much as possible

You should create a new array as a result grid instead of altering the existing one. This way, you could for example allow different solving algorithms to run concurrently on the same grid without fearing to run into concurrency issues. Consider this also when returning Sets. Maybe you want to cache values one day? Make it explicit that these sets are not to be altered, i.e. immutable, and make this part of the method's explicit contract by wrapping the return values into a Collections#immutableSet. Also, use the final keyword whenever possible if you consider changing your solutions to using specified types.

As for optimization

Don't do it (now)! Do such (micro-)optimizations when you find out that speed is an issue. It is more important to make your code readable and understandable. Apart from algorithmic considerations, you should allow the JIT compiler to handle micro-optimizations for you. Some people might recommend you to use static handles for improving run time behavior but this is in general not true. Trust the JVM, it is smarter than you might think it is, it does not need your help with this. What you should optimize is algorithmic complexity what brings me to the last hint.

Algorithm complexity

Your methods are of the following complexity:

1. print: Iterates over the matrix: O(n^2). (This is the same complexity as building the array though, so this is a minimum for this program anyways.)

2. getNumber: Iterates only over a row: O(n)

3. solveSudoku: In the worst case, you are making on average (n-2)^2 recursive calls for n while iterating over worst n values of a row. (This is quite inefficient.) Writing this relation down:

   T(0) = 1

   T(n + 1) = n^3 T(n) + 1

If you resolve this equation system, you find out that your complexity is indeed of O(nⁿ).

This means that your overall implementation is also of this complexity.

• Gareth Rees: It's not surprising that the overall complexity is exponential: generalized Sudoku is NP-hard!
• Rafael Winterhalter: True, there are however algorithms that can solve the problem faster which only succeed most likely.