prolog

Lock Challenge in Prolog


I just started learning prolog and I'm stuck trying to solve this puzzle :

Alt

I tried to add some rules like this example http://swish.swi-prolog.org/example/houses_puzzle.pl but I couldn't come up with a solution.

What I tried so far:

% Render the houses term as a nice table.
:- use_rendering(table,
         [header(h('N1', 'N2', 'N3'))]).
numbers(Hs) :-
    length(Hs, 1),
    member(h(6,8,2), Hs),
    member(h(6,1,4), Hs),
    member(h(2,0,6), Hs),
    member(h(7,3,8), Hs),
    member(h(7,8,0), Hs),
    correct_and_placed(6, 8, 2, Hs).

correct_and_place(A, B, C, R).

But I don't even know how to write a rule that can check if a number is correct and on the right place.


Solution

  • To the existing answers, I would like to add a version using CLP(FD) constraints.

    The two building blocks I shall use are num_correct/3 and num_well_placed/3.

    First, num_correct/3, relating two lists of integers to the number of common elements:

    num_correct(Vs, Ns, Num) :-
            foldl(num_correct_(Vs), Ns, 0, Num).
    
    num_correct_(Vs, Num, N0, N) :-
            foldl(eq_disjunction(Num), Vs, 0, Disjunction),
            Disjunction #<==> T,
            N #= N0 + T.
    
    eq_disjunction(N, V, D0, D0 #\/ (N #= V)).
    

    Sample query:

    ?- num_correct([1,2,3], [3,5], Num).
    Num = 1.
    

    As is characteristic for pure relations, this also works for much more general queries, for example:

    ?- num_correct([A], [B], Num).
    B#=A#<==>Num,
    Num in 0..1.
    

    Second, I use num_well_placed/3, which relates two lists of integers to the number of indices where corresponding elements are equal:

    num_well_placed(Vs, Ns, Num) :-
            maplist(num_well_placed_, Vs, Ns, Bs),
            sum(Bs, #=, Num).
    
    num_well_placed_(V, N, B) :- (V #= N) #<==> B.
    

    Again, a sample query and answer:

    ?- num_well_placed([8,3,4], [0,3,4], Num).
    Num = 2.
    

    The following predicate simply combines these two:

    num_correct_placed(Vs, Hs, C, P) :-
            num_correct(Vs, Hs, C),
            num_well_placed(Vs, Hs, P).
    

    Thus, the whole puzzle can be formulated as follows:

    lock(Vs) :-
            Vs = [_,_,_],
            Vs ins 0..9,
            num_correct_placed(Vs, [6,8,2], 1, 1),
            num_correct_placed(Vs, [6,1,4], 1, 0),
            num_correct_placed(Vs, [2,0,6], 2, 0),
            num_correct_placed(Vs, [7,3,8], 0, 0),
            num_correct_placed(Vs, [7,8,0], 1, 0).
    

    No search at all is required in this case:

    ?- lock(Vs).
    Vs = [0, 4, 2].
    

    Moreover, if I generalize away the last hint, i.e., if I write:

    lock(Vs) :-
            Vs = [_,_,_],
            Vs ins 0..9,
            num_correct_placed(Vs, [6,8,2], 1, 1),
            num_correct_placed(Vs, [6,1,4], 1, 0),
            num_correct_placed(Vs, [2,0,6], 2, 0),
            num_correct_placed(Vs, [7,3,8], 0, 0),
            * num_correct_placed(Vs, [7,8,0], 1, 0).
    

    then the unique solution can still be determined without search:

    ?- lock(Vs).
    Vs = [0, 4, 2].
    

    In fact, I can even also take away the penultimate hint:

    lock(Vs) :-
            Vs = [_,_,_],
            Vs ins 0..9,
            num_correct_placed(Vs, [6,8,2], 1, 1),
            num_correct_placed(Vs, [6,1,4], 1, 0),
            num_correct_placed(Vs, [2,0,6], 2, 0),
            * num_correct_placed(Vs, [7,3,8], 0, 0),
            * num_correct_placed(Vs, [7,8,0], 1, 0).
    

    and still the solution is unique, although I now have to use label/1 to find it:

    ?- lock(Vs), label(Vs).
    Vs = [0, 4, 2] ;
    false.