Comparing values in an array in Java?

You could really simplify things if you don't check that the whole game board is free from all duplicates, but instead check that a specific row, column, and 3x3 square don't have duplicates only when a new value is placed (either by the player, or when loading a game from a file).

This way you would only need three non-nested loops. One each to check that the new value being placed doesn't already exist in its row, column and 3x3 square.

You would also never need to worry about checking for a -1 (assuming you already error check the inputs for the values 1-9).

Note: The "check if a row, column, or 3x3 square adds up to 45" doesn't work. It's a nice idea, but it doesn't catch multiple duplicates (for example, a row of all 5s would pass).

This is a good question and I'm bored, so here's a fairly complete description of one way to do it. Of course, there are many others! This approach is efficient but not especially elegant. I'd like to see what other people come up with.

1) Make a BitSet object for each row, column, and 3x3 square. Put these in arrays, like this:

// Initialize arrays
BitSet[] rows = new BitSet[9];
BitSet[] cols = new BitSet[9];
BitSet[] squares = new BitSet[9];
// Initialize the array elements
for(int i=0;i<9;i++){
    rows[i] = new BitSet(9);
    cols[i] = new BitSet(9);
    squares[i] = new BitSet(9);
}

Now we can go over the grid in one pass and set a bit in the appropriate row, column, and square. By "appropriate" I mean that if we're looking at the i^th row and j^th column, we'll set the bit in and rows[i], cols[j]. To index the elements of squares, we'll use the following layout:

0 1 2
3 4 5
6 7 8

We can get the row and column in the above layout by simply dividing i and j by 3. So the index we want is i / 3 + 3 * ( j / 3 ). Notice that integer division is at work here, so 7 / 3 == 8 / 3 == 2, which means that with i and j equal to 8, we have for example 8 / 3 + 3 * ( 8 / 3 ) = 2 + 3 * 2 = 8.

Putting it all together, we can write the method to check if the puzzle isn't solved like this:

public boolean hasRepeats(){
            // ...
        // initialize rows, cols, and squares as above
            // ...

    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            int gridValue = grid[i + 9 * j];
            if( gridValue == -1 ){
                // Skip empty squares
                continue;
            }
            // Check for repeats
            if( rows[i].get(gridValue) ){
                return true; 
            }
            rows[i].set(gridValue);
            if( cols[j].get(gridValue) ){
                return true;
            }
            cols[j].set(gridValue);
            BitSet square = squares[ i / 3 + 3 * ( j / 3 ) ]
            if( square.get( gridValue ) ){
                return true;
            }
            square.set( gridValue );
        }
    }
    return false;
}

Since you are new to java, I assume you are using a 2D integer array to store the 3x3 square. Your goal is to validate any duplicate integer(except -1) exists in the square.

private static final int WIDTH = 3;
private static final int HEIGHT = 3;
private static int[][] cells = new int[WIDTH][HEIGHT];

And you can initialize the 2D array by -1

for (int i = 0; i < WIDTH; i++) {
    for (int j = 0; j < HEIGHT; j++) {
        cells[i][j] = -1;
    }
}

A simple approach is to use a list to store the user inputs temporarily, and check if the adding input is already existed.

private static boolean validateCells() {
    boolean isValid = true;
    List<Integer> inputValues = new ArrayList<Integer>();
    for (int i = 0; i < WIDTH; i++) {
        for (int j = 0; j < HEIGHT; j++) {
            int inputValue = cells[i][j];
            if (inputValue != -1) {
                if (inputValues.contains(inputValue)) {
                    isValid = false;
                    break;
                } else {
                    inputValues.add(inputValue);
                }
            }
        }
    }
    return isValid;
}

This is obviously not a efficient approach, but it's simple and quite easy to understand for java beginners.

An easy way that is correct by induction would be to load the 9 values an array and then do the following:

1. Convert to a set to ensure no duplicates
2. Convert back to an array
3. Sort the array

Then you can check 3 things to guarantee that the values are valid:

1. Check that the first number (i.e. the lowest) is 1
2. Check that the last number (i.e. the highest) is 9
3. Check that the length of the array is 9 (so you did, in fact, have all 9 numbers present)