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. (A completely empty board is a valid square).

The Idea: A board is valid if all the rows, columns, and squares contain no duplicate integers.

Complexity: O(n^2) time and O(n) space with n is the len(sqrt(board))

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        dim = len(board)
        if not board or dim == 0 or \
            len(board[0]) != dim:
            return False

        # rule 1: no duplicates in rows
        for row in board:
            row_elms = [elm for elm in row if elm != '.']
            if len(set(row_elms)) != len(row_elms):
                return False

        # rule 2: no duplicates in cols
        for i in range(dim):
            col_elms = [board[j][i] for j in range(dim) if board[j][i] != '.']
            if len(set(col_elms)) != len(col_elms):
                return False

        # rule 3: no duplicates in each square grid
        square = int(dim/3)
        for row_mult in range(square):
            for col_mult in range(square):
                square_elm = []
                for i in range(row_mult*square, (row_mult*square) + square):
                    for j in range(col_mult*square, (col_mult*square) + square):
                        if board[i][j] != '.':
                            square_elm.append(board[i][j])
                if len(set(square_elm)) != len(square_elm):
                    return False
        return True

Discussion

• If the board is not necessarily 9x9, and if we wanted to generalize this algorithm. Here are some of the changes that need to be made.

  • The board must be a perfect square. e.g. 0^2, 1^1, 2^2 ... , n^n

  • squarevariable should then become math.sqrt(dim)