wayetan
12/31/2013 - 9:32 AM

Valid Sudoku

Valid Sudoku

/**
 * The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
 */
 
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        // invalid board;
        if(board.length != board[0].length || board.length != 9 || board[0].length != 9)
            return false;
        Map<Character, Boolean> row = new HashMap<Character, Boolean>();
        Map<Character, Boolean> col = new HashMap<Character, Boolean>();
        Map<Character, Boolean> block = new HashMap<Character, Boolean>();
        for(int i = 0; i < 9; i++){
            row.clear();
            col.clear();
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    // check column; 
                    if(col.containsKey(board[i][j]))
                        return false;
                    else
                        col.put(board[i][j], true);
                }
                if(board[j][i] != '.'){
                    // check row
                    if(row.containsKey(board[j][i]))
                        return false;
                    else
                        row.put(board[j][i], true);
                }
            }
        }
        //check block;
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                block.clear();
                for(int a = i; a < i + 3; a++){
                    for(int b = j; b < j + 3; b++){
                        if(board[a][b] != '.'){
                             if(block.containsKey(board[a][b]))
                                return false;
                            else
                                block.put(board[a][b], true);
                        }
                    }
                }
            }
        }
        return true;
    }
    
    public boolean isValidSudoku(char[][] board) {

       boolean[][] row = new boolean[9][9];
       boolean[][] column = new boolean[9][9];
       boolean[][] block = new boolean[9][9];

       for(int i = 0;i<9;i++){
           for(int j=0;j<9;j++){
                int c = board[i][j] - '1';       
                if(board[i][j]=='.'){
                    continue;
                }
                if(row[i][c]||column[j][c]||block[i - i % 3 + j / 3][c]){
                    return false;
                }
                row[i][c] = column[j][c] = block[i - i % 3 + j / 3][c] = true;
           }
       }
       return true;
    }
}