Solving a Logic Puzzle with Clingo
Wednesday, 26th August, 2020
I am working through the exercises in Vladimir Lifschitz’ Answer Set Programming (Springer, 2019). Section 3.2 shows a clingo encoding of one of those logic problems:
Each of four men owns a different species of exotic pet. Here is what we know about them:
…
We would like to find the full name of the person who owns the jackal.
I thought I would try and encode a similar puzzle from a magazine — a puzzle found in the wild! Logic Problems from Puzzler Media is my favourite and this puzzle was from the May issue (No. 429):
The code:
%%%% Boys in the Hood %%%% The world. episode(1..5). victim(friar_tuck; little_john; maid_marian; much; will_scarlet). location(inn; dungeon; lodge; gaol; stocks). disguise(abbot; shepherd; phantom; prince_john; washerwoman). %% For each Episode, there is one (V,L,D) combination, %% and the four variables together make a story. { story(E, V, L, D) : victim(V), location(L), disguise(D) } = 1 :- episode(E). %% Each victim, location and disguise appears in one episode only. E1 = E2 :- story(E1, V, _, _), story(E2, V, _, _). E1 = E2 :- story(E1, _, L, _), story(E2, _, L, _). E1 = E2 :- story(E1, _, _, D), story(E2, _, _, D). %%%% Clue 1 %% "Prince John" rescued a victim from the dungeon, ... D = prince_john :- story(_, _, dungeon, D). %% ... this was in the next episode after Little John's appearance. E2 = E1 + 1 :- story(E1, little_john, _, _), story(E2, _, dungeon, _). %%%% Clue 2 %% Friar Tuck was rescued from the inn. L = inn :- story(_, friar_tuck, L, _). %%%% Clue 3 %% The "washerwoman" appeared in episode 2. D = washerwoman :- story(2, _, _, D). %%%% Clue 4 %% Much the miller's son appeared in a later episode than the "abbot", ... E1 < E2 :- story(E1, _, _, abbot), story(E2, much, _, _). %% ... but an earlier episode than the rescue from the lodge. E1 < E2 :- story(E1, much, _, _), story(E2, _, lodge, _). %%%% Clue 5 %% The "phantom horseman" rescued Will Scarlet, ... V = will_scarlet :- story(_, V, _, phantom). %% ... in a later episode than the rescue from the gaol. E1 < E2 :- story(E1, _, gaol, _), story(E2, will_scarlet, _, _). %%%% Clue 6 %% The rescue from the stocks was in episode 3, ... L = stocks :- story(3, _, L, _). %% ... and did not feature Will Scarlet. :- story(3, will_scarlet, _, _). %%%% Clue 7 %% The "shepherd" was the rescuer in the episode before Maid Marian's. E2 = E1 + 1 :- story(E1, _, _, shepherd), story(E2, maid_marian, _, _). %% Maid Marian was not the victim in episode 2. :- story(2, maid_marian, _, _). #show story/4.
(… and in a gist.)
After describing the four sets, the first constraint involves a set comprehension, or "choice rule" in ASP parlance:
{ story(E, V, L, D) : victim(V), location(L), disguise(D) } = 1 :- episode(E).
The form { p(X, Y) : q(X), r(Y) }
describes a set — the set of facts p(X, Y)
where q(X), r(Y)
is true.
The form { ... } = n
asserts that the cardinality of the set described is n
.
Perhaps betraying my Prolog background, I initially tried to write things like (for Clue 2) …
story(_, friar_tuck, inn, _).
… which wouldn’t compile (unsafe anonymous variables), or …
story(E, friar_tuck, inn, D) :- episode(E), disguise(D).
… which didn’t work. Thinking of the clues as constraints rather than facts or predicates was the breakthrough, and the correct (or, at least, working) version, is concise and elegant:
L = inn :- story(_, friar_tuck, L, _).
A fun little exercise on "real world" but still relatively tame data. Recommended!
To any Answer Set Programming experts reading: how could this program be improved?
Saturday, 11th March, 2023 at 3:08 am
Good afternoon. If you no longer want number 429 of Puzzler logic problems books would you be willing to sell it to me?
I love these magazines, when I can find them, and would be happy to pay postage.
Janette Bohan
Saturday, 11th March, 2023 at 10:32 pm
Hello! Thank you for your comment. It is an excellent magazine. I’m afraid I no longer have this issue (429 was two years ago). The Puzzler website has some samples and a subscription form: https://www.puzzler.com/magazines/logic/logic-problems.