validate sudoku

← 🏠

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Solution

In the graphs module, we'll learn how to write a Sudoku solver. For now, testing the validity of a Sudoku board is a good warm-up exercise.

Here's an example board:

 1board = [
 2[".",".","3","8",".",".","4",".","."],
 3[".",".",".",".","1",".",".","7","."],
 4[".","6",".",".",".","5",".",".","9"],
 5[".",".",".","9",".",".","6",".","."],
 6[".","2",".",".",".",".",".","1","."],
 7[".",".","4",".",".","3",".",".","2"],
 8[".",".","2",".",".",".","8",".","."],
 9[".","1",".",".",".",".",".","5","."],
10["9",".",".",".",".","7",".",".","3"]]

Validating a row

Validating a row is the easiest task. We simply need to filter out the unassigned cells, and check whether the size of the set of entries is the same as the size of the list of entries.

1def is_unique(A):
2  nums = [x for x in A if x != '.']
3  return len(nums) == len(set(nums))
4
5print(is_unique([".",".","3","8",".",".","4",".","."])) # True
6print(is_unique([".",".","3","8",".",".","4",".","3"])) # False

Validating all rows

Validating all rows is therefore only a matter of passing a generator expression to all.

1all(is_unique(board[i]) for i in range(9)) # True

Validating a column

Validating a column is a little trickier, since the column needs to be extracted from the board. Python does not have a built-in solution for column extraction in a matrix (unlike Numpy), so this has to be done using a list comprehension, or generator expression.

1print([board[row][0] for row in range(9)]) # ['.', '.', '5', '.', '4', '.', '.', '.', '.']

Now that we know how to extract a column, we can simply validate it.

1print(is_valid(board[row][0] for row in range(9)))

Validating all columns

Validating every column is simply a matter of nesting this statement in another generator expression, and passing it to all:

1all(is_unique(board[row][col] for row in range(9)) for col in range(9)) # True

Validating sections

Validating sections begins by:
- identifying the indices of the sub-matrices
- transforming those sub-matrices into lists
- validating those lists

Sub-matrix indices

These are the indices of the top left cell of each section.

1section_indices = lambda: [(i, j) for i in range(0,9,3) for j in range(0,9,3)]

Sub-matrix extraction

We can now extract a list from each section. We do so by performing a 3x3 nested loop from the starting indices of each section.

1section_as_list = lambda I, J: [board[I+i][J+j] for i in range(3) for j in range(3)]

We can finally validate our sub-matrices, with a call to all:

1all(is_unique(section_as_list(*section)) for section in section_indices())

Bringing it all together

Please note this is not the most efficient solution to this problem, however it's a good exercise at turning the rules of Sudoku into actionable steps that can be built up progressively.

 1def is_valid(board):
 2    def is_unique(A):
 3        nums = [x for x in A if x != '.']
 4        return len(nums) == len(set(nums))
 5    
 6    section_indices = lambda: [(i, j) for i in range(0,9,3) for j in range(0,9,3)]
 7    section_as_list = lambda I, J: [board[I+i][J+j] for i in range(3) for j in range(3)]
 8
 9    return  all(is_unique(board[i]) for i in range(9)) and \
10            all(is_unique([board[row][col] for row in range(9)]) for col in range(9)) and \
11            all(is_unique(section_as_list(*section)) for section in section_indices())
12
13print(is_valid(board))