2
\$\begingroup\$

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 < 0, min_len)
    if len(more_than_ten) or len(less_than_zero):
        return False

    # now we need to make sure that each number is present only one time in a row
    one_per_row = map(lambda x: len(set(x)) == 9, grid)
    if False in one_per_row:
        return False

    # and next up is making sure that each number is present only one time in a column
    # to do that, we want to follow the previous procedure, but for it to be valid, we
    # shall first need to turn each column into a line
    columns_to_lines = []
    for i in range(0, 9):
        column = []
        for z in range(0, 9):
            column.append(grid[i][z])
        columns_to_lines.append(column)
    one_per_column = map(lambda x: len(set(x)) == 9, columns_to_lines)
    if False in one_per_column:
        return False

    # for the last check, we need to ensure that each number is unique in the 3x3 grids
    # we can do this by creating a single 9 list element out of the 3x3 grid, and perform
    # the same procedure as above.
    three_times_three = []
    first_one   = []
    second_one  = []
    third_one   = []
    times_break = 0
    for i in range(0, 9):
        first_one.append(grid[i][0:3])
        second_one.append(grid[i][3:6])
        third_one.append(grid[i][6:9])
        times_break += 1
        if times_break > 2:
            three_times_three.append(first_one)
            three_times_three.append(second_one)
            three_times_three.append(third_one)
            first_one  = []
            second_one = []
            third_one  = []
            times_break = 0

    # collapse the lists because they now contain sublists, making it
    # slightly icky for the rest of the pipeline
    three_times_three = map(lambda l: sum(l, []), three_times_three)
    one_per_three_box = map(lambda x: len(set(x)) == 9, three_times_three)
    if False in one_per_three_box:
        return False

    return True

I wrote it all in functional style - that's what you get after a whole summer full of Scheme. My question is, is this considered high quality readable code? Would you consider it hard to read instead? If so why? What could you do better?

\$\endgroup\$
  • \$\begingroup\$ This might be of interest. \$\endgroup\$ – 409_Conflict Oct 1 '16 at 7:57
6
\$\begingroup\$

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):
    """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))
    THREES = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]

    def correct(groups):
        return all(set(group) == DIGITS for group in groups)

    rows = grid
    columns = zip(*grid)
    squares3x3 = [
        [grid[r][c] for r, c in product(row_block, col_block)]
        for row_block, col_block in product(THREES, THREES)
    ]

    return correct(rows) and correct(columns) and correct(squares3x3)
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. This is exactly the kind of feedback that I was looking for when I came here. I feel bad for only being able to award you with 1 thumbs up and 1 accepted answer. I still have a question though. I can see that your provided code is times more idiomatic python, and it's also less code - something that's arguably better. However, I still feel like the map-filter pure functional version is cleaner to me - perhaps because I spent a lot of time working this way in lisp recently. Are python idioms to always be preferable over the map-filter implementation? \$\endgroup\$ – NlightNFotis Sep 30 '16 at 19:57
  • 1
    \$\begingroup\$ stackoverflow.com/a/1247490/1157100 \$\endgroup\$ – 200_success Sep 30 '16 at 20:03
  • \$\begingroup\$ @200_success Out of curiosity, what would be the "further" solution that can "validate all nine 3×3 blocks using just one statement?" \$\endgroup\$ – T145 Oct 31 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.