[LeetCode] 36. Valid Sudoku

36. Valid Sudoku

 

Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

 

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

 

I solved it a long way. I should have been smarter, but it worked anyway. Another way to optimize this code is using multiple maps.

 

 

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (!checkWidthNumber(board)){
            return false;
        }
        if (!checkHeightNumber(board)){
            return false;
        }
        if (!checkBoxNumber(board)){
            return false;
        }
        return true;
    }
    
    boolean isEmpty(char a){
        if (a == '.') {
            return true;
        } 
        return false;
    }
    
    boolean checkWidthNumber(char[][] board) {
        HashMap<Character, Boolean> map = new HashMap<>();
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (isEmpty(board[i][j])){
                    continue;
                } else {
                    if (map.get(board[i][j]) != null) {
                        return false;
                    } else {
                        map.put(board[i][j], true);
                    }
                }
            }
            map.clear();
        }
        return true;
    }
    
    boolean checkHeightNumber(char[][] board) {
        HashMap<Character, Boolean> map = new HashMap<>();
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (isEmpty(board[j][i])){
                    continue;
                } else {
                    if (map.get(board[j][i]) != null) {
                        return false;
                    } else {
                        map.put(board[j][i], true);
                    }
                }
            }
            map.clear();
        }
        return true;
    }
    
    boolean checkBoxNumber(char[][] board) {
        int[] first = new int[]{0,2};
        int[] middle = new int[]{3,5};
        int[] last = new int[]{6,8};
        if (
            checkBox(board, first, first) &&
            checkBox(board, middle, first) &&
            checkBox(board, last, first) &&
            checkBox(board, first, middle) &&
            checkBox(board, middle, middle) &&
            checkBox(board, last, middle) &&
            checkBox(board, first, last) &&
            checkBox(board, middle, last) &&
            checkBox(board, last, last) 
        ){
            return true;
        } else {
            return false;
        }
    }
    
    boolean checkBox(char[][] board, int[] widthBound, int[] heightBound) {
        HashMap<Character, Boolean> map = new HashMap<>();
        for (int i = widthBound[0]; i <= widthBound[1]; i++){
            for (int j = heightBound[0]; j <= heightBound[1]; j++){
                if (isEmpty(board[j][i])){
                    continue;
                } else {
                    if (map.get(board[j][i]) != null) {
                        return false;
                    } else {
                        map.put(board[j][i], true);
                    }
                }
            }
        }
        return true;
    }
}

 

Better Algorithm from LeetCode:

class Solution {
    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;
    }
}

This algorithm uses a Java Set feature that sends a false message if it already exists. Additionally, it uses Row and Column Index by diving them with 3. Since Each box can be just three, it uses that property to get the Box check as well. 

 

Following uses only one Set because it gives unique calculated values each time. It's smart, but it takes more time to compute. 

public boolean isValidSudoku(char[][] board) {
        Set<String> set = new HashSet<>();
        
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                char val = board[row][col];
                if (val != '.') {
                    int block = (row / 3 * 3) + (col / 3);
                    if (set.contains("r" + row + val) || 
                        set.contains("c" + col + val) ||
                        set.contains("b" + block + val))
                        return false;
                    else {
                        set.add("r" + row + val);
                        set.add("c" + col + val);
                        set.add("b" + block + val);
                    }   
                }
            }
        }
        
        return true;
    }

 

Fastest Algorithm:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int n = 9;
        
        int[] rows = new int[n];
        int[] cols = new int[n];
        int[] boxes = new int[n];

        
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (board[i][j] == '.') continue;
                
                int pos = board[i][j] - '1';
                int mask = 1 << pos;
                
                if ((rows[i] & mask) != 0)
                    return false;
                rows[i] |= mask;
                
                if ((cols[j] & mask) != 0)
                    return false;
                cols[j] |= mask;
                
                int boxI = (i / 3) * 3 + (j / 3);
                if ((boxes[boxI] & mask) != 0)
                    return false;
                boxes[boxI] |= mask;
            }
        }
        
        return true;
    }
}