Prolog implementation of "Which answer in this list is the correct answer to this question?"

user_12125728 0
Viewed 63

I came across this post on Math Exchange, asking for the solution to the following logic puzzle:

Which answer in this list is the correct answer to this question?

  1. All of the below.
  2. None of the below.
  3. All of the above.
  4. One of the above.
  5. None of the above.
  6. None of the above.

I know that the answer is 5, but because I am trying to learn Prolog I'd like to find a way for Prolog to give me the answer. I tried to use the following knowledge base to encode the information given in the puzzle:

answer(1) :- answer(2),answer(3),answer(4),answer(5),answer(6).
answer(2) :- \+answer(3), \+answer(4), \+answer(5), \+answer(6).
answer(3) :- answer(1), answer(2).
answer(4) :- answer(1); answer(2); answer(3).
answer(5) :- \+answer(1), \+answer(2), \+answer(3), \+answer(4).
answer(6) :- \+answer(1), \+answer(2), \+answer(3), \+answer(4), \+answer(5).

However, when trying to evaluate

?- answer(X).

I run into a infinite recursion (which is to be expected when naively substituting the predicates).

  1. Is there a way to solve this specific puzzle with Prolog? 1
  2. More generally, how can I know ahead of time when a logic puzzle is well suited for Prolog?

1: Yes, I know Prolog is turing complete, so encoding the problem into a turing machine and iterating all the possible solutions (like is done in the first answer to the Math exchange post) is of course a possibility but I'm looking for the "canonical" way of solving this.

prolog logic
1 Answers

This feels like a good use of library(clpb) for defining and solving a direct solution using boolean variables:

:- use_module(library(clpb)).

solve(Answer) :- 
    Options = [A1, A2, A3, A4, A5, A6],
    sat(*([
        (A1 =:= (A2 * A3 * A4 * A5 * A6)),
        (A2 =:= (~A3 * ~A4 * ~A5 * ~A6)),
        (A3 =:= (A1 * A2)),
        (A4 =:= (card([1], [A1, A2, A3]))),
        (A5 =:= (~A1 * ~A2 * ~A3 * ~A4)),
        (A6 =:= ( ~A1 * ~A2 * ~A3 * ~A4 * ~A5))
    ])),
    labeling(Options),
    nth1(Answer, Options, 1).

Taking the options provided as variables A1 through A6, each of the individual expressions must hold, so they are made a conjunction with *(Exprs). Most of the options are as listed in the question, just converted to the CLP(B) forms. A4 uses the cardinality constraint, meaning "only one of" the listed options can be true. After running the options through labeling and picking out the answer from the options that is set to 1, the result is as expected:

?- solve(Answer).
Answer = 5 ;
false.
user_5114850
Related