-
-
Save drewverlee/3820204 to your computer and use it in GitHub Desktop.
Sudoku Solver/Checker - Udacity CS258
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
def get_subgrids(three_rows): | |
""" splits given set of three rows into subgrids""" | |
return zip(*[(row[0:3], row[3:6], row[6:]) for row in three_rows]) | |
def check_sudoku(sudoku): | |
try: | |
def check_row(row): | |
""" checks that the row contains 1 and only 1 element from 1 to 9 and | |
that the total count == 9""" | |
counts = [0 for x in range(10)] | |
for i in range(9): | |
# this both checks that row is indexable by integers AND | |
# that every element in counts is integer-ish | |
counts[row[i]] += 1 | |
return all(count <= 1 for count in counts[1:]) and (sum(counts) == 9) | |
legal_numbers = frozenset([0,1,2,3,4,5,6,7,8,9]) | |
# sanity check | |
if not (len(sudoku) == 9 and | |
all((len(row) == 9 and | |
all(x in legal_numbers for x in row)) | |
for row in sudoku)): | |
return None | |
# zip(*sudoku) is the transpose of sudoku | |
rows_match = (all(check_row(row) for row in sudoku) | |
and all(check_row(row) for row in zip(*sudoku))) | |
if not rows_match: | |
return False | |
return all(check_row([elem for row in subgrid for elem in row]) for subgrids in | |
(get_subgrids(sudoku[0:3]), get_subgrids(sudoku[3:6]), get_subgrids(sudoku[6:])) | |
for subgrid in subgrids) | |
except (TypeError, AttributeError): | |
return None | |
def get_valid_options(row, legal_options=set(range(1, 10))): | |
""" returns all values that are in legal_options but not in row""" | |
return legal_options.difference(set(row)) | |
def check_completed(sudoku): | |
return sudoku and check_sudoku(sudoku) and all(elem for row in sudoku for elem in row) | |
class DefaultList(dict): | |
@classmethod | |
def create(cls, factory): | |
new_lst = cls() | |
new_lst.factory = factory | |
return new_lst | |
def __getitem__(self, n): | |
try: | |
return super(DefaultList, self).__getitem__(n) | |
except KeyError: | |
new_item = self.factory(n) | |
super(DefaultList, self).__setitem__(n, new_item) | |
return new_item | |
def do_solve(sudoku, solver, convert_to_int = True): | |
check = check_sudoku(sudoku) | |
if not check: | |
return check | |
if convert_to_int: | |
try: | |
sudoku = [[int(x) for x in row] for row in sudoku] | |
except (TypeError, ValueError): | |
return None | |
return solver(sudoku, get_valid_options) | |
def brute_force_sudoku(sudoku, get_valid_options): | |
# make sure it's a valid sudoku | |
sudoku_transpose = zip(*sudoku) | |
row_options = DefaultList.create(lambda i: get_valid_options(sudoku[i])) | |
col_options = DefaultList.create(lambda j: get_valid_options(sudoku_transpose[j])) | |
# subgrids are referenced first by top(0)/middle(1)/bottom(2) then by left(0), middle(1), right(2) | |
subgrid_options = [[get_valid_options([elem for row in subgrid for elem in row]) | |
for subgrid in subgrids] | |
for subgrids in (get_subgrids(sudoku[0:3]), get_subgrids(sudoku[3:6]), get_subgrids(sudoku[6:]))] | |
# check that every 0 spot can be filled with something AND fill in single_option spots | |
for i, j in [(i,j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]: | |
# get subgrid (0-2 means top, etc, so dividing by 3 gives pos'n) | |
sub_opts = subgrid_options[i//3][j//3] | |
# check that there is actually a possible option | |
row_opts = row_options[i] | |
col_opts = col_options[j] | |
options = row_opts & col_opts & sub_opts | |
if not options: | |
return None | |
elif len(options) == 1: | |
new_elem = tuple(options)[0] | |
# get rid of the element from all option sets | |
row_opts.remove(new_elem) | |
col_opts.remove(new_elem) | |
sub_opts.remove(new_elem) | |
sudoku[i][j] = new_elem | |
for i, j in [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]: | |
options = row_options[i] & col_options[j] and subgrid_options[i//3][j//3] | |
res = False | |
for opt in options: | |
res = brute_force_sudoku([[e if (_i,_j) != (i,j) else opt for _j, e in enumerate(row)] for _i, row in enumerate(sudoku)], get_valid_options) | |
if check_completed(res): | |
return res | |
else: | |
res = False | |
return res | |
return check_completed(sudoku) and sudoku or False | |
solve_sudoku = lambda sudoku : do_solve(sudoku, brute_force_sudoku) |
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
from nose.tools import eq_, nottest | |
from sudoku import solve_sudoku, check_sudoku, get_valid_options | |
LONG_TEST = False | |
# solve_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]] | |
# solve_sudoku should return valid unchanged | |
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]] | |
# solve_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]] | |
# solve_sudoku should return a | |
# sudoku grid which passes a | |
# sudoku checker. There may be | |
# multiple correct grids which | |
# can be made from this starting | |
# grid. | |
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]] | |
# Note: this may timeout | |
# in the Udacity IDE! Try running | |
# it locally if you'd like to test | |
# your solution with it. | |
# | |
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]] | |
@nottest | |
def test_successful(sudoku): | |
legal_numbers = set(range(1,10)) | |
assert sudoku, "Given test sudoku, {sudoku}, not truthy".format(sudoku=sudoku) | |
def check_successful(result): | |
assert result, """Solver returned {result} instead of valid sudoku for input:\n{sudoku}""".format(sudoku=sudoku, result=result) | |
check = check_sudoku(result) | |
assert check, """Solver returned invalid sudoku | |
(yielding `{check}` from check_sudoku) | |
instead of valid sudoku for | |
{sudoku}""".format(check=check, sudoku=sudoku) | |
for i, j, elem in [(i, j, elem) for i, row in enumerate(result) for j, elem in enumerate(row)]: | |
assert elem in legal_numbers, """Element ({i}, {j}) [{elem}] not in [1..9] in sudoku:\n {sudoku}""".format(i=i, j=j, elem=elem, sudoku=sudoku) | |
check_successful(solve_sudoku(sudoku)) | |
def test_get_valid_options(): | |
legal_options = set(range(1,10)) | |
legal_options2 = set(range(1,10)) | |
cases = [ | |
([0], set(range(1,10))), | |
([0, 0, 0, 0, 0, 0, 0, 0, 0], set(range(1,10))), | |
([1, 0, 0, 0, 0, 0, 0, 0, 0], set(range(2, 10))), | |
([1, 0, 0, 4, 0, 3, 2, 0, 0], set([5, 6, 7, 8, 9])), | |
# obviously the following is invalid, but we don't went get_valid_options | |
# to really be testing for that at all | |
([1, 2, 5, 6, 0, 8, 9, 1, 0], set([3, 4, 7])), | |
([0, 0, 9, 8, 7, 0, 0, 1, 0], set([2, 3, 4, 5, 6]))] | |
for inpt, expected in cases: | |
yield eq_, expected, get_valid_options(inpt, legal_options) | |
yield eq_, legal_options, legal_options2, "Legal options changed by get_valid_options :(" | |
illegal = [ill_formed] | |
not_valid = [invalid] | |
def test_check_sudoku(): | |
""" test check_sudoku for invalid input""" | |
for s in illegal: | |
yield eq_, None, check_sudoku(s) | |
for s in not_valid: | |
yield eq_, False, check_sudoku(s) | |
def test_check_sudoku_valid(): | |
""" test check_sudoku for valid input""" | |
valid = [easy, hard] | |
for s in valid: | |
yield eq_, True, check_sudoku(s) | |
def test_solve_sudoku_generator(): | |
""" test illegal and invalid sudokus""" | |
for s in illegal: | |
yield eq_, None, solve_sudoku(s) | |
for s in not_valid: | |
yield eq_, False, solve_sudoku(s) | |
def test_normal_sudokus(): | |
""" test normal sudokus""" | |
normal_success = [easy, valid] | |
long = [hard] | |
if LONG_TEST: | |
normal_success.extend(long) | |
for s in normal_success: | |
yield test_successful, s |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment