Which language could be

A vast array of interesting and commonly known logic puzzles can be elegantly and efficiently solved with Prolog and constraints. Some puzzles can be very directly modeled and solved as combinatorial tasks, others need more effort to find a suitable formulation as such tasks, and yet other puzzles require a search over different states. In the following, we consider a few example puzzles.

Using Prolog and its

- use
**0**(**false**) to denote a*knave* - use
**1**(**true**) to denote a*knight* - use one Boolean
*variable*for each inhabitant, its truth value representing whether the person is a knave or a knight.

A

?- sat(A=:=(~A + B)).This shows thatA = B, B = 1.

Translated to Boolean constraints, this corresponds to:

?- sat(A=:=(~A * B)).Thus, in this example, both A and B areA = B, B = 0.

Using CLP(B) constraints, we can use the Boolean expression

?- sat(A=:=card([1,2],[~A,~B])).A = 1, B = 0.

We can translate these two statements to a

?- sat(A=:=(~A * ~B * ~C)), sat(B=:=card([1],[A,B,C])).A = C, C = 0, B = 1.

We can translate this to Prolog as follows:

?- sat(A=:= ~B), sat(B=:=(A=:=C)).This shows that C is definitely aC = 0, sat(A=\=B).

- All of the below.
- None of the below.
- All of the above.
- At least one of the above.
- None of the above.
- None of the above.

Again, we can trivially translate this puzzle to statements over

solution([A1,A2,A3,A4,A5,A6]) :- sat(A1 =:= A2*A3*A4*A5*A6), sat(A2 =:= ~(A2+A3+A4+A5+A6)), sat(A3 =:= A1*A2), sat(A4 =:= card([1,2,3],[A1,A2,A3])), sat(A5 =:= ~(A1+A2+A3+A4)), sat(A6 =:= ~(A1+A2+A3+A4+A5)).In this formulation, we are again assuming that your Prolog system ships with a dedicated constraint solver over Boolean domains that implements

The following interaction shows that only a single answer (option

?- solution(Vs).The Prolog system hasVs = [0, 0, 0, 0, 1, 0].

In many of these puzzles, your job is to string together all given statements so that they form a chain of implications, arriving at an often surprising or amusing result. For example:

- None of the unnoticed things, met with at sea, are mermaids.
- Things entered in the log, as met with at sea, are sure to be worth remembering.
- I have never met with anything worth remembering, when on a voyage.
- Things met with at sea, that are noticed, are sure to be recorded in the log.

Once more, we can translate each of these statements to a formula of

N | it is noticed |

M | it is a mermaid |

L | it is entered in the log |

R | it is worth remembering |

I | I have seen it |

Using these abbreviations, we can model the puzzle as follows:

sea([N,M,L,R,I]) :- sat(M =< N), % statement 1 sat(L =< R), % statement 2 sat(I =< ~R), % statement 3 sat(N =< L). % statement 4It only remains to find a chain of implications that links all statements or their negations:

implication_chain([], Prev) --> [Prev]. implication_chain(Vs0, Prev) --> [Prev], { select(V, Vs0, Vs) }, ( { taut(Prev =< V, 1) } -> implication_chain(Vs, V) ; { taut(Prev =< ~V, 1) } -> implication_chain(Vs, ~V) ).Sample query:

?- sea(Vs), Vs = [N,M,L,R,I], select(Start, Vs, Rest), phrase(implication_chain(Rest, Start), Cs).In this case, the two solutions for

Such deductions also frequently arise or are needed when applying Prolog for theorem proving.

An example of a cryptoarithmetic puzzle is:

CP + IS + FUN -------- = TRUEDifferent letters correspond to different digits.

Integer constraints are a great fit for such puzzles. Let us first define the

digits_number(Ds, N) :- length(Ds, _), Ds ins 0..9, reverse(Ds, RDs), foldl(pow, RDs, 0-0, N-_). pow(D, N0-I0, N-I) :- N #= N0 + D*10^I0, I #= I0 + 1.Using

?- digits_number([C,P], CP), digits_number([I,S], IS), digits_number([F,U,N], FUN), digits_number([T,R,U,E], TRUE), CP + IS + FUN #= TRUE, Vs = [C,P,I,S,F,U,N,T,R,E], all_distinct(Vs), label(Vs).The first solution is: 12+83+579=674. On backtracking,

Let us consider the following variant of this famous group of puzzles:

- The Englishman lives in the red house.
- The Spaniard owns the dog.
- Coffee is drunk in the green house.
- The Ukrainian drinks tea.
- From your perspective, the green house is immediately to
the
*right*of the ivory house. - The Old Gold smoker owns snails.
- Kools are smoked in the yellow house.
- Milk is drunk in the middle house.
- The Norwegian lives in the first house.
- The man who smokes Chesterfields lives in the house next to the man with the fox.
- Kools are smoked in the house next to the house where the horse is kept.
- The Lucky Strike smoker drinks orange juice.
- The Japanese smokes Parliaments.
- The Norwegian lives next to the blue house.

Such puzzles can be very conveniently solved by first translating the entities to

abs(H-N) #= 1This relation works correctly in

Thus, let us consider the following Prolog formulation of the task:

solution(Pairs, Water, Zebra, Vs) :- Table = [Houses,Nations,Drinks,Smokes,Animals], Houses = [Red,Green,Yellow,Blue,Ivory], Nations = [England,Spain,Ukraine,Norway,Japan], Names = [england,spain,ukraine,norway,japan], Drinks = [Coffee,Milk,OrangeJuice,Tea,Water], Smokes = [OldGold,Kools,Chesterfield,LuckyStrike,Parliaments], Animals = [Dog,Snails,Horse,Fox,Zebra], pairs_keys_values(Pairs, Nations, Names), maplist(all_distinct, Table), append(Table, Vs), Vs ins 1..5, England #= Red, % hint 1 Spain #= Dog, % hint 2 Coffee #= Green, % hint 3 Ukraine #= Tea, % hint 4 Green #= Ivory + 1, % hint 5 OldGold #= Snails, % hint 6 Kools #= Yellow, % hint 7 Milk #= 3, % hint 8 Norway #= 1, % hint 9 next_to(Chesterfield, Fox), % hint 10 next_to(Kools, Horse), % hint 11 LuckyStrike #= OrangeJuice, % hint 12 Japan #= Parliaments, % hint 13 next_to(Norway, Blue). % hint 14 next_to(H, N) :- abs(H-N) #= 1.Using labeling, we obtain the puzzle's unique solution:

?- solution(Pairs, Water, Zebra, Vs), label(Vs).Dozens of questions on Stackoverflow are about solving this famous puzzle or closely related ones with Prolog. You can thus read the existing questions and answers for more information.Pairs = [3-england, 4-spain, 2-ukraine, 1-norway, 5-japan], Water = 1, Zebra = 5,Vs = [3, 5, 1, 2, 4, 3, 4, 2, 1|...] ; false.

See