Sudoku solver/checker

sudoku_solve.py

def times(A, B):
    return [(i,j) for i in A for j in B]

dims = range(9)
subdims = ([0,1,2],[3,4,5],[6,7,8])
squares  = times(dims, dims)
unitlist = ([times(dims, [c]) for c in dims] +
            [times([r], dims) for r in dims] +
            [times(rs, cs) for rs in subdims for cs in subdims])
units = dict((s, [u for u in unitlist if s in u])
             for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

def copy(board):
    return map(lambda x: x[:], board)

def subgrid(i):
    return range(i/3*3, i/3*3+3)

def check_row(nums):
    ## each number should be between 0 and 9
    counts = [0 for i in range(10)]
    for num in nums:
        if num < 0 or num > 9:
            return False
        counts[num] += 1
        if num > 0 and counts[num] > 1: 
            return False
    return True

def get_constraints(grid, i, j):
    row = grid[i]
    col = [grid[k][j] for k in dims]
    cell = [grid[k][l] for k in subgrid(i) for l in subgrid(j)]
    if check_row(row) and check_row(col) and check_row(cell):
        if grid[i][j] > 0 and grid[i][j] < 10:
            return str(grid[i][j])
        else:
            return ''.join(map(lambda x: str(x), set(range(1, 10)) - set(row) - set(col) - set(cell)))

def check_sudoku(grid):
    if type(grid) is not list or len(grid) != 9: return
    for row in grid:
        if type(row) is not list or len(row) != 9: return
        for num in row:
            if type(num) is not int: return
    for i in range(9):
        for j in range(9):
            if get_constraints(grid, i, j) is None:
                return False
    return True

def assign(board, i, j, d):
    if d not in board[i][j]:
        return False
    board[i][j] = d
    updated = []
    for (i1,j1) in peers[i,j]:
        if d in board[i1][j1]:
            board[i1][j1] = board[i1][j1].replace(d, '')
            if len(board[i1][j1]) == 0:
                return False
            elif len(board[i1][j1]) == 1:
                updated.append((i1,j1,board[i1][j1]))
            # propagate
            for unit in units[i1,j1]:
                for d2 in '123456789':
                    d2places = [(i2,j2) for (i2,j2) in unit if d2 in board[i2][j2]]
                    if len(d2places) == 0:
                        return False
                    elif len(d2places) == 1:
                        i2,j2 = d2places[0]
                        updated.append((i2,j2,d2))
    for i1,j1,d1 in set(updated):
        if not assign(board, i1, j1, d1):
            return False
    return board

def assign_from(board):
    return [map(lambda x: int(x), row) for row in board]

def solve_partial(board):
    if board is False: return False
    # most constrained
    cell_lengths = [(len(board[c[0]][c[1]]), c) for c in squares]
    if all(lc[0] == 1 for lc in cell_lengths):
        return board
    least, (i, j) = min([lc for lc in cell_lengths if lc[0] > 1], key=lambda x: x[0])
    for d in board[i][j]:
        newboard = solve_partial(assign(copy(board), i, j, d))
        if newboard: return newboard # found partial solution
    return False

def solve_sudoku (grid):
    ###Your code here.
    grid_check = check_sudoku(grid)
    if grid_check == None or grid_check == False: return grid_check
    board = copy(grid)
    for i in range(9):
        for j in range(9): board[i][j] = get_constraints(grid, i, j)
    soln = solve_partial(board)
    if soln:
        grid = assign_from(soln)
        assert check_sudoku(grid) == True 
        assert sum(map(sum, grid)) == 405
        return grid
    else:
        return False