Sudoku solution validator/verifier/checker implemented in Java

Question

This Sudoku solution validator/verifier/checker implemented in Java is extremely hardcoded code. How do I think modularly?

import java.util.*;
// problems with the code will be reported in comments
public class Example {
 public static void main(String[] args) {
 int[][] solution = {
 { 9, 6, 3, 1, 7, 4, 2, 5, 8 },
 { 1, 7, 8, 3, 2, 5, 6, 4, 9 },
 { 2, 5, 4, 6, 8, 9, 7, 3, 1 },
 { 8, 2, 1, 4, 3, 7, 5, 9, 6 },
 { 4, 9, 6, 8, 5, 2, 3, 1, 7 },
 { 7, 3, 5, 9, 6, 1, 8, 2, 4 },
 { 5, 8, 9, 7, 1, 3, 4, 6, 2 },
 { 3, 1, 7, 2, 4, 6, 9, 8, 5 },
 { 6, 4, 2, 5, 9, 8, 1, 7, 3 }
 };
 boolean ok = true;
 int[] count = new int[9];
 // row-wise loop
 for (int i = 0; i < solution.length; i++) {
 // -1 added for array index starting from 0, means 9 in above means count[8]
 for (int j = 0; j < solution[0].length; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 }
 // column-wise loop
 for (int i = 0; i < solution.length; i++) {
 // -1 added for array index starting from 0, means 9 in above means count[8]
 for (int j = 0; j < solution[0].length; j++) {
 count[solution[j][i] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 }
 // grid check 3x3
 // 1st grid,2nd grid, 3rd grid
 for (int i = 0; i < 3; i++) {
 for (int j = 0; j < 3; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 3; j < 6; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 6; j < 9; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 }
 // 4th,5th,6th grid
 // so on
 for (int i = 3; i < 6; i++) {
 for (int j = 0; j < 3; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 3; j < 6; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 6; j < 9; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 }
 // 7th,8th,9th grid
 // so on
 for (int i = 6; i < 9; i++) {
 for (int j = 0; j < 3; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 3; j < 6; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 for (int j = 6; j < 9; j++) {
 count[solution[i][j] - 1]++;
 }
 ok = checkIfOk(count);
 System.out.println(ok);
 reset(count);
 }
 System.out.println(ok);
 }
 public static void reset(int[] arr) {
 for (int i = 0; i < arr.length; i++) {
 arr[i] = 0;
 }
 }
 public static boolean checkIfOk(int[] arr) {
 for (int i = 0; i < arr.length; i++) {
 if (arr[i] > 1) {
 return false;
 }
 }
 return true;
 }
}

Few of the problems that I will report:

• The code for checking the 3x3 subgrids is repetitive and could be streamlined. It's currently hard-coded for each set of grids (1st-3rd, 4th-6th, 7th-9th) with unnecessary repetition.

• In checkIfOk function, I've not checked for non-appearance of a number.

• Most crucial part of implementation is I didn't know how to return "ok"'s boolean value. That's why I've put all the printlns. I am not aware how to combine all of these systematically.

• meriton: You might find some ideas here

Answer 1

Variable names are important. sodukuBoard conveys much more context than arr.

The public methods are only designed for use inside their class. They should be private.

A single method could take as parameters the start coordinates of a square and evaluate that square. There could also be separate methods for verifying all the rows and all the columns.

The way to combine boolean values is to use && (and) and || (or).

A better way to clear an array is Arrays.fill().

Instead of an array, a better data type to use would be a BitSet. set(), clear() and cardinality() are relevant to this problem.

Homework: familiarize yourself with the contents of java.util.

Try to avoid star imports - they make it harder to see what dependencies a class has. In this case, the import is unused and can be removed.

If I were to rewrite this, it would look more like the below code. In production code, I would also consider making a stateful, immutable class which was passed in a board, ran verification, and tracked results, such as which squares were invalid. But that's a bit beyond the scope of this problem.

Disclaimer - this code is untested and may have off-by-one or other errors.

package codereview.soduku;
import java.util.BitSet;
public class SodukuVerifier {
 public static void main(String[] args) {
 int[][] solution = 
 { 
 { 9, 6, 3, 1, 7, 4, 2, 5, 8 }, 
 { 1, 7, 8, 3, 2, 5, 6, 4, 9 },
 { 2, 5, 4, 6, 8, 9, 7, 3, 1 }, 
 { 8, 2, 1, 4, 3, 7, 5, 9, 6 }, 
 { 4, 9, 6, 8, 5, 2, 3, 1, 7 },
 { 7, 3, 5, 9, 6, 1, 8, 2, 4 }, 
 { 5, 8, 9, 7, 1, 3, 4, 6, 2 }, 
 { 3, 1, 7, 2, 4, 6, 9, 8, 5 },
 { 6, 4, 2, 5, 9, 8, 1, 7, 3 } 
 };
 SodukuVerifier sodukuVerifier = new SodukuVerifier();
 System.out.println(sodukuVerifier.verify(solution));
 }
 
 public boolean verify(int[][] sodukuBoard) {
 return checkRows(sodukuBoard) && checkColumns(sodukuBoard) && checkSquares(sodukuBoard);
 }
 private static boolean checkRows(int[][] sodukuBoard) {
 for (int i = 0; i < sodukuBoard.length; i++) {
 BitSet values = new BitSet();
 for (int j = 0; j < sodukuBoard[0].length; j++) {
 values.set(sodukuBoard[i][j]);
 }
 if (values.cardinality() != 9) {
 return false;
 }
 }
 return true;
 }
 private static boolean checkColumns(int[][] sodukuBoard) {
 for (int i = 0; i < sodukuBoard.length; i++) {
 BitSet values = new BitSet();
 for (int j = 0; j < sodukuBoard[0].length; j++) {
 values.set(sodukuBoard[j][i]);
 }
 if (values.cardinality() != 9) {
 return false;
 }
 }
 return true;
 }
 private static boolean checkSquares(int[][] sodukuBoard) {
 boolean ok = true;
 for (int i = 0; i < 9; i += 3) {
 for (int j = 0; j < 9; j += 3) {
 ok = ok && checkSquare(sodukuBoard, i, j);
 if (!ok) {
 return false;
 }
 }
 }
 return true;
 }
 private static boolean checkSquare(int[][] sodukuBoard, int startRow, int startColumn) {
 BitSet values = new BitSet();
 for (int i = startRow; i < startRow + 3; i++) {
 for (int j = startColumn; j < startColumn + 3; j++) {
 values.set(sodukuBoard[i][j]);
 }
 }
 return values.cardinality() != 9;
 }
}

• Team B.I: This is giving invalid as output for that solution. I think there's a problem.
• Team B.I: I chose this as the accepted answer as this clicked this problem for me. The techniques used are very friendly.

Answer 2

I suggest you implement checking the minisquares in a double loop that iterates over all minisquares and for each minisquare checks that it is valid.

Also, I would have used counter[10]. That way, I don't have to translate between sudoku numbers and the indices to counter.

All in all, I had this in mind:

package com.github.coderodde.sudoku;
public final class SudokuChecker {
 private static final int SUDOKU_DIMENSIONS = 9;
 private static final int MINISQUARE_DIMENSIONS = 3;
 
 public static boolean isValidSolution(final int[][] sudoku) {
 checkDimensions(sudoku);
 preCheck(sudoku);
 
 final IntSet intSet = new IntSet(10);
 
 // Check rows:
 for (int r = 0; r < sudoku.length; r++) {
 for (int c = 0; c < sudoku.length; c++) {
 final int number = sudoku[r][c];
 
 if (intSet.read(number)) {
 return false;
 }
 
 intSet.add(number);
 }
 
 intSet.clear();
 }
 
 // Check columns:
 for (int c = 0; c < sudoku.length; c++) {
 for (int r = 0; r < sudoku.length; r++) {
 final int number = sudoku[r][c];
 
 if (intSet.read(number)) {
 return false;
 }
 
 intSet.add(number);
 }
 
 intSet.clear();
 }
 
 // Check minisquares:
 for (int minisquareY = 0;
 minisquareY < MINISQUARE_DIMENSIONS; 
 minisquareY++) {
 
 for (int minisquareX = 0;
 minisquareX < MINISQUARE_DIMENSIONS;
 minisquareX++) {
 
 for (int r = 0; r < MINISQUARE_DIMENSIONS; r++) {
 for (int c = 0; c < MINISQUARE_DIMENSIONS; c++) {
 final int number =
 sudoku[MINISQUARE_DIMENSIONS * minisquareY + r]
 [MINISQUARE_DIMENSIONS * minisquareX + c];
 
 if (intSet.read(number)) {
 return false;
 }
 
 intSet.add(number);
 }
 }
 
 intSet.clear();
 }
 }
 
 return true;
 } 
 
 public static void main(String[] args) {
 int[][] sudoku = {
 { 9, 6, 3, 1, 7, 4, 2, 5, 8 },
 { 1, 7, 8, 3, 2, 5, 6, 4, 9 },
 { 2, 5, 4, 6, 8, 9, 7, 3, 1 },
 { 8, 2, 1, 4, 3, 7, 5, 9, 6 },
 { 4, 9, 6, 8, 5, 2, 3, 1, 7 },
 { 7, 3, 5, 9, 6, 1, 8, 2, 4 },
 { 5, 8, 9, 7, 1, 3, 4, 6, 2 },
 { 3, 1, 7, 2, 4, 6, 9, 8, 5 },
 { 6, 4, 2, 5, 9, 8, 1, 7, 3 }
 };
 
 System.out.println(isValidSolution(sudoku));
 }
 
 private static boolean isValidNumber(final int number) {
 return 1 <= number && number <= SUDOKU_DIMENSIONS;
 }
 
 private static void checkDimensions(final int[][] sudoku) {
 if (sudoku.length != SUDOKU_DIMENSIONS) {
 throw new IllegalArgumentException(
 "A sudoku with invalid dimensions.");
 }
 
 for (int i = 0; i < sudoku.length; i++) {
 if (sudoku[i].length != SUDOKU_DIMENSIONS) {
 throw new IllegalArgumentException(
 "A sudoku with invalid dimensions.");
 }
 }
 }
 
 private static void preCheck(final int[][] sudoku) {
 for (final int[] row : sudoku) {
 for (final int number : row) {
 if (!isValidNumber(number)) {
 throw new IllegalArgumentException(
 "Contains invalid number: " + number);
 }
 }
 }
 }
}
class IntSet {
 private final boolean[] array;
 
 IntSet(final int length) {
 array = new boolean[length];
 }
 
 void add(final int index) {
 array[index] = true;
 }
 
 boolean read(final int index) {
 return array[index];
 }
 
 void clear() {
 for (int i = 0; i < array.length; i++) {
 array[i] = false;
 }
 }
}

Finally, your count array works like this: if the solution contains numbers outside of the set of allowed numbers, you will get an ArrayIndexOutOfBoundsException. If you have duplicates, some array components will remain zero yet some another array component must become larger than one.

Answer 3

You've already received some good responses about writing this operation in Java.

Here is a pseudocode reimplementation of the scanning/tabulating loops as a more compact single loop.

for cell = 0 to 80 // IDs of 81 cells
 row = cell / 9
 col = cell % 9
 sqr = row/3*3 + col/3
 val = board[row][col]
 countRow[row][val]++
 countCol[col][val]++
 countSqr[sqr][val]++

Left as an exercise is to evaluate the tabulations to ensure the Sudoku meets the criteria.

Because this single purpose operation is unlikely to change to accommodate future enhancements, it is even possible to check the value of each 'tabulator' element (before or after incrementing) to facilitate early (immediate) detection of an invalid Sudoko solution. However, good counter arguments can be put forward for retaining KISS "isolation of purpose" of regions of code.

---

Code Review

Too much code!

Write less code that gets the job done (correctly.)