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 Twin-Twins 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 Twin-Twins 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. Nose-Knosi: "If Nese-Knesi is Bebian, then either Nay-Knasi or Noy-Knosi is Abian". Nese-Knesi: "If Nose-Knosi is one of the Abians, then Noy-Knosi is Bebian, being the case that Nise-Knisi is Abian". Nise-Knisi: "Nuse-Knusi is from the same tribe as Nay-Knasi". Nose-Knosi: "If Noy-Knosi is Bebian, then Nase-Knasi is Abian". Nuse-Knusi: "I am Abian, but Nose-Knosi is Bebian: Nay-Knasi: ĻIf Nuse-Knusi is Bebian, so Nose-Knosi Abian" Noy-Knose: "Either Nase-Knasi or Nay-Knasi 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.
|