Skip to content

Instantly share code, notes, and snippets.

@boyarsky
Created July 12, 2012 23:22
Show Gist options
  • Save boyarsky/3101789 to your computer and use it in GitHub Desktop.
Save boyarsky/3101789 to your computer and use it in GitHub Desktop.
Boyarsky - Python cs 358
# 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 nine_by_nine(grid):
if not grid:
return False
if len(grid) != 9:
return False
for row in grid:
if len(row) != 9:
return False
return True
def all_digits(grid):
for row in grid:
for cell in row:
try:
int_value = int(cell)
if int_value < 0 or int_value > 9 or int_value != cell:
return False
except:
return False
return True
# checks no duplicates from 1 to 9 (duplicate 0's are ok)
def check_no_dups(nineGrouping):
uniqueDigits = set()
for num in nineGrouping:
if num != 0:
if num in uniqueDigits:
return False
uniqueDigits.add(num)
return True
def check_row(grid, row):
nineGrouping = []
for cell in grid[row]:
nineGrouping.append(cell)
return check_no_dups(nineGrouping)
def check_column(grid, column):
nineGrouping = []
for row in grid:
nineGrouping.append(row[column])
return check_no_dups(nineGrouping)
def check_subgrid(grid, row, column):
nineGrouping = []
for i in range(row, row + 3):
for j in range(column, column + 3):
nineGrouping.append(grid[i][j])
return check_no_dups(nineGrouping)
def check_sudoku(grid):
if not nine_by_nine(grid) or not all_digits(grid):
return None
for i in range(0, 9):
if not check_row(grid, i):
return False
if not check_column(grid, i):
return False
for i in range(0, 7, 3):
for j in range(0, 7, 3):
if not check_subgrid(grid, i, j):
return False
return True
pass
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
@heretoinfinity
Copy link

Please clarify for me. What's the use of int_value != cell: on line 118? A string and an int can't be the same. If the cast weren't possible an error would have been produced on previous line 117 with int_value = int(cell).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment