A logic puzzle called "Prize Box" from the ASCM problem solving competition:
Three boxes, 3 signs: Only one box has the prize; n is odd if and only if two signs are true. Sign A says "n is even and box 1 has the prize." Sign B says "n + 4 is a multiple of 3 or box 3 has the prize." Sign C says "n is odd or box 2 has the prize." Given that n is a single digit positive integer where every digit is equally likely, which box most often has the prize?
Obviously with a little thought, we can come up with a solution to this problem. However, there's a way to come up with the solution without thinking at all. That is, if we know a little Prolog.
All we have to do is describe the problem appropriately and let Prolog find feasible solutions.
First, a few simple predicates.
even(N) :- 0 is N mod 2.
odd(N) :- 1 is N mod 2.
Since the signs involve parity, writing some parity predicates will make our program clean.
Let's also define some predicates of what each piece of data looks like.
is_sign(S) :- member(S, [a, b, c]).
digit(N) :- between(1, 9, N).
box(X) :- between(1, 3, X).
Next, we should define the statements written on the signs.
sign(a, N, X) :- even(N), X = 1.
sign(b, N, X) :- 0 is (N + 4) mod 3 ; X = 3.
sign(c, N, X) :- odd(N) ; X = 2.
Our sign(S, N, X) predicate takes a sign name S,
our number N, and the prize box X.
Now, this represents just a single sign being true.
We're going to have multiple signs so we need a
signs(SS, N, X) predicate with a list of true
signs SS.
signs(SS, N, X) :-
digit(N),
box(X),
setof(S, (is_sign(S), sign(S, N, X)), SS).
Here we're saying that every member of SS is a
valid sign and that it's true by asserting the
sign predicate.
Now, we need to incorporate the rule about how many signs are true and the parity of our number.
soln(SS, N, X) :-
signs(SS, N, X),
length(SS, L),
((odd(N), L >= 2) ; (even(N), L < 2)).
So, now we can check the feasibility of any particular scenario. Now, we just count what box has the prize for every number.
?- setof(X-SS, soln(SS, N, X), L).
N = 1,
L = [3-[b, c]] ;
N = 2,
L = [3-[b]] ;
N = 3,
L = [3-[b, c]] ;
N = 4,
L = [1-[a], 2-[c], 3-[b]] ;
N = 5,
L = [1-[b, c], 2-[b, c], 3-[b, c]] ;
N = 6,
L = [1-[a], 2-[c], 3-[b]] ;
N = 7,
L = [3-[b, c]] ;
N = 8,
L = [3-[b]] ;
N = 9,
L = [3-[b, c]].
Notice, that for N = 1, 2, 3, 7, 8, 9 the only box that could possibly have the prize is 3. For N = 4, 5, 6 any of the boxes could have the prize.
Hence, our answer is box 3. We have avoided the rather tedious argument that follows.
When n is either 2 or 8, then sign B is true because n + 4 is a multiple of 3. Also, because n is even, two signs must be false, thus signs A and C are false. To make A false the prize is not in Box 1; to make C false the prize is not in Box 2. Thus in these two cases, Box 3 has the prize.
When n is 1, 3, 7, or 9, then because n is odd, sign A is false, but also thee other two signs must be true by the stated requirement. Because n + 4 is not a multiple of 3 in any of these cases, the only way to make sign B true is to have the prize in Box 3.
When n is 4, 5, or 6, the location of the prize is not uniquely determined. However, this is of no concern as we have already determined that the prize is in Box 3 at least six out of the nine cases.