HackySudoku.py

# The subgrid of grid starting at x,y
def sub_grid(grid,x,y):
    res = []
    rows = grid[y:y+3]
    for i in range(len(rows)):
        res += rows[i][x:x+3]
    return res

# i'th column of grid
def col(grid,i):
    res = []
    for j in range(len(grid)):
        res += [grid[j][i]]
    return res

# Returns whether row is free of duplicates (not counting 0s)
def valid_row(row):
    for i in range(1,10):
        count = 0
        for j in range(len(row)):
            if row[j] == i:
                count += 1
        if count > 1:
            return False
    return True

# Returns whether grid is a 9x9 list of in-range integers
def sane(grid):
    if not isinstance(grid, list):
        return False
    if len(grid) != 9:
        return False
    for i in range(len(grid)):
        l = grid[i]
        if not isinstance(l, list):
            return False
        if len(l) != 9:
            return False
        for j in range(len(l)):
            x=l[j]
            if not isinstance(x, int):
                return False
            if x < 0 or x > 9:
                return False
    return True

# Return None if grid is crazy, False if invalid, True if valid
def check_sudoku(grid):
    if not sane(grid):
        return None
    lists = []
    # Lazy hack: Write out all the starting indices for subgrids. Who needs loops?
    xs = [0,3,6,0,3,6,0,3,6]
    ys = [0,0,0,3,3,3,6,6,6]
    for i in range(len(xs)):
        lists += [sub_grid(grid,xs[i], ys[i])]
    for i in range(len(xs)):
        lists += [grid[i]]
    for i in range(len(ys)):
        lists += [col(grid,i)]
    return all (map (valid_row, lists))

def copy (grid):
    map (lambda x: x[:], grid)

# Recursively return None if grid is insane, False if no soln, Or soln if it exists
def solve_sudoku (grid):
    check = check_sudoku(grid)

    # Crazy or clearly no solution? We're done
    if not check:
        return check

    x,y = None, None
    # Find a place to make a move
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 0:
                x,y = i,j

    # No moves left, and wasn't invalid, so it was done!
    if x is None:
        return grid

    # Make all possible moves there
    for i in range(1,10):
        g = copy(grid)
        g[x][y] = i
        res = solve_sudoku(g)
        if res:
            return res

    # Was sane, but no move led to a solution
    return False