Sudoku grid validator

I have coded a sudoku grid validator as a problem set from an online course.

My input to the validator is a list of lists, that represents a sudoku grid. For reference, below are examples of an ill-formed sudoku grid, an invalid one, and a valid one.

# check_sudoku should return None
ill_formed = [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9],  # <---
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

# check_sudoku should return True
valid = [[5,3,4,6,7,8,9,1,2],
         [6,7,2,1,9,5,3,4,8],
         [1,9,8,3,4,2,5,6,7],
         [8,5,9,7,6,1,4,2,3],
         [4,2,6,8,5,3,7,9,1],
         [7,1,3,9,2,4,8,5,6],
         [9,6,1,5,3,7,2,8,4],
         [2,8,7,4,1,9,6,3,5],
         [3,4,5,2,8,6,1,7,9]]

# check_sudoku should return False
invalid = [[5,3,4,6,7,8,9,1,2],
           [6,7,2,1,9,5,3,4,8],
           [1,9,8,3,8,2,5,6,7],
           [8,5,9,7,6,1,4,2,3],
           [4,2,6,8,5,3,7,9,1],
           [7,1,3,9,2,4,8,5,6],
           [9,6,1,5,3,7,2,8,4],
           [2,8,7,4,1,9,6,3,5],
           [3,4,5,2,8,6,1,7,9]]

My code for the validator is the following:

```
def check_sudoku(grid):
""" Gets a list of lists as input, and returns None for ill-formed
Sudoku grids, False for invalid ones, and True for valid.
"""
assert type(grid) == list

# First, we need to make sure that the grid is 9x9.
if len(grid) != 9:
return None
row_len = map(lambda x: len(x) == 9, grid)
if False in row_len:
return None

# next we need to make sure that the numbers are between 0 and 9
max_len = map(max, grid)
min_len = map(min, grid)
more_than_ten = filter(lambda x: x > 9, max_len)
less_than_zero = filter(lambda x: x 2:
three_times_three.append(first_one)
three_times_three.append(second

The solution is generally good.

The docstring is OK, but could be better if it more clearly stated the purpose of the function. Follow the PEP 257 conventions for formatting. Use the imperative rather than the indicative mood.

The comment blocks throughout the function are useful, but could be less verbose. For example, you can cut out filler words like "First, we need to …".

Instead of assert type(grid) == list, I would assert isinstance(grid, list) to state what you really require without being too strict about the type, since duck-typing is the norm in Python.

You used this to validate the row lengths:

row_len = map(lambda x: len(x) == 9, grid)
if False in row_len:
    return None

Here, as in many places throughout the function, you used x as dummy variable. x is vague, and has a connotation of being a floating-point number. Try to pick more helpful names, as in lambda row: len(row) == 9.

Throughout this exercise, the all() built-in function and generator expressions are your friend. These are ways to write compact Pythonic code that is in the spirit of functional programming without actually using map and lambda explicitly.

I don't think that this block is necessary:

# next we need to make sure that the numbers are between 0 and 9
max_len = map(max, grid)
min_len = map(min, grid)
more_than_ten  = filter(lambda x: x > 9, max_len)
less_than_zero = filter(lambda x: x < 0, min_len)
if len(more_than_ten) or len(less_than_zero):
    return False

Your strategy is to first ensure that the entire grid contains nothing but digits 1 to 9, then ensure that each set contains nine distinct members. It would be simpler and clearer to eliminate this block, then check whether each set is equal to set(range(1, 10)).

For example, to check each row…

DIGITS = set(range(1, 10))
    if not all(set(row) == DIGITS for row in grid):
        return False

Checking rows is easy; checking columns is slightly more challenging. Transposing the grid can easily be accomplished with a list comprehension.

Checking each 3×3 square is more challenging. You used one loop to build a bunch of lists of lists, then cleaned up the "ickiness" by flattening it. You could avoid the flattening step by using .extend() instead of .append().

But really, what you should be using is itertools.product().

>>> from pprint import pprint as pp
>>> from itertools import product
>>> THREES = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]
>>> pp(list(product(THREES, THREES)))
[((0, 1, 2), (0, 1, 2)),
 ((0, 1, 2), (3, 4, 5)),
 ((0, 1, 2), (6, 7, 8)),
 ((3, 4, 5), (0, 1, 2)),
 ((3, 4, 5), (3, 4, 5)),
 ((3, 4, 5), (6, 7, 8)),
 ((6, 7, 8), (0, 1, 2)),
 ((6, 7, 8), (3, 4, 5)),
 ((6, 7, 8), (6, 7, 8))]
>>> pp([
...     [(r, c) for r, c in product(row_block, col_block)]
...     for row_block, col_block in product(THREES, THREES)
... ])
[[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)],
 [(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)],
 [(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)],
 [(3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2)],
 [(3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)],
 [(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)],
 [(6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1), (8, 2)],
 [(6, 3), (6, 4), (6, 5), (7, 3), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)],
 [(6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8, 7), (8, 8)]]

I could go further and validate all nine 3×3 blocks using just one statement, but that could be a bit too overwhelming.

Suggested solution

from itertools import product

def check_sudoku(grid):
    """Validate a sudoku solution.

    Given a grid as a list of lists, return None if it is ill-formed,
    False if it is invalid, or True if it is a valid solution.
    """
    assert isinstance(grid, list)

    # Check that the grid is 9x9.
    if len(grid) != 9 or not all(len(row) == 9 for row in grid):
        return None

    DIGITS = set(range(1, 10))

    # Check that each number appears exactly once per row
    if not all(set(row) == DIGITS for row in grid):
        return False

    # Check that each number appears exactly once per column
    columns = [[row[c] for row in grid] for c in range(9)]
    if not all(set(col) == DIGITS for col in columns):
        return False

    # Check that each number appears exactly once per 3x3 grid
    THREES = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]
    for row_block, col_block in product(THREES, THREES):
        block = [grid[r][c] for r, c in product(row_block, col_block)]
        if set(block) != DIGITS:
            return False

    return True

Functional solution

Since you mentioned an interest in functional programming, I thought I should also present a more functional variant for your consideration.

```
from itertools import product

def check_sudoku(grid)

StackExchange Code Review Q#142923, answer score: 6