## 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?

This site uses Akismet to reduce spam. Learn how your comment data is processed.