I could go further and validate all nine ×ばつ3 blocks using just one statement, but that wouldcould be a bit too nasty, I thinkoverwhelming.
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)
I could go further and validate all nine ×ばつ3 blocks using just one statement, but that would be a bit too nasty, I think.
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
I could go further and validate all nine ×ばつ3 blocks using just one statement, but that could be a bit too overwhelming.
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)
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 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 blocks using just one statement, but that would be a bit too nasty, I think.
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