Binary Puzzle

You can readily use the Prolog code I posted to generate such puzzles.

For example, you can go about it as follows. First, let us define the following relation that yields the N-th solution of a given Prolog goal:

    call_nth(Goal_0, C) :-
       State = count(0,_),
       Goal_0,
       arg(1, State, C1),
       C2 #= C1+1,
       nb_setarg(1, State, C2),
       C = C2.

We can use this as a building block to determine whether a given puzzle is still well-defined in the sense that it only admits a single solution. If call_nth(Goal, 2) for a given Goal succeeds, then we know that there are at least 2 answers, which is what we want to avoid in this case.

So, I define single_solution/1 to be true iff there are not two solutions:

    single_solution(Rows) :-
            \+ ( binary_puzzle(Rows),
                   append(Rows, Vs),
                   call_nth(label(Vs), 2) ).

As a further building block, consider the definition of generalize_row/2, which relates a given roster with hints to a generalized version where at most one hint has been removed:

    generalize_row([], []).
    generalize_row([Row|Rows0], [Row|Rows]) :-
            generalize_row(Rows0, Rows).
    generalize_row([Row0|Rows], [Row|Rows]) :-
            generalize_element(Row0, Row).

    generalize_element([], []).
    generalize_element([I|Es], [_|Es]) :- integer(I).
    generalize_element([E|Es0], [E|Es]) :-
            generalize_element(Es0, Es).

For example, here are the various possible generalizations for a single row, obtained by removing at most a single hint in each case, and replacing it by a logical variable:

    ?- generalize_element([1,0,1], Ls).
    Ls = [_54540, 0, 1] ;
    Ls = [1, _54546, 1] ;
    Ls = [1, 0, _54552] ;
    Ls = [1, 0, 1].

Note how different generalizations are naturally obtained via backtracking.

With these building blacks, everything is in place to generate such puzzles, with code that could look as follows:

    generate_puzzle(N, Hints, Rows) :-
            length(Rows0, N),
            binary_puzzle(Rows0),
            append(Rows0, Vs),
            once(label(Vs)),
            Hints #= N^2 - R,
            length(Rs, R),
            foldl(remove_hints, Rs, Rows0, Rows).

    remove_hints(_, Rows0, Rows) :-
            generalize_row(Rows0, Rows),
            Rows0 \== Rows,
            single_solution(Rows).

This starts from a fully instantiated roster of size NxN, and then successively removes hints. It is a ternary relation, also yielding the number of hints that remain, and of course the list of rows that constitute the found puzzle.

Here is an example invocation for N=4:

    ?- generate_puzzle(4, H, Rows),
       maplist(portray_clause, Rows).

The first two answers are:

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [1, 1, 0, 0].
    H = 16,

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [_, 1, 0, 0].
    H = 15

In the first solution, all hints are still present, and in the second solution, exactly one hint was removed.

You can use the second argument to specify the number of hints you want for the final puzzle, which you can regard as setting a difficulty (lower makes it harder). For example, let us try to find solutions with only 10 (instead of 16 or 15) hints:

    ?- generate_puzzle(4, 10, Rows),
       maplist(portray_clause, Rows).

In that case, we find for example:

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

and also:

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

In the 10x10 puzzle I showed earlier, only 22 hints are present, making it classified as "very hard". Let us generate 10x10 puzzles that are easier by containing more hints. For example, let us generate a 10x10 puzzle with 30 hints via the query:

    ?- generate_puzzle(10, 30, Rows),
       maplist(portray_clause, Rows).

Within at most seconds, we get for example:

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

This should provide a nice basis for further experiments to automatically generate such puzzles. For example, as you can see, the puzzle has a certain shape to it, and you can generate different shapes more readily by choosing random elements for generalization, instead of going so systematically about it.