Llaisdy

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?