Created
July 15, 2012 02:18
-
-
Save feynmanliang/3114500 to your computer and use it in GitHub Desktop.
Sudoku Checker
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# SPECIFICATION: | |
# | |
# check_sudoku() determines whether its argument is a valid Sudoku | |
# grid. It can handle grids that are completely filled in, and also | |
# grids that hold some empty cells where the player has not yet | |
# written numbers. | |
# | |
# First, your code must do some sanity checking to make sure that its | |
# argument: | |
# | |
# - is a 9x9 list of lists | |
# | |
# - contains, in each of its 81 elements, a number in the range 0..9 | |
# | |
# If either of these properties does not hold, check_sudoku must | |
# return None. | |
# | |
# If the sanity checks pass, your code should return True if all of | |
# the following hold, and False otherwise: | |
# | |
# - each number in the range 1..9 occurs only once in each row | |
# | |
# - each number in the range 1..9 occurs only once in each column | |
# | |
# - each number the range 1..9 occurs only once in each of the nine | |
# 3x3 sub-grids, or "boxes", that make up the board | |
# | |
# This diagram (which depicts a valid Sudoku grid) illustrates how the | |
# grid is divided into sub-grids: | |
# | |
# 5 3 4 | 6 7 8 | 9 1 2 | |
# 6 7 2 | 1 9 5 | 3 4 8 | |
# 1 9 8 | 3 4 2 | 5 6 7 | |
# --------------------- | |
# 8 5 9 | 7 6 1 | 4 2 3 | |
# 4 2 6 | 8 5 3 | 7 9 1 | |
# 7 1 3 | 9 2 4 | 8 5 6 | |
# --------------------- | |
# 9 6 1 | 5 3 7 | 0 0 0 | |
# 2 8 7 | 4 1 9 | 0 0 0 | |
# 3 4 5 | 2 8 6 | 0 0 0 | |
# | |
# Please keep in mind that a valid grid (i.e., one for which your | |
# function returns True) may contain 0 multiple times in a row, | |
# column, or sub-grid. Here we are using 0 to represent an element of | |
# the Sudoku grid that the player has not yet filled in. | |
# check_sudoku should return None | |
ill_formed = [[5,3,4,6,7,8,9,1,2], | |
[6,7,2,1,9,5,3,4,8], | |
[1,9,8,3,4,2,5,6,7], | |
[8,5,9,7,6,1,4,2,3], | |
[4,2,6,8,5,3,7,9], # <--- | |
[7,1,3,9,2,4,8,5,6], | |
[9,6,1,5,3,7,2,8,4], | |
[2,8,7,4,1,9,6,3,5], | |
[3,4,5,2,8,6,1,7,9]] | |
# check_sudoku should return True | |
valid = [[5,3,4,6,7,8,9,1,2], | |
[6,7,2,1,9,5,3,4,8], | |
[1,9,8,3,4,2,5,6,7], | |
[8,5,9,7,6,1,4,2,3], | |
[4,2,6,8,5,3,7,9,1], | |
[7,1,3,9,2,4,8,5,6], | |
[9,6,1,5,3,7,2,8,4], | |
[2,8,7,4,1,9,6,3,5], | |
[3,4,5,2,8,6,1,7,9]] | |
# check_sudoku should return False | |
invalid = [[5,3,4,6,7,8,9,1,2], | |
[6,7,2,1,9,5,3,4,8], | |
[1,9,8,3,8,2,5,6,7], | |
[8,5,9,7,6,1,4,2,3], | |
[4,2,6,8,5,3,7,9,1], | |
[7,1,3,9,2,4,8,5,6], | |
[9,6,1,5,3,7,2,8,4], | |
[2,8,7,4,1,9,6,3,5], | |
[3,4,5,2,8,6,1,7,9]] | |
# check_sudoku should return True | |
easy = [[2,9,0,0,0,0,0,7,0], | |
[3,0,6,0,0,8,4,0,0], | |
[8,0,0,0,4,0,0,0,2], | |
[0,2,0,0,3,1,0,0,7], | |
[0,0,0,0,8,0,0,0,0], | |
[1,0,0,9,5,0,0,6,0], | |
[7,0,0,0,9,0,0,0,1], | |
[0,0,1,2,0,0,3,0,6], | |
[0,3,0,0,0,0,0,5,9]] | |
# check_sudoku should return True | |
hard = [[1,0,0,0,0,7,0,9,0], | |
[0,3,0,0,2,0,0,0,8], | |
[0,0,9,6,0,0,5,0,0], | |
[0,0,5,3,0,0,9,0,0], | |
[0,1,0,0,8,0,0,0,2], | |
[6,0,0,0,0,4,0,0,0], | |
[3,0,0,0,0,0,0,1,0], | |
[0,4,0,0,0,0,0,0,7], | |
[0,0,7,0,0,0,3,0,0]] | |
def check_sudoku(grid): | |
try: | |
if len(grid) != 9 or type(grid) != list: | |
return None | |
for row in grid: | |
if len(row) != 9 or type(row) != list: | |
return None | |
for cell in row: | |
if cell not in range(0,10) or type(cell) != int: | |
return None | |
except TypeError: | |
return None | |
rows = grid | |
columns = zip(*grid) | |
for check in (rows + columns): | |
counts = {} | |
for num in check: | |
if num != 0: | |
if num not in counts.keys(): | |
counts[num] = 1 | |
else: | |
counts[num] += 1 | |
for count in counts.itervalues(): | |
if count > 1: | |
return False | |
subgriddim = [(0,3),(3,6),(6,9)] | |
for row in subgriddim: | |
for column in subgriddim: | |
snums = [grid[i][j] for i in range(*row) for j in range(*column)] | |
print snums | |
counts = {} | |
for num in snums: | |
if num != 0: | |
if num not in counts.keys(): | |
counts[num] = 1 | |
else: | |
counts[num] += 1 | |
for count in counts.itervalues(): | |
if count > 1: | |
return False | |
return True | |
print check_sudoku(ill_formed) # --> None | |
print check_sudoku(valid) # --> True | |
print check_sudoku(invalid) # --> False | |
print check_sudoku(easy) # --> True | |
print check_sudoku(hard) # --> True |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment