Sudoku Solver/Checker - Udacity CS258

sudoku.py

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)

test_sudoku.py

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