Sudoku verifier program

Question

I implemented a Sudoku validation program. Can this be optimized even further in terms of performance?

public class ValidSudoku {
    public boolean verifySudoku(int arr[][], int num, int i, int j, int row, int col) {
        return (verifyRow(arr, num, i, j, col)
               && verifyCol(arr, num, i, j, row)
               && verifyGrid(arr, num, i, j));

    }

    public boolean verifyRow(int arr[][], int num, int i, int j, int col) {
        int k;
        for (k = 0; k < col; k++) {
           if ((arr[i][k] == num) && (j != k)) {
                return false;
            }
        }
        return true;
    }

    public boolean verifyCol(int arr[][], int num, int i, int j, int row){
        int k;
        for (k = 0; k < row; k++) {
            if ((arr[k][j] == num) && (i != k)) {
                return false;
            }
        }
        return true;
    }

    public boolean verifyGrid(int arr[][], int num, int i, int j) {
        int k, l;
        int start_row = i - (i % 3);
        int start_col = j - (j % 3);
        for (k = 0; k < 3; k++) {
            for (l = 0; l < 3; l++) {
                if ((arr[k + start_row][l + start_col] == num) && (i != k + start_row) && (j != l + start_col)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String args[]) {
        ValidSudoku v = new ValidSudoku();
        int i, j;
        int arr[][] = {{3, 1, 6, 5, 7, 8, 4, 9, 2},
                       {5, 2, 9, 1, 3, 4, 7, 6, 8},
                       {4, 8, 7, 6, 2, 9, 5, 3, 1},
                       {2, 6, 3, 4, 1, 5, 9, 8, 7},
                       {9, 7, 4, 8, 6, 3, 1, 2, 5},
                       {8, 5, 1, 7, 9, 2, 6, 4, 3},
                       {1, 3, 8, 9, 4, 7, 2, 5, 6},
                       {6, 9, 2, 3, 5, 1, 8, 7, 4},
                       {7, 4, 5, 2, 8, 6, 3, 1, 9}};
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (!v.verifySudoku(arr, arr[i][j], i, j, 9, 9)) {
                    System.out.print(arr[i][j] + "nay");
                }
            }
        }
    }
}

Answer 1

The methods verifyRow, verifyCol, verifyGrid, and verifySudoku are all only accessed inside this class. Therefore, there is no point in making them public right?

If there do happen to be other classes, just they aren't shown here, you could probably leave verifySudoku as public because it makes sense for another class to possible access those.

---

I think Sudoku should be it's own, immutable, separate class. It should probably hold the 2D int array that is the sudoku board.

Now thinking about, the should be the class with the method verifySudoku (I'd call it isValid) because the method is to validate a sudoku board and the Sudoku class is holding a board to being with.

Here is what I came up with for the class:

public class Sudoku {
    private final int[][] board;
    private final int rows;
    private final int columns;

    public Sudoku(int[][] board, int rows, int columns) {
        this.board = board;
        this.rows = rows;
        this.columns = columns;
    }

    public boolean isValid(...) {
        [code]
    }

    private boolean verifyGrid(...) {
        [code]
    }

    private boolean verifyRow(...) {
        [code]
    }

    private boolean verifyCol(...) {
        [code]
    }
}

---

public boolean verifyRow(int arr[][], int num, int i, int j, int col) {

The argument names i and j are not descriptive whatsoever.

---

int k;
for (k = 0; k < col; k++) {

You do not need to declare the iterator variable outside of the loop. This can and should be turned in to:

for (int k = 0; k < col; k++) {

---

I think you have a very smart algorithm for verifying if the board.

Here is the way I thought of:

1. Create an java.util.ArrayList of the numbers 1-9.
2. In each verify method, copy this ArrayList.
3. Iterate through the row/column/grid's squares
4. If the number is in the array list, go to 6
5. If not, return false
6. Take the number out of the array list
7. If the array list is empty, return true
8. Go to 3

(I believe) This works because, by removing the numbers from the array list, you are making sure that that number is not repeated again in that row, which would make a row invalid if it contained 2+ of the same number.

Here is my implementation in Java:

private boolean verifyRow(int row) {
    List<Integer> numbers = new ArrayList<Integer>(this.allNumbers);

    for(int i = 0; i < this.rows; i++) {
        if(numbers.contains(i)) {
            numbers.remove(new Integer(i)); // using java.util.ArrayList.remove(Object o) so I turned int i to an Integer
            if(numbers.isEmpty()) {
                return true;
            }
        } else {
            return false;
        }
    }
}

This used my Sudoku class idea. allNumbers is the list of numbers 1-9 to copy.

I am not sure which version is faster.