The declarative programming language Prolog is a natural choice for solving such combinatorial tasks. Here is a Prolog formulation of the puzzle, using constra

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!