This type of puzzles can be solved using reified
constraints, i.e., constraints over variables that are restricted to a
domain of 0 and 1, expressing logical values. Special propagators for
reified constraints which express the usual connectives like
disjunction etc. are available.


The Zebra Puzzle 
From the Oz Primer Five men with different nationalities live in the first five houses of the street. There are only houses on one side of the street. The men practice different professions, and each of them has a favorite drink and a favorite animal, all of them different. The five houses are painted in different colours. The following facts are known:
Who lives where? 

Who's "ploemp"? 
From the Zeit Magazine "Who's ploemp and who isn't?" asks the soolic Typher, while palampling nervously at his lopperdumpy. "I've explained it to you a hundred times already", replies the Heltzpusine cooly, "but because you can quotsh so beautifully in the slicksy hulk, I'clarofy it once more". The Heltzpusine spoke then: "If the Arpus is ploemp and at the same time neither the Flutz nor the Gnutz, then the Ol'Jauze isn't ploemp. If of the brothers Gnutz and Arpus at least one is ploemp, then the dumb Blondo is ploemp, but not the Hockerprotz. If the Flutz is ploemp, then the dumb Blondo is, too, but to the contrary, the Drulf not. If the Drulf isn't ploemp, then the Ol'Jauze is, surely; but the Gnutz is not ploemp if the Ol'Jauze is. If the Ebradulp is ploemp, then inevitably the Drulf is ploemp. And if the Arpus is not ploemp, then the Drulf cannot be. If the Ol'Jauze is ploemp, then so the Hockerprotz! Additionally, if the Ebradulp isn't ploemp, so on the one side, the Ol'Jauze isn't ploemp, but then the Gnutz is." The soolic Typer was quite impressed by this sermon. Close to tears, he thanked the Heltzpusine with the words: "Loveloy Heltzpusine! There's nothing like a clear, unpretentious explanation. I'll never forget again who's ploemp and who isn't" 

The birthday 
modified from a prolog lecture by Espen Vestre, summer 1993
Zorgon met Nuq the other day. "Wok's TwinTwins have birthday tomorrow", he said. "And Wok invented four presents for them, but can't decide who's getting what. He made a screaming sack, a rolling rock, an idiot incinerator and a some useless underwear. But he told me that at least he knew
"You should change your sources", said Zorgon. "They are obviously lying". What are the TwinTwins getting if Wok is actually telling the truth? And what's wrong with the information that Wok is a consequent liar? 

Abians and Bebians 
From the Zeit Magazine, 28/1996 A while ago, I was visitor at the knusic minister president. He introduced me to the other guests, seven members of the knusic parliament. He told me: "Every one of these lords of parliament is either an Abian or a Bebian, but who comes from which tribe, you'll have to find out for yourself" Like everyone should know nowadays, Abians always tell the truth, while any assertion stated by a Bebian is wrong. So I asked the delegates about their tribal ties. NoseKnosi: "If NeseKnesi is Bebian, then either NayKnasi or NoyKnosi is Abian". NeseKnesi: "If NoseKnosi is one of the Abians, then NoyKnosi is Bebian, being the case that NiseKnisi is Abian". NiseKnisi: "NuseKnusi is from the same tribe as NayKnasi". NoseKnosi: "If NoyKnosi is Bebian, then NaseKnasi is Abian". NuseKnusi: "I am Abian, but NoseKnosi is Bebian: NayKnasi: ĻIf NuseKnusi is Bebian, so NoseKnosi Abian" NoyKnose: "Either NaseKnasi or NayKnasi is Abian" The minister, who was an Abian (by the way), was very amused by the interviews he had witnessed and remarked: "You can deduce precisely who is Abian and who is Bebian from what they said". 

Kalotan males and females 
found by Dorai Sitaram (dorai@cs.rice.edu) Kalotan males always tell the truth. Kalotan females never make two consecutive true or untrue statements (i.e., they lie and tell the truth in strict alteration). An anthropologist who doesn't know Kalotan meets a Kalotan (heterosexual) couple and their child Kibi. He asks Kibi: "Are you a boy?". Kibi answers in Kalotan, which the anthropologist does not get. The anthropologist turns to the parents for explanation. One of them says: "Kibi said, 'I am a boy'". The other adds: "Kibi is a girl. Kibi lied." Solve for the sex of the parents (i.e., which parent made which statement) and Kibi. 