Java solution to check if a Sudoku solution is valid

Question

Here's my solution to checking if a Sudoku board is valid. The algorithm checks the following,

• Rows add up to 45
• Columns add up to 45
• Rows have no duplicates
• Cols have no duplicates
• Every 3X3 sub-grid has no duplicate

Invite comments.

public class Checker {
 private int size;
 private int[][] board;
 public Checker(int size){
 this.size = size;
 board = new int[size][size];
 }
 private boolean rowCheck(){
 int sum = (size*(size+1))/2;
 int count = 0;
 for (int i = 0; i <size ; i++) {
 for (int j = 0; j < size ; j++) {
 count += board[i][j];
 }
 if(count != sum) return false;
 count = 0;
 }
 return true;
 }
 private boolean columnCheck(){
 int sum =0;
 int count = 0;
 for (int i = 0; i <size ; i++) {
 for (int j = 0; j <size ; j++) {
 count += board[j][i];
 }
 if(count != sum) return false;
 count = 0;
 }
 return true;
 }
 private boolean checkRowDuplicates(){
 HashSet<Integer> set = new HashSet<>();
 for (int i = 0; i <size ; i++) {
 for (int j = 0; j < size ; j++) {
 set.add(board[i][j]);
 }
 if(set.size() != size) return false;
 set = null;
 }
 return true;
 }
 private boolean checkColumnDuplicates(){
 HashSet<Integer> set = new HashSet<>();
 for (int i = 0; i <size ; i++) {
 for (int j = 0; j < size ; j++) {
 set.add(board[j][i]);
 }
 if(set.size() != size) return false;
 set = null;
 }
 return true;
 }
 private boolean checkSubBoardDuplicates(){
 return (subBoardTraversal(0,3,0,3) && subBoardTraversal(0,3,3,6) && subBoardTraversal(0,3,6,9) && subBoardTraversal(3,6,0,3)
 && subBoardTraversal(3,6,3,6) && subBoardTraversal(3,6,6,9) && subBoardTraversal(6,9,0,3) && subBoardTraversal(6,9,3,6)
 && subBoardTraversal(6,9,6,9));
 }
 private boolean subBoardTraversal(int rowStart, int rowFinish, int colStart, int colFinish){
 HashSet<Integer> set = new HashSet<>();
 for (int i = rowStart; i < rowFinish ; i++) {
 for (int j =colStart ; j < colFinish; j++) {
 set.add(board[i][j]);
 }
 if(set.size() != 9) return false;
 }
 return true;
 }
 public boolean isValid(){
 return(rowCheck() && columnCheck() && checkRowDuplicates() && checkColumnDuplicates() && checkSubBoardDuplicates());
 }
 public void trace(){
 for (int i = 0; i < size; i++) {
 for (int j = 0; j < size; j++) {
 System.out.print(board[i][j] + " ");
 }
 System.out.println();
 }
 }
}

• Mathieu Guindon: Should that last closing brace not be part of the code block? Remember that markdown text requires 4 leading spaces to be considered a code block. You can paste directly from your IDE, select everything, and hit Ctrl+K to add the 4 spaces across the entire selection. Feel free to edit.
• Kevin W.: Quick note - you may want to check if the numbers are between 1 and 9
• Captain Man: -9 -8 -7 -6 -5 -4 -3 -2 89 is a valid row/column? :)
• Zeus: How is it valid, it doesn't add up to 45.
• holroy: Your code for columnCheck is flawed as the sum is always zero...

Answer 1

Your setting of count = 0 should be immediately before the appropriate for loop, not after it, and I would actually call that variable sum (renaming your sum to target) since it's not really a "count" at all, e.g:

private boolean rowCheck(){
 int target = size * (size + 1) / 2;
 for (int i = 0; i <size; i++) {
 int sum = 0; // declaration moved, too
 for (int j = 0; j < size ; j++) {
 sum += board[i][j];
 }
 if (sum != target) return false;
 }
 return true;
}

The point being that you should be setting the variable in advance of the loop, not resetting it afterwards (that being a pointless operation on the final iteration).

I would probably also move target into a class member, calculated in the constructor.

• holroy: The count is reset before the next inner loop, so it makes sense, but looks cleaner when done in front of inner loop.

Answer 2

• DRY

  Code for columns and rows is identical except the board access (board[i][j] and board[j][i] respectively). Such minute difference is hard to spot, and the reviewer (or maintainer) has hard time understanding what's going on. I recommend to factor the common part out, along the lines of:

  bool rowCheck() {
   return boardCheck(rowWize);
  }
  bool columnCheck() {
   return boardCheck(columnWize);
  }
  bool boardCheck(Callable<Integer,Integer> boardAccess) {
   ....
   value = boardAccess(i, j);
   ....
  }
  

  or with lambdas instead of callable wrappers. See this discussion for details.

• HashMap

  seems like overkill. A bool seen[size] initialized to false and

   value = board[i][j] - 1;
   if (seen[value]) {
   return false;
   } else {
   seen[value] = true;
   }
  

  achieves the same goal with much less overhead. Of course you'd need a bound check.

  The side effect of this approach is that your way may have false positives as @CaptainMan noticed in the comment.

• Betlista: I'd also check, that value < seen.lengthand probably also value >= 0... #HashMap

Answer 3

Why there is a size int? Can it be something different than 9? If so, let it be say 16 (4x4 version if such exists), but then these hardcoded values are wrong:

private boolean checkSubBoardDuplicates(){
 return (subBoardTraversal(0,3,0,3) && subBoardTraversal(0,3,3,6) && subBoardTraversal(0,3,6,9) && subBoardTraversal(3,6,0,3)
 && subBoardTraversal(3,6,3,6) && subBoardTraversal(3,6,6,9) && subBoardTraversal(6,9,0,3) && subBoardTraversal(6,9,3,6)
 && subBoardTraversal(6,9,6,9));
}

Answer 4

There are flaws in your design, and room for improvements, so here are some comments to choice of coding algorithm:

• Bug: columnCheck always return false – In columnCheck you set sum=0, so this should return false alway, that is if the badly named count (which actually is a sum, and not a count) has increased it value during the loop
• Feature: Relying on the sum to be 45 – As indicated in comments, there are multiple combinations of numbers which gives the sum 45. I.e. \1ドル + 2 + 4 + 4 + 5 + 6 + 6 + 8 + 9\$ or \$ -9 + -8 + -7 + -6 + -5 + -4 + -3 + -2 + 89\$. The first would fail on non-unique numbers, and the second could be countered limiting to the numbers 1 through 9.
• Inefficient loop constructions – Your code loops 5 times through the double loop from 1 through 9 (in the standard case). Using a little more memory, you could loop through the double loop once, and still find the same solution.

Alternate solution

My suggestion is to use 3 * size boolean arrays of size dimension to keep track of whether all numbers have been visited. In the standard case with size=9, there would be 9 arrays for keeping track of the rows we're checking, 9 arrays for the columns, and 9 arrays for the squares within the board.

Instead of using the possibly expensive HashSet or the slightly unreliable sum of 45 for checking uniqueness, I suggest to check the value to be in the correct range, and that corresponding value cell in either of corresponding row, column or square has not been visited before.

Here is a tested implementation of this algorithm:

public boolean isValid() {
 boolean[][] row = new boolean[size][size];
 boolean[][] column = new boolean[size][size];
 boolean[][] square = new boolean[size][size];
 int value, square_no;
 for (int x = 0; x < size; x++) {
 for (int y = 0; y < size; y++) {
 value = board[x][y] - 1;
 // Check for valid values
 if ((value < 0) || (value >= size)) {
 return false;
 }
 // Calculate the square number using mod and div
 // NB! This should be generalised somewhat...
 square_no = (x / 3) + (y / 3) * 3;
 // Check if this value has been seen in row, column or square
 if (row[y][value] ||
 column[x][value] ||
 square[square_no][value] ) {
 return false;
 } else {
 // if not, mark it as seen
 row[y][value] = true;
 column[x][value] = true;
 square[square_no][value] = true;
 }
 }
 }
 return true;
}

This should replace most of your methods, whilst still providing the correct result on whether the sudoku has been solved correctly or not.