Verify If A Sudoku Board Is Correct
30 Jan 2021 - Hadron DaVinci
Problem
Given a 9x9 array, verify it meets the criteria of a Sudoku board.
A Sudoku board is valid when three criterion are met:
- Each row contains unique values from 1-9.
- Each column contains unique values from 1-9.
- Each of the 9 sub-squares, of size 3x3, contains a unique value from 1-9.
Example
Given
A = [
[8, 5, 3, 2, 9, 1, 7, 4, 6],
[9, 2, 7, 5, 6, 4, 1, 3, 8],
[1, 6, 4, 8, 7, 3, 5, 9, 2],
[2, 3, 9, 7, 5, 6, 8, 1, 4],
[6, 4, 5, 1, 8, 9, 2, 7, 3],
[7, 8, 1, 3, 4, 2, 6, 5, 9],
[3, 1, 8, 9, 2, 7, 4, 6, 5],
[5, 9, 6, 4, 1, 8, 3, 2, 7],
[4, 7, 2, 6, 3, 5, 9, 8, 1],
]
Then:
is_valid_sudoku(A) = True
Method
- Iterate through row
- verify numbers in row are valid
- Iterate through column
- verify numbers in column are valid
- Iterate through 3x3 chunks
- verify numbers in chunk are valid
Complexity
Given NxN matrix
TC: N
SC: N
Solution
from typing import Generator
def row_iterator(arr: list) -> Generator:
"""
Yields each row as a list
"""
for row in arr:
yield row
def column_iterator(arr: list) -> Generator:
"""
Yields each column as a list
"""
for column in zip(*arr):
yield column
def grid_iterator(arr: list, width=3, height=3) -> Generator:
"""
Yields each grid as a list
"""
column_count = len(arr[0])
row_count = len(arr)
for j in range(0, column_count, height):
for i in range(0, row_count, width):
grid = []
for sub_j in range(j, j + height):
grid.extend(arr[sub_j][i: i + width])
yield grid
def chunk_is_valid(chunk) -> bool:
"""
Verifies each chunk has 9 unique numbers
:param chunk: a group of numbers
"""
return len(set(chunk)) == 9
def sudoku_is_valid(arr: list):
# verify rows are valid
for row in row_iterator(arr):
if not chunk_is_valid(row):
return False
# verify columns are valid
for column in column_iterator(arr):
if not chunk_is_valid(column):
return False
# verify 3x3 grids are valid
for grid in grid_iterator(arr):
if not chunk_is_valid(grid):
return False
return True
# Try Code
if __name__ == "__main__":
A = [
[8, 5, 3, 2, 9, 1, 7, 4, 6],
[9, 2, 7, 5, 6, 4, 1, 3, 8],
[1, 6, 4, 8, 7, 3, 5, 9, 2],
[2, 3, 9, 7, 5, 6, 8, 1, 4],
[6, 4, 5, 1, 8, 9, 2, 7, 3],
[7, 8, 1, 3, 4, 2, 6, 5, 9],
[3, 1, 8, 9, 2, 7, 4, 6, 5],
[5, 9, 6, 4, 1, 8, 3, 2, 7],
[4, 7, 2, 6, 3, 5, 9, 8, 1],
]
if sudoku_is_valid(A):
print('Sudoku Is Valid')
else:
print('Sudoku Is Not Valid')