# 36 Valid Sudoku

Determine if a Sudoku is valid, according to:[Sudoku Puzzles - The Rules](http://sudoku.com.au/TheRules.aspx).

The Sudoku board could be partially filled, where empty cells are filled with the character`'.'`.

![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)

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))

```python
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`
  * `square`variable should then become `math.sqrt(dim)`