Binary Puzzle
The declarative programming language Prolog is a natural choice for solving such combinatorial tasks.<p>Here is a Prolog formulation of the puzzle, using constraint logic programming over <i>integers</i> that ships with typical Prolog systems:<p><pre><code>    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 &#x2F;&#x2F; 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 ) #==&gt; ( C #\= B ),
            ( B #= C ) #==&gt; ( B #\= A ),
            only_two_next_to_each_other([B,C|Rest]).
</code></pre>
For example, let us consider the concrete 10x10 puzzle of today:<p><pre><code>    puzzle([[_,_,_,_,_,1,_,_,_,1],
            [1,_,_,_,_,_,_,0,_,_],
            [_,_,0,_,_,_,_,0,_,_],
            [_,0,0,_,_,_,0,_,_,1],
            [1,_,_,_,_,_,_,_,_,1],
            [_,_,_,0,_,_,1,_,_,_],
            [0,_,_,_,_,1,_,_,_,_],
            [_,_,_,_,_,_,_,0,_,0],
            [0,_,_,_,_,_,_,_,_,0],
            [_,0,_,0,_,1,_,_,_,_]]).
</code></pre>
You can solve it with the above formulation, using for example SICStus Prolog and its CLP(FD) library, with the following query:<p><pre><code>    ?- puzzle(Rows),
       binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).
</code></pre>
The unique solution is:<p><pre><code>    [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].
</code></pre>
It is found within a second on current machines.<p>The above formulation is also quite general. For example, you can use it to <i>complete</i>, <i>test</i> and <i>generate</i> solutions:<p><pre><code>    ?- binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).
</code></pre>
This <i>generates</i> valid solutions of the puzzle for all board sizes:<p><pre><code>    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.

</code></pre>
Thank you for sharing!