Valid Sudoku

Problem: Valid Sudoku

A valid Sudoku doesn't have conflict in itself, which means we need to check whether each row, each col and each block has duplicate numbers. To do this, we establish hash table of each of them and iterate through the matrix to check. Note that in leetcode they use "." to denote empty element.

Code in Python:

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        rowCheck = [{} for _ in xrange(9)]
        colCheck = [{} for _ in xrange(9)]
        blockCheck = [[{} for _ in xrange(3)] for _ in xrange(3)]

        for i in xrange(9):
            for j in xrange(9):
                cur = board[i][j]
                if cur == '.':
                    continue
                block_i, block_j = i / 3, j / 3
                if cur in rowCheck[i] or cur in colCheck[j] or cur in blockCheck[block_i][block_j]:
                    return False
                rowCheck[i][cur], colCheck[j][cur], blockCheck[block_i][block_j][cur] = True, True, True
        return True

Code in Java:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Character, Boolean> check = new HashMap<Character, Boolean>();
        for (int i = 0; i < 9; i++) {
            check.clear();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if (check.get(board[i][j]) != null) return false;
                check.put(board[i][j], true);
            }
        }

        for (int i = 0; i < 9; i++) {
            check.clear();
            for (int j = 0; j < 9; j++) {
                if (board[j][i] == '.') continue;
                if (check.get(board[j][i]) != null) return false;
                check.put(board[j][i], true);
            }
        }

        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                check.clear();
                for (int m = 0; m < 3; m++) {
                    for (int n = 0; n < 3; n++) {
                        if (board[i+m][j+n] == '.') continue;
                        if (check.get(board[i+m][j+n]) != null) return false;
                        check.put(board[i+m][j+n], true);
                    }
                }
            }
        }

        return true;
    }
}

We can also use an array of boolean rather than hash tables to check the sudoku, like the solution here