Check whether the sudoku is valid or not

I find sudoku puzzle very interesting. Lets write a program to find whether the given sudoku puzzle is valid or not.

Problem statement:

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1–9 without repetition.
2. Each column must contain the digits 1–9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1–9 without repetition.

Solution:

The above problem can be solved by checking all the three conditions which need to be satisfied for a Sudoku to be valid.

Algorithm:

Divide the problem into three sub-problems

1. Check for each row consisting unique number
2. Check for each column consisting unique number
3. Check for each of 9 3X3 sub-boxes consisting unique number

For each sub-problem

1. Declare a set for each row/column/sub-box
2. Check whether the current row/column/sub-box have all unique no or not
3. If any row/column/sub-box fails to have all unique numbers, return false

If there is no such row/column/sub-box that returns false

Then it’s a valid Sudoku & return true;

public void solveSudoku(char[][] board) {
    helper(board);
}
 
private boolean helper(char[][] board){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            if(board[i][j]!='.'){
                continue;
            }
 
            for(char k='1'; k<='9'; k++){
                board[i][j]=k;
                if(isValid(board, i, j) && helper(board)){
                    return true;
                }
                board[i][j]='.';
            }
 
            return false;
        }
    }
 
    return true; //return true if all cells are checked
}
 
private boolean isValid(char[][] board, int i, int j){
    HashSet<Character> set = new HashSet<>();
 
    for(int k=0; k<9; k++){
        if(set.contains(board[i][k])){
            return false;
        }
        if(board[i][k]!='.'){
            set.add(board[i][k]);
        }
 
    }
 
    set.clear();
 
    for(int k=0; k<9; k++){
        if(set.contains(board[k][j])){
            return false;
        }
        if(board[k][j]!='.'){
            set.add(board[k][j]);
        }
    }
 
    set.clear();
 
    int x=i/3 * 3;
    int y=j/3 * 3;
    for(int m=x; m<x+3; m++){
        for(int n=y; n<y+3; n++){
            if(set.contains(board[m][n])){
                return false;
            }
            if(board[m][n]!='.'){
                set.add(board[m][n]);
            }
        }
    }
 
    set.clear();
 
    return true;
}

Another Approach would be:

public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.add(board[j][i]))
                return false;
            int RowIndex = 3*(i/3);
            int ColIndex = 3*(i%3);
            if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                return false;
        }
    }
    return true;
}

For a block traversal, it goes the following way.

0,0, 0,1, 0,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

1,0, 1,1, 1,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

2,0, 2,1, 2,2; < --- 3 Horizontal Steps.

And so on…
But, the j iterates from 0 to 9.

But we need to stop after 3 horizontal steps, and go down 1 step vertical.

Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

So far, for a given block, you can traverse the whole block using just j.

But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

Similarly, to move to next block vertically, use / and multiply by 3 as explained above.

Hope this helps.