# 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))
```