CS258 (sudoku checker)

gistfile1.py

valid_range = range(0, 10)

def check_list(l):
    return type(l) == list and len(l) == 9

def check_values(l):
    counts_ok = not any([l.count(e) - 1 for e in l if e != 0])
    ranges_ok = (len([e for e in l if e in valid_range]) == len(l))
    return counts_ok and ranges_ok

def check_sudoku(grid):
    ###Your code here.
    # check general structure
    if not check_list(grid):
        return None
    invalid = False
    # check rows
    for row in grid:
        if not check_list(row):
            return None
        if not check_values(row):
            invalid = True
    if invalid:
        return False
    # check columns
    rotated_grid = zip(*grid)
    for col in rotated_grid:
        if not check_values(col):
            return False
    # check squares
    for r in xrange(0, 9, 3):
        for c in xrange(0, 9, 3):
            square = [grid[r][c], grid[r][c + 1], grid[r][c + 2],
                      grid[r + 1][c], grid[r + 1][c + 1], grid[r + 1][c + 2],
                      grid[r + 2][c], grid[r + 2][c + 1], grid[r + 2][c + 2]]
            if not check_values(square):
                return False
    return True

from copy import deepcopy

def solve_sudoku (grid):
    ###Your code here.
    # check if we have a valid grid
    valid = check_sudoku(grid)
    if not valid:
        return valid
    # check if we have finished
    zr, zc = -1, -1
    for r in xrange(9):
        if grid[r].count(0):
            zc, zr = grid[r].index(0), r
            break
    if zr == -1:
        if not check_sudoku(grid):
            return False
        return grid
    # construct a set of values we can't use
    excluded = set(grid[zr])      # rows
    for r in xrange(9):           # columns
        excluded.add(grid[r][zc])
    for r in xrange(0, 9, 3):     #squares
        if r <= zr < r + 3:
            for c in xrange(0, 9, 3):
                if c <= zc < c + 3:
                    excluded.update([grid[r][c], grid[r][c + 1], grid[r][c + 2],
                                     grid[r + 1][c], grid[r + 1][c + 1], grid[r + 1][c + 2],
                                     grid[r + 2][c], grid[r + 2][c + 1], grid[r + 2][c + 2]])
                    break
            break
    # try new values
    for x in xrange(1, 10):
        #new_grid = deepcopy(grid)
        grid[zr][zc] = x
        new_grid = solve_sudoku(grid)
        if new_grid:
            return new_grid
        grid[zr][zc] = 0
    return False