[LeetCode] 36. Valid Sudoku

</br>

---

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'

A partially filled sudoku which is valid.

Note:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

---

</br>

Solution

To determine whether a Sudoku is valid, we have to check every columns, every rows, every sub-block of the Sudoku only contains non-repeated number, that is to say, number from 0 to 9 only appears once.

To achieve this requirement, we can build a function to check isSubValid() to check whether certain part of the Sudoku has replicate number.

To check whether there is repeating numbers, we can use the features of Java HashSet, as HashSet cannot contain replicate numbers. When we try to add a number to the HashSet, if the set does not contain the target, then the add() function will return true. However, when there already exists the same number, the add() function will return false to indicate the replicate number.

In this way, for any columns, rows or blocks of Sudoku, we can implement this method to check whether this region has replicate number.
</br>
One more thing to make the code concise, instead of using another for-loop, we can use only one variable to represent all 9 blocks. We assign 9 blocks like following.

1  2  3
4  5  6
7  8  9

And in the first block, contains another 9 numbers,

[0][0]  [0][1]  [0][2]
[1][0]  [1][1]  [1][2]
[2][0]  [2][1]  [2][2]

By implementing

column_s    column_e    int row_s    int row_e
(i%3)*3     (i%3)*3+2   (i/3)*3      (i/3)*3+2)

we can iterate every elements in the block using just one variable i.
</br>
The code is shown as below.
Java

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        for(int i=0;i<9;i++){
        //Vertical
            if(!isSubValid(board,i,i,0,8))
                return false;
        //Horizontal
            if(!isSubValid(board,0,8,i,i))
                return false;
        //Block
            if(!isSubValid(board,(i%3)*3,(i%3)*3+2,(i/3)*3,(i/3)*3+2))
                return false;
        }
        return true;
    }
    
    private boolean isSubValid(char[][] board, int column_s, int column_e, int row_s, int row_e){
        Set set = new HashSet();
        int i = column_s;
        
        while(i<=column_e){
            int j = row_s;
            while(j<=row_e){
                if(board[i][j] != '.')
                    if(set.add(board[i][j]) == false)
                        return false;
                j++;
            }
            i++;
        }
        return true;
    }
}

</br>