def solve(board):
    '''
    Solves a Takuzu board, with None for empty (unsolved) spaces
    '''
    assert len(set(map(len, board))) == 1  # all row lengths are the same
    assert len(board) == len(board[0])     # width and height are the same
    assert len(board) % 2 == 0             # board has even dimensions

    line_sum = len(board) / 2  # the number to which all rows and columns sum
    line = range(len(board))   # line and row indices

    solver = pywrapcp.Solver('takuzu')

    grid = {}
    for i in line:
        for j in line:
            grid[(i, j)] = solver.IntVar(0, 1, 'grid %i %i' % (i, j))

    # initial values
    for i in line:
        for j in line:
            if board[i][j] is not None:
                solver.Add(grid[(i, j)] == board[i][j])

    # no three consecutive elements in rows or columns
    for i in line:
        for j in range(len(board) - 2):
            solver.Add(solver.SumGreaterOrEqual([grid[(i, jl)]
                        for jl in line[j:j + 3]], 1))
            solver.Add(solver.SumLessOrEqual([grid[(i, jl)]
                        for jl in line[j:j + 3]], 2))
            solver.Add(solver.SumGreaterOrEqual([grid[(jl, i)]
                        for jl in line[j:j + 3]], 1))
            solver.Add(solver.SumLessOrEqual([grid[(jl, i)]
                        for jl in line[j:j + 3]], 2))

    # rows and columns sum to half the size
    for i in line:
        solver.Add(solver.SumEquality([grid[(i, j)] for j in line], line_sum))

    for j in line:
        solver.Add(solver.SumEquality([grid[(i, j)] for i in line], line_sum))

    # regroup all variables into a list
    all_vars = [grid[(i, j)] for i in line for j in line]

    # create search phases
    vars_phase = solver.Phase(all_vars,
                              solver.INT_VAR_SIMPLE,
                              solver.INT_VALUE_SIMPLE)

    # search for all solutions and remove those with duplicate rows or columns
    solver.NewSearch(vars_phase)

    solutions = []

    while solver.NextSolution():
        solutions.append([[int(grid[(i, j)].Value()) for j in line]
                          for i in line])

    solver.EndSearch()

    solutions = filter(valid, solutions)

    assert len(solutions) == 1  # there should be only one solution

    return solutions[0]

    Solves a Takuzu board, with None for empty (unsolved) spaces
    
recipes/Python/578414_Takuzu_solver/recipe-578414.py