Skip to content

Instantly share code, notes, and snippets.

@lopespm
Last active May 6, 2019 17:40
Show Gist options
  • Save lopespm/70cb459eb79bf3ee11727e6cba0fc0bf to your computer and use it in GitHub Desktop.
Save lopespm/70cb459eb79bf3ee11727e6cba0fc0bf to your computer and use it in GitHub Desktop.
The Sudoku Check Problem - Alternative Solution (Python)
# Alternative python solution for 5.17 The Sudoku Check Problem on EPI (Elements of Programming Interviews)) (September 2018 edition)
# For an nxn Sudoku grid:
# Time complexity: O(n^2)
# Space complexity: O(n)
from typing import List
import math
from typing import List, Set
import math
def is_valid_sudoku(partial_assignment: List[List[int]]):
def duplicate_check(validation_set: Set[int], i: int, j: int):
number = partial_assignment[i][j]
if (number in validation_set):
return True
if (number != 0):
validation_set.add(number)
return False
n = len(partial_assignment)
r = int(math.sqrt(n))
for i in range(n):
row_numbers, col_numbers, block_numbers = set(), set(), set()
for j in range(n):
if (duplicate_check(row_numbers, i, j) or
duplicate_check(col_numbers, j, i) or
duplicate_check(block_numbers, (j // r) + r * (i % r), (j % r) + r * (i // r))):
return False
return True
# Some examples
s = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 6, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 8, 0, 0, 0, 0], [9, 0, 0, 0, 7, 5, 0, 0, 0], [0, 0, 0, 0, 5, 0, 0, 8, 0], [0, 0, 9, 0, 0, 0, 0, 0, 0], [2, 0, 6, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
print(is_valid_sudoku(s))
s = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [7, 0, 0, 5, 9, 8, 0, 2, 1], [0, 1, 0, 4, 0, 0, 9, 0, 3], [3, 0, 6, 7, 0, 0, 4, 0, 8], [8, 2, 0, 1, 5, 0, 0, 0, 0], [0, 0, 0, 0, 0, 3, 0, 0, 0], [0, 8, 4, 3, 0, 7, 0, 5, 0], [6, 9, 0, 0, 0, 0, 2, 0, 0], [1, 3, 0, 0, 0, 2, 8, 0, 7]]
print(is_valid_sudoku(s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment