9
\$\begingroup\$

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");
}
}
\$\endgroup\$
  • 4
    \$\begingroup\$ The actual conditions of a valid sudoku are "each of the digits 1 through 9 is present". Do you have a proof that "no duplicates and sum is 45" is always equivalent to the actual condition? Because "1, 2, 3, 4, 5, 6, 7, -1, 18" has no duplicates and sums to 45. \$\endgroup\$ – Eric Lippert Nov 20 '17 at 16:21
  • \$\begingroup\$ @EricLippert We dont really need the sum to be 45 right ? Just no duplicates and the digits are between 1 and 9. \$\endgroup\$ – Blaviken25 Nov 21 '17 at 0:00
  • 1
    \$\begingroup\$ That's what I'm asking you. I'm claiming that the sudoku property is that each of the digits from 1 to 9 is present; you're claiming that this is equivalent to "adds to 45 with no duplicates", but I cannot see how that is necessarily true. If it is not necessarily true, then surely you should write your program to check to see if each of the digits from 1 to 9 is present. If you do so your program will get shorter and easier to understand. \$\endgroup\$ – Eric Lippert Nov 21 '17 at 1:23
  • \$\begingroup\$ What if you form 28 sets: the set of numbers 1-9, the sets of all the rows, the sets of all the columns, and the sets of all the squares. If you then intersect those sets all together and the resulting set has less than 9 elements, then you know that at least one of your sets was missing a value. \$\endgroup\$ – Eric Lippert Nov 21 '17 at 1:26
9
\$\begingroup\$
    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;

\$\endgroup\$
  • 3
    \$\begingroup\$ You can do Arrays.stream(arr).distinct().count() == 9 to ensure they're all unique. Explicit loops are so 2013 ;) \$\endgroup\$ – JollyJoker Nov 20 '17 at 8:02
  • \$\begingroup\$ @JollyJoker That seems more like an answer than a comment. \$\endgroup\$ – mdfst13 Nov 20 '17 at 20:06
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I tried to avoid a third for-loop. This is why i used hardcoding, Bad idea i guess. Thanks, i will update my code to improve it. \$\endgroup\$ – Blaviken25 Nov 19 '17 at 21:05
  • \$\begingroup\$ @Damine25 If you're interested I can recommend taking a look at a Sudoku solver I wrote a few years ago. Although written in C# and not Java, you might be able to re-use some ideas and approaches from that. Or just read it for fun. \$\endgroup\$ – Simon Forsberg Nov 19 '17 at 21:39
  • \$\begingroup\$ i'll check it out for sure ! \$\endgroup\$ – Blaviken25 Nov 19 '17 at 22:59
6
\$\begingroup\$

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.
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Speaking of rSum and cSum, I just realized: Why are they not local variables? \$\endgroup\$ – Simon Forsberg Nov 19 '17 at 21:37
  • \$\begingroup\$ Thanks for the best practice advices. Why everything is static ? Well, i tried to make a one class solution, this is why i didn't use objects and classes like in Hackerrank and Codingame. And all methods and members are statics because i can't access them otherwise. \$\endgroup\$ – Blaviken25 Nov 19 '17 at 21:39
  • 1
    \$\begingroup\$ @Damine25 "a one class solution" doesn't have to exclude non-static fields and methods. If you make the methods static because you need to access them, you should learn more about what the static keyword really means and how you can write code without it. Trust me, it is a very good coding practice to avoid excessive use of static. \$\endgroup\$ – Simon Forsberg Nov 19 '17 at 21:41
  • \$\begingroup\$ @SimonForsberg Thanks, refering to what i know, static allows us to use methods and variables without instanciating them, right ? By others mothods to access variables, you mean encapsulation ? \$\endgroup\$ – Blaviken25 Nov 19 '17 at 22:48
  • 1
    \$\begingroup\$ @Phil because 0 is not used - things are 1 indexed here - so the index maps directly to the presence. \$\endgroup\$ – Boris the Spider Nov 20 '17 at 7:41
5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the best practice advices ! Really appreciate that. \$\endgroup\$ – Blaviken25 Nov 19 '17 at 23:03
  • \$\begingroup\$ Using a bits here for the sake of a few words of storage or a few processor cycles encourages code which is exceedingly hard to understand and maintain. Especially as you have no comments in your code to explain what is going on and why such a non-straightforward approach is necessary. \$\endgroup\$ – Phil Nov 20 '17 at 4:50
  • \$\begingroup\$ I agree with @Phil on the bits. That said, I prefer not to name method check..., but rather isAreaValid or something. That makes the resulting boolean easier to understand. BTW. I really like the logic behind area checking and the reuse. \$\endgroup\$ – RobAu Nov 20 '17 at 15:02
  • \$\begingroup\$ @Phil: Whether this is hard to understand really depends on the team composition. If team members have any background in a low level programming language, this is actually more straightforward and expressive than the map API. But yes, if your team only writes high level code you should a BitSet instead, as I write in my answer ... \$\endgroup\$ – meriton Nov 20 '17 at 17:33
  • \$\begingroup\$ I find this very clear, but it don't like that it has-a Sudoku board. It should take the int[][] numbers board as a parameter and pass it down. I'd make all methods static. This has no business being stateful. \$\endgroup\$ – David Conrad Dec 3 '17 at 9:14
0
\$\begingroup\$

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;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.