The declarative programming language Prolog is a natural choice for solving such combinatorial tasks.

Here is a Prolog formulation of the puzzle, using constraint logic programming over integers that ships with typical Prolog systems:

    binary_puzzle(Rows) :-
            length(Rows, L),
            maplist(same_length(Rows), Rows),
            maplist(only_two_next_to_each_other, Rows),
            transpose(Rows, Cols),
            maplist(only_two_next_to_each_other, Cols),
            maplist(booleans_integer, Rows, RIs),
            all_different(RIs),
            maplist(booleans_integer, Cols, CIs),
            all_different(CIs),
            Half #= L // 2,
            maplist(equally_distributed(Half), Rows),
            maplist(equally_distributed(Half), Cols).

    equally_distributed(L, Bs) :-
            global_cardinality(Bs, [0-L,1-L]).

    booleans_integer(Bs, I) :-
            foldl(pow, Bs, 0-0, I-_).

    pow(B, N0-I0, N-I) :-
            B in 0..1,
            N #= N0 + B*2^I0,
            I #= I0 + 1.

    only_two_next_to_each_other([]).
    only_two_next_to_each_other([_,_]).
    only_two_next_to_each_other([A,B,C|Rest]) :-
            ( A #= B ) #==> ( C #\= B ),
            ( B #= C ) #==> ( B #\= A ),
            only_two_next_to_each_other([B,C|Rest]).

For example, let us consider the concrete 10x10 puzzle of today:

    puzzle([[_,_,_,_,_,1,_,_,_,1],
            [1,_,_,_,_,_,_,0,_,_],
            [_,_,0,_,_,_,_,0,_,_],
            [_,0,0,_,_,_,0,_,_,1],
            [1,_,_,_,_,_,_,_,_,1],
            [_,_,_,0,_,_,1,_,_,_],
            [0,_,_,_,_,1,_,_,_,_],
            [_,_,_,_,_,_,_,0,_,0],
            [0,_,_,_,_,_,_,_,_,0],
            [_,0,_,0,_,1,_,_,_,_]]).

You can solve it with the above formulation, using for example SICStus Prolog and its CLP(FD) library, with the following query:

    ?- puzzle(Rows),
       binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).

The unique solution is:

    [0, 1, 0, 1, 0, 1, 0, 1, 0, 1].
    [1, 0, 1, 0, 0, 1, 1, 0, 1, 0].
    [0, 1, 0, 1, 1, 0, 1, 0, 1, 0].
    [1, 0, 0, 1, 1, 0, 0, 1, 0, 1].
    [1, 0, 1, 0, 0, 1, 0, 0, 1, 1].
    [0, 1, 1, 0, 1, 0, 1, 1, 0, 0].
    [0, 1, 0, 1, 0, 1, 0, 0, 1, 1].
    [1, 0, 1, 0, 1, 0, 1, 0, 1, 0].
    [0, 1, 0, 1, 1, 0, 1, 1, 0, 0].
    [1, 0, 1, 0, 0, 1, 0, 1, 0, 1].

It is found within a second on current machines.

The above formulation is also quite general. For example, you can use it to complete, test and generate solutions:

    ?- binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).

This generates valid solutions of the puzzle for all board sizes:

    Rows = [] ;
    [0, 1].
    [1, 0].
    Rows = [[0, 1], [1, 0]] ;
    [1, 0].
    [0, 1].
    Rows = [[1, 0], [0, 1]] ;
    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [1, 1, 0, 0].
    Rows = [[0, 0, 1, 1], [0, 1, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]] ;
    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 1, 0, 0].
    [1, 0, 1, 0].
    Rows = [[0, 0, 1, 1], [0, 1, 0, 1], [1, 1, 0, 0], [1, 0, 1, 0]] ;
    etc.

Thank you for sharing!