"""
Codefights: Interview Prep - sudoku2.py
Written by cmdellinger

Implementation of an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable.
"""

def sudoku2(grid):
    ''' checks 9x9 matrix to see if its a valid puzzle '''
    def check(values = []):
        ''' checks list for no repeats and all in range 1-9 '''
        return len(set(values)) == len(values) and set(values).issubset(range(1,10))
    
    # check rows
    for row in grid:
        values = [int(value) for value in row if value.isdigit()]
        if check(values) == False:
            return False
    # check columns
    for column in xrange(9):
        values = [int(row[column]) for row in grid if row[column].isdigit()]
        if check(values) == False:
            return False
    # check blocks
    for block_row in xrange(0,9,3):
        for block_column in xrange(0,9,3):
            values = [grid[i][j] for i in xrange(block_row,block_row+3) for j in xrange(block_column,block_column+3)]
            values = [int(value) for value in values if value.isdigit()]
            if check(values) == False:
                return False
    return True

"""
-------
Problem
-------
Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.

Implement an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable.

Example:

* For

grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
        ['.', '.', '6', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '1', '.', '.', '.', '.', '.', '.'],
        ['.', '6', '7', '.', '.', '.', '.', '.', '9'],
        ['.', '.', '.', '.', '.', '.', '8', '1', '.'],
        ['.', '3', '.', '.', '.', '.', '.', '.', '6'],
        ['.', '.', '.', '.', '.', '7', '.', '.', '.'],
        ['.', '.', '.', '5', '.', '.', '.', '7', '.']]

the output should be:

    sudoku2(grid) = true;

* For

grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
        ['.', '.', '.', '.', '6', '.', '.', '.', '.'],
        ['7', '1', '.', '.', '7', '5', '.', '.', '.'],
        ['.', '7', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '8', '3', '.', '.', '.'],
        ['.', '.', '8', '.', '.', '7', '.', '6', '.'],
        ['.', '.', '.', '.', '.', '2', '.', '.', '.'],
        ['.', '1', '.', '2', '.', '.', '.', '.', '.'],
        ['.', '2', '.', '.', '3', '.', '.', '.', '.']]

the output should be:

    sudoku2(grid) = false.

    The given grid is not correct because there are two 1s in the second column. Each column, each row, and each 3 × 3 subgrid can only contain the numbers 1 through 9 one time.

Input/Output

* [time limit] 4000ms (py)
* [input] array.array.char grid

    A 9 × 9 array of characters, in which each character is either a digit from '1' to '9' or a period '.'.

* [output] boolean
    Return true if grid represents a valid Sudoku puzzle, otherwise return false.
"""

if __name__ == '__main__':
    print(__doc__)
