Udacity CS258 - Sudoku Solver

SudokuSolver.py

# Sudoku solver for Udacity CS258.

def get_groups():
    q = lambda f:[[f(i,j) for j in range(9)] for i in range(9)]
    return q(lambda i,j:(i,j)) + q(lambda i,j:(j,i)) + q(lambda i,j:(i/3*3+j/3,i%3*3+j%3))
    # I think this is more readable than the one-liner:
    # >> return [l for i in range(9) for l in zip(*[[(i,j),(j,i),(i/3*3+j/3,i%3*3+j%3)] for j in range(9)])]

def check_sudoku(grid):
# Check to see if grid is a list with 9 elements
    if ((not type(grid) is list) or (len(grid) != 9)): return None

    # Check to see if each row is a list with 9 elements
    for row in grid:
        if ((not type(row) is list) or (len(row) != 9)): return None

    if set(map(len,grid)) != set([9]): return None
    if min(map(min,grid)) < 0: return None
    if max(map(max,grid)) > 9: return None
    for s in get_groups():
        l = filter(None,[grid[i][j] for i,j in s])
        if len(l) != len(set(l)): return False
    return True


def solve_sudoku (grid):
    check = check_sudoku(grid)
    if not check: return check
    grid = [row[:] for row in grid]
    groups = get_groups()
    pairs = [[set(t for s in groups if (i,j) in s for t in s) for j in range(9)] for i in range(9)]
    def go(x,y):
        if y==9: return True
        if grid[y][x]: return go((x+1)%9,y+x/8)
        for o in set(range(1,10)) - set(grid[i][j] for (i,j) in pairs[y][x]):
            grid[y][x] = o
            if go((x+1)%9,y+x/8): return True
        grid[y][x] = 0
    return grid if go(0,0) else False

#print solve_sudoku(easy)