Binary Puzzle

Oh Hi (https://play.google.com/store/apps/details?id=com.presto.ohh...) is an app I have that has these puzzles.

Simple rules and can get surprisingly difficult.

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!

I wonder how one creates puzzles like this (or indeed creates Sudoku puzzles). I can think of a few strategies

1. Lovingly hand craft them. Extremely labour intensive!

2. Generate random grids and repeatedly remove elements. If that leads to a puzzle with more than one solution, backtrack.

3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop.

Finally, classify the difficulty using some heuristic.

Does anyone have a better strategy? Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver?

What's the difference between your app (that has 100-500 downloads) and this app that has 100,000-500,000 downloads?

https://play.google.com/store/apps/details?id=com.q42.ohhi&h...

Also, the list of puzzles on the site goes to March 2011.

I think this is a nice case of taking something interesting and making it more approachable, perhaps even fun.