How do I verify the validity of a Sudoku grid in Java?

Question

I'm trying to create a Sudoku program that checks if a Sudoku grid is valid. I figured out how to check that each row is valid, as well as for each column. However, I'm having trouble coming up with code to check each of the 9 small boxes in the grid. Below is the method I'm trying to use to check each of the small boxes. Only one number can appear for each space in a small box or the method returns false.

    public static boolean isValidSquare(int[][] grid, int i, int j) {
    int[][] square = new int[3][3];
    int row = 0; int column = 0;
    for (int x = i; x < i + 3; x++) {
        for (int y = j; y < j + 3; y++) {
            square[row][column] = grid[x][j];
            column++;
        }
        row++;
    }
    return true;
}

However, when I run it, the method consistently returns true. I've tried changing the conditions in the for loops to i + 2 and j + 2 respectively and it still gives me the same problem.

Or does it have to do with this piece of code which throws to the method?

    for (int i = 0; i < grid.length; i += 3) {
        for (int j = 0; j < grid[i].length; j += 3) {
            if (isValidSquare(grid, i, j) == false)
                return false;
        }
    }

UPDATE: Just tested to see which methods work, the program didn't even get to the ValidSquare part, the Column part is the method that is returning false:

    public static boolean isValidColumn(int[][] grid, int i) {
    for (int j = 0; j < grid[0].length - 1; j++) {
        for (int k = j; k < grid.length; k++) {
            if ((grid[j][i] < 1 || grid[j][i] > 9) || grid[j][i] == grid[k][i])
                return false;
        }
    }
    return true;

I can't figure out what is causing it to continuously declare false, I printed and checked each column and it looks fine to me.

Edit 2: Okay, the column one was just because I set k = to j, and not j + 1. The other problem with the subsquare method is still bothering me, since it throws a OutOfBoundsException at '3'

Answer 1

The biggest problem with isValidSquare is you always return true. Even a cursory look through the code yields no line that will even return false.

Answer 2

Think I get the question and happy to chime in with something, it might help you it might not...hopefully.

I can't speak specifically for JavaScript but I did write a similar program in c a long time ago. You can do this with some simple multiplication if you store your values in a 9x9 array.

If you think - you have 9 small blocks or squares which are 3x3 so 3 is a golden number.

We can arrange these into rows and columns sort of like this:

    # # # | # # # | # # #
    # # # | # # # | # # #
    # # # | # # # | # # #
    ---------------------
    # # # | # # # | # # #
    # # # | # # # | # # #
    # # # | # # # | # # #
    ---------------------
    # # # | # # # | # # #
    # # # | # # # | # # #
    # # # | # # # | # # #

This arranges it into those blocks you need to check, we need to be able to reference a block so let's give them co-ordinates - we can say our entire sudoku grid is a 3x3 grid of blocks. Co-ordinates - 0,0 references the top-left block, 1,0 the top-middle block, 0,2 the top-right block, etc...until we get to 2,2 which references the bottom-right block.

Now we can reference a block, we could write a basic function to cycle through each value in a given block with something like...

/**
 * We can reference any block by setting row and col, for example:
 *
 *    check_block(grid, 0, 0);
 *
 * To reference the upper-left block, or:
 *
 *    check_block(grid, 2, 2);
 *
 * To reference the bottom-right block.
 */
function check_block(grid, row, col) {
    /**
     * We'll use x to index the elements of the horizontal row of a given
     * block, and y to index the elements of the vertical column.
     */
    var x, y;

    /**
     * We know each block is a 3x3 square - we can cycle through these
     * using a couple of nested loops...
     */
    for (y = 0; y < 3; y++) {
       for (x = 0; x < 3; x++) {
          /**
           * To index the digit within the block we simply multiply our
           * row with 3 and add it to y and our col with 3 and add that
           * to x...
           */
          grid[(y + (row * 3))][(x + (col * 3))] ...
       }
    }
}

If you sit and work this out with pen and paper - assume we want to check the values in block 2, 2.

Since each block is a 3x3 array and 3 is our golden number, multiplying the row (2) and col (2) by 3, so essentially we're referencing cell 6, 6.

So by looping through the 3x3 square and adding the x and y values we're working on that individual block:

y = 0, x = 0      y = 0, x = 1      y = 0, x = 2
6,6               6,7               6,8

y = 1, x = 0      y = 1, x = 1      y = 1, x = 2
7,6               7,7               7,8

And so on...sorry for the over-winded spiel and not really sure if it'll help. It's a sound little bit of code though and comes in handy for all sorts of things, sudoku grids being one. It might not fit exactly with the code you have but the theory behind it is solid and quite practical.

Hope you get something useful from it and best of luck with your coding.

Answer 3

Your method

public static boolean isValidSquare(int[][] grid, int i, int j) {
    int[][] square = new int[3][3];
    int row = 0; int column = 0;
    for (int x = i; x < i + 3; x++) {
        for (int y = j; y < j + 3; y++) {
            square[row][column] = grid[x][j];
            column++;
        }
        row++;
    }
    return true;
}

always returns true. There's only one return statement.

Or does it have to do with this piece of code which throws to the method?

I'm not sure what it means to "throw" to a method, but the condition

isValidSquare(grid, i, j) == false

will never be true, based on the previous assumption.

---

I have to question the general design here: Why is isValidSquare a static function anyway?

Why not create a class for a sudoku grid and provide methods to set numbers, check validity, etc?

Your static method works on any int[][], which includes those that aren't even valid sudoku grids. If you have a well encapsulated SudokuGrid class, you can safely assume properly sized and initialized internal private data structures. isValidSquare happily accepts a 2x2 grid of int for example, which is not desirable.

Answer 4

You have a typo in your code:

public static boolean isValidSquare(int[][] grid, int i, int j) {
 int[][] square = new int[3][3];
 int row = 0; int column = 0;
 for (int x = i; x < i + 3; x++) {
     for (int y = j; y < j + 3; y++) {
         square[row][column] = grid[x][j]; // j should be y
         column++;
     }
     row++;
 }
return true;
}

I'm guessing that is the reason why it is not performing as you expect.

Also, as the others stated, your method never returns false and it will not work properly, but it's rather obvious.

I suggest verifying the small box validity by writing it's contents to a set and returning false when method yourSet.add(number) returns false