Wednesday, January 7, 2015

LeetCode 36: Valid Sudoku

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.
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board==null || board.length!=9 || board[0].length!=9)
            return false;
        
        // Row checker: Integer - 1 ~ 9; Set<Integer> - x coordinates    
        Map<Integer, Set<Integer>> rowChecker = new HashMap<>();
        
        // Column checker: Integer - 1 ~ 9; Set<Integer> - y coordinates 
        Map<Integer, Set<Integer>> colChecker = new HashMap<>();
        
        // Block checker: Integer - 1 ~ 9; Set<Integer> - block id 
        Map<Integer, Set<Integer>> blkChecker = new HashMap<>();
        
        // Allocate memory for 1 ~ 9
        for (int i = 1; i <= 9; i++)
        {
            Set<Integer> xc = new HashSet<>();
            rowChecker.put(i, xc);
            
            Set<Integer> yc = new HashSet<>();
            colChecker.put(i, yc);
            
            Set<Integer> blkId = new HashSet<>();
            blkChecker.put(i, blkId);
        }
        
        int bID = 0; // Block ID
        
        // Check validity by block
        for (int x = 0; x < 9; x = x+3)
            for (int y = 0; y < 9; y = y+3)
            {
                for (int i = x; i < x+3; i++)
                    for (int j = y; j < y+3; j++)
                    {
                        if (board[i][j] == '.')
                            continue;
                        
                        // Convert char to int    
                        int num = Character.getNumericValue(board[i][j]);
                        
                        if (rowChecker.get(num).contains(i))
                            return false;
                        else
                            rowChecker.get(num).add(i);
                            
                        if (colChecker.get(num).contains(j))
                            return false;
                        else
                            colChecker.get(num).add(j);
                            
                        if (blkChecker.get(num).contains(bID))
                            return false;
                        else
                            blkChecker.get(num).add(bID);
                    }
                
                bID++;    
            }
            
        return true;
    }
}

No comments:

Post a Comment