Sudoku verifier in Java

Question

This program verifies if a matrix is a Sudoku or not. These conditions should be verified:

• There are no duplicates in a row, column, or square
• The sum of a row, column, or square should be equal to 45

public class SudokuChecker {    

static int[][] invalidMatrix={

        {5,5,5,5,5,5,5,5,5},
        {1,2,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5},
        {5,5,5,5,5,5,5,5,5}
    };

static int[][] validMatrix={

    {5,3,4,6,7,8,9,1,2},
    {6,7,2,1,9,5,3,4,8},
    {1,9,8,3,4,2,5,6,7},
    {8,5,9,7,6,1,4,2,3},
    {4,2,6,8,5,3,7,9,1},
    {7,1,3,9,2,4,8,5,6},
    {9,6,1,5,3,7,2,8,4},
    {2,8,7,4,1,9,6,3,5},
    {3,4,5,2,8,6,1,7,9}
    };

static int rSum = 0;
static int cSum = 0;
static int squareSum = 0;

static int[] rArray = new int[9];
static int[] cArray = new int[9];
static int[] squareArray = new int[9];

/*
 * check of there is duplicates 
 */

public static boolean checkDuplicate(int[] array){

    Boolean duplicate = false;
    Set<Integer> set= new HashSet<>();
    for(int i : array){
        if(set.contains(i)){
            duplicate = true;
    } else {
        set.add(i);         
    }
    }
    return duplicate;
}

/*
 * check if the sum of the element of a row are equals to 45 
 */

public static boolean rowSum(int[][] matrix){
    boolean correct = true;
    for(int i =0; i < matrix.length; i++){
        for(int j=0 ; j < matrix[i].length; j++){
            rArray[j] = matrix[i][j];
            rSum += rArray[j];  
        } 
        if(rSum != 45 || checkDuplicate(rArray) ){              
            correct = false;
            break;
        }
        rSum = 0;
    }
    return correct;

}

/*
 * check if the sum of the elements of a col are equals to 45
 */

public static boolean colSum(int[][] matrix){
    boolean correct = true;
    for(int j=0 ; j < matrix.length; j++){
        for(int i=0 ; i < matrix.length ; i++){
            cArray[i] = matrix[i][j];
            cSum += cArray[i];
        }
        if(cSum != 45 || checkDuplicate(cArray)){
            correct = false;
            break;
        }
        cSum = 0;
    }
    return correct;
}

/*
 * check if the sum of the elemnts of a square 3x3 are equals to 45
 */

public static boolean squareSum(int[][] matrix){
    boolean correct = true;
    for(int i=0; i < matrix.length ; i = i + 3){
        for(int j=0; j < matrix.length ; j = j +3){

            squareArray[0] = matrix[i][j];
            squareArray[1] = matrix[i][j+1];
            squareArray[2] = matrix[i][j+2];
            squareArray[3] = matrix[i+1][j];
            squareArray[4] = matrix[i+1][j+1];
            squareArray[5] = matrix[i+1][j+2];
            squareArray[6] = matrix[i+2][j];
            squareArray[7] = matrix[i+2][j+1];
            squareArray[8] = matrix[i+2][j+2];

            squareSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2] 
                      + matrix[i+1][j] + matrix[i+1][j+1] + matrix[i+1][j+2] 
                      + matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2] ;
            if(squareSum != 45 || checkDuplicate(squareArray)){
                correct = false;
                break;
            } else{                 
                squareSum = 0;
            }
        }   
    }
    return correct;
}

/*
 *  Test
 */

public static boolean test(int[][] matrix){

    boolean correct = true;
    if (!(rowSum(matrix) && colSum(matrix) && squareSum(matrix))){
        correct = false;
    }
    return correct;

}

public static void main(String[] args) {

    System.out.println(test(invalidMatrix) ? "Sudoku valide" : "Sudoku invalide");
}
}

Answer 1

    Boolean duplicate = false;
    Set<Integer> set= new HashSet<>();
    for(int i : array){
        if(set.contains(i)){
            duplicate = true;
    } else {
        set.add(i);         
    }
    }
    return duplicate;

This can be written more briefly as

    Set<Integer> seen = new HashSet<>();
    for (int i : array) {
        if (!seen.add(i)) {
            return true;
        }
    }

    return false;

You do not need to check contains before add. The add will check contains for you.

You do not need to keep going after you've found a duplicate. You can stop immediately and return. Everything else will be just wasted work.

You do not need the duplicate variable. You can just return instead.

The indent is now consistent, and I added some horizontal whitespace for readability.

Another alternative would be

    int[] seenCounts = new int[array.length];
    for (int i : array) {
        i--;
        if (seenCounts[i] >= 1) {
            return true;
        } else {
            seenCounts[i]++;
        }
    }

    return false;

The array will be more efficient than the Set.

Also, this will enforce that the numbers are in the range 1 to 9. If you had a 0 or 10, this code would throw an exception. This is important because an array with five 9s and four 0s would return true;

Answer 2

You only use static fields which reduces the usefulness of your solution, as you can only check one Sudoku board at a time. Learn more about object-oriented programming and use classes and objects without static fields.

Checking a 3x3 square can be improved by writing another (nested) for-loop, instead of hardcoding the position of the squares to check (which is prone to coding-errors).

You check for non-duplicates and for the sum 45, but what about the integers \$0, -2, 4, 5, -21, 1, 13, 42, 3\$? They also add up to 45. So what you have here is not necessarily a Sudoku checker, it could be a Math puzzle checker.

Answer 3

Javadoc.

---

Why is everything is static?

---

Why are all members package-private and all functions public?

---

static int rSum = 0;
static int cSum = 0;

You should opt to have easily readable and longer variable names, like columnSum and rowSum.

---

public static boolean checkDuplicate(int[] array){

    Boolean duplicate = false;
    Set<Integer> set= new HashSet<>();
    for(int i : array){
        if(set.contains(i)){
            duplicate = true;
    } else {
        set.add(i);         
    }
    }
    return duplicate;
}

Let's start with the fact that boolean is not the same Boolean and that you avoid Autoboxing. Also this function could return early and utilize a simple trick to become more efficient.

private static final boolean hasDuplicates(int[] array) {
    // We will be using the value of the cell as index for accesing
    // the "duplicate state" that this array holds.
    boolean[] containedNumbers = new boolean[10];

    for (int value : array) {
        if (value > 0 && containedNumbers[value]) {
            return true;
        } else {
            containedNumbers[value] = true;
        }
    }

    return false;
}

Also, with this function you can only test rows according to your current implementation. It would be more interesting to have a function which allows you to test "areas".

private static final boolean hasDuplicates(int[][] matrix, int startX, int startY, int endX, int endY) {
    boolean[] containedNumbers = new boolean[10];

    // This code is untested, sorry.
    for (int y = startY; y <= endY; y++) {
        for (int x = startX; x <= endX; x++) {
            int value = matrix[x][y];

            if (value > 0 && containedNumbers[value]) {
                return true;
            } else {
                containedNumbers[value] = true;
            }
        }
    }

    return false;
}

private static final boolean hasDuplicatesInRow(int[][] matrix, int row) {
    return hasDuplicates(matrix, row, 0, row, COLUMN_SIZE);
}

private static final boolean hasDuplicatesInColumn(int[][] matrix, int column) {
    return hasDuplicates(matrix, 0, column, ROW_SIZE, column);
}

That would make it much more versatile.

---

public static boolean colSum(int[][] matrix){
    boolean correct = true;
    for(int j=0 ; j < matrix.length; j++){
        for(int i=0 ; i < matrix.length ; i++){
            cArray[i] = matrix[i][j];
            cSum += cArray[i];
        }
        if(cSum != 45 || checkDuplicate(cArray)){
            correct = false;
            break;
        }
        cSum = 0;
    }
    return correct;
}

• Return early whenever you can.
• Define constants for the size ROW_SIZE and COLUMN_SIZE to make the code easier readable.
• I know that i and j and k are used for loops, but start using declarative variable names like index, counter, indexX or x.
• Don't use magic numbers like 45, define a constant for it with a good name.

---

I never wrote a Sudoku checker, but wouldn't it be enough to check each row, column and block if they contain 1 to 9? That would remove any other check like calculating the sum.

---

Overall, in pseudo-code, what you want is this:

public class SudokuChecker
    public boolean isSolved(int[][] sudoku)

And that will be your API, which can be used like this:

SudokuChecker checker = new SudokuChecker();

if (checker.isSolved(sudoku)) {
    // Okay.
} else {
    // Not okay.
}

If you don't exactly need an instance, you could amke everything static, but it might be the better choice to make it extendable and provide a default instance:

public class SudokuChecker
    public static final SudokuChecker INSTANCE = new SudokuChecker();

if (SudokuChecker.INSTANCE.isSolved(sudoku)) {
    // Okay.
} else {
    // Not okay.
}

Answer 4

Big Picture

• you should verify all numbers are in the range 1..9 (to exclude bogus solutions with negative or greater numbers)
• if you do that in addition to duplicate checking, verifying the sum is redundant

Code Structure

• well done on reducing code duplication by factoring out the duplicate testing to its own method, but why not do the same for the sum verification?
• the method names are misleading:
  • colSum, rowSum and squareSum compute many sums, not just one
  • colSum, rowSum and squareSum also check for duplicates
  • checkDuplicates also verifies that numbers are positive

Coding Practices

• variables only used by a single method (such as rArray, cArray, squareArray, rSum, cSum, squareSum) should be local to that method, not static fields. This makes it apparent where they are used, and simplifies refactoring since you don't have to check which other methods may be using these fields.
• a Set<Integer> is a viable choice, but if you know the contents to be integers in a dense range, you can use the more efficient Bitset, or - if both you and the expected reader are comfortable with binary numbers - use the bits of a single int to hold your set, which allows for faster equality comparison of sets.

Personally, I'd have done something like this:

public class SudokuVerifier {

    final int[][] numbers;

    private SudokuVerifier(int[][] numbers) {
        this.numbers = numbers;
    }

    public boolean valid() {
        return checkAreasOfSize(1, 9)
            && checkAreasOfSize(3, 3)
            && checkAreasOfSize(9, 1);
    }

    private boolean checkAreasOfSize(int sizeX, int sizeY) {
        for (int ay = 0; ay < 9; ay += sizeY) {
            for (int ax = 0; ax < 9; ax += sizeX) {
                if (!checkArea(ax, ax + sizeX, ay, ay + sizeY)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean checkArea(int startX, int endX, int startY, int endY) {
        int seen = 0;
        for (int y = startY; y < endY; y++) {
            for (int x = startX; x < endX; x++) {
                seen |= 1 << numbers[x][y];
            }
        }
        return seen == 0b1111111110;
    }
}

Answer 5

During debugging no problem about using a test matrix :

   static int[][] invalidMatrix={

        {5,5,5,5,5,5,5,5,5},
        .....
    };

static int[][] validMatrix={

    {5,3,4,6,7,8,9,1,2},
    ...
    };

But it's realy helpful if you let user try different cases:

int[][] grid = readSolutions();
 //get user solution
 private static int[][] readSolutions() {
    Scanner input = new Scanner(System.in);
    int[][] grid = new int[9][9];
    System.out.println("Enter full solution");
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid.length; j++)
            grid[i][j] = input.nextInt();

    return grid;
}

Also i see you have wrote to much code while you can minimize that too much, for example you need only two methods for checking rows, columns, diagonals.

So the full solution would be look like:

public class SudokuChecker { 
     int[][] grid = readSolutions();

        System.out.println((isValid(grid) ? "It's valid solution!" : "It's not valid."));
    }

    private static boolean isValid(int[][] grid) {

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                if (grid[i][j] < 1 || grid[i][j] > 9
                        || !isValid(i, j, grid))
                    return false;
            }
        }
        return true;
    }

    private static boolean isValid(int i, int j, int[][] grid) {
        //check columns
        for (int column = 0; column < grid.length; column++)
            if (column != j && grid[i][column] == grid[i][j])
                return false;
        //check rows
        for (int row = 0; row < grid.length; row++)
            if (row != i && grid[row][j] == grid[i][j])
                return false;
        //check diagonals
        for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
            for (int column = (j / 3) * 3; column < (j / 3) * 3 + 3; column++)
                if (row != i && column != j && grid[row][column] == grid[i][j])
                    return false;

        return true;
    }

    private static int[][] readSolutions() {
        Scanner input = new Scanner(System.in);
        int[][] grid = new int[9][9];
        System.out.println("Enter full solution");
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid.length; j++)
                grid[i][j] = input.nextInt();

        return grid;
    }
}