How to validate Sudoku With O(n2) complexity

Sudoko is number placement puzzle, We have to fill 9X9 matrix with numbers ranging 1 to 9 and  following criteria should be fulfilled.

1)  Each row should contain unique digits
2)  Each column should contain unique digits
3)  Each subgrid or region (3X3)(Coloured) should also contain unique digits

For any valid Sudoku, above criterion should be fulfilled.
First we have to check, it should contain digits from 1-9 and should not be repeated in same row. Same is true for column and subgrid.






Lets take a row, it is nothing but 1-D Array with size 9.

How to check whether array has duplicate number or missing number from given range 1-9. ...???

One way to solve this problem is, Sort the array and validate it. Sorting will work here but the complexity would be nlogn or O(n)(counting sort). In case of counting sort space complexity would be O(n).

Is there any way to solve this problem in O(n) time complexity and space complexity should be O(1)...???

Yes, we can achieve it by using XOR operation. Column validation could also be done in similar fashion.

Now, I have to check each highlighted sub grid(3X3).






Lets write a Program to solve this problem in O(n2):

public static boolean isSudokuSolutionValid(int[][] sudoku) {
        int row = 1;
        int col = 1;
        int block1 = 1;
        int block2 = 1;
        int block3 = 1;
        boolean isValid = true;
       for (int i = 0; i < sudoku.length; i++) {

            for (int j = 0; j < (sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block1 = block1 ^ sudoku[i][j];
            }

            for (int j = 3; j < 3+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block2 = block2 ^ sudoku[i][j];
            }
            for (int j = 6; j < 6+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block3 = block3 ^ sudoku[i][j];
            }
            if ((i + 1) % 3 == 0) {
                if (block1 != 0 || block2 != 0 || block3 != 0) {
                    return false;
                }
                block1 = 1;
                block2 = 1;
                block3 = 1;
            }
            if (row != 0 || col!=0) {
                return false;
            }
            row = 1;
            col = 1;
        }
        return isValid;
    }


 Above Sudoku is  an example of invalid Sudoku.

Above Sudoku is an example of valid Sudoku.

This Problem takes O(n2) complexity to validate whether Sudoku is valid or not.