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.
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) :
  disguise(D) } = 1 :-

%% 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) :
  disguise(D) } = 1 :-

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) :-

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

That Giant’s Causeway puzzle in Prolog

Tuesday, 13th January, 2015

Chris Lamb published a very nice blog post the other day showing a wooden logic puzzle he’d found, and implementing a solver in Python.

It was such a nice post I thought I’d write one in Prolog. Here it is (and in a gist):

% hex tiles puzzle
% -
% -

:- use_module(library(clpfd)).  %% for all_different/1

%% tile(Name, Colours).

% tiles from picture
% tile(11, [red, blue, black, yellow, green, white]).
% tile(22, [white, black, yellow, green, blue, red]).
% tile(33, [green, blue, black, yellow, red, white]).
% tile(44, [white, black, red, green, blue, yellow]).
% tile(55, [white, blue, green, yellow, black, red]).
% tile(66, [white, yellow, red, blue, black, green]).
% tile(77, [red, yellow, green, black, blue, white]).

% re-jigged a bit
tile(11, [white, black, red, green, blue, yellow]).
tile(22, [white, black, yellow, green, blue, red]).
tile(33, [white, blue, green, yellow, black, red]).
tile(44, [white, green, blue, black, yellow, red]).
tile(55, [white, red, blue, black, yellow, green]).
tile(66, [white, red, yellow, green, black, blue]).
tile(77, [white, yellow, red, blue, black, green]).

%% only six rotations allowed


%% rotate(List1, NStepsAntiClockwise, List2). 

rotate(Cs, 0, Cs).
rotate([A,B,C,D,E,F], 1, [B,C,D,E,F,A]).
rotate([A,B,C,D,E,F], 2, [C,D,E,F,A,B]).
rotate([A,B,C,D,E,F], 3, [D,E,F,A,B,C]).
rotate([A,B,C,D,E,F], 4, [E,F,A,B,C,D]).
rotate([A,B,C,D,E,F], 5, [F,A,B,C,D,E]).

%% colour(Name, Rotation, Position, Colour).

colour(N, R, P, C):-
    tile(N, Cs),
    X is (P + R) mod 6,
    nth0(X, Cs, C).

same_colour(N1, R1, P1, N2, R2, P2):-
    colour(N1, R1, P1, C),
    colour(N2, R2, P2, C).

solve(N1, R1, N2, R2, N3, R3, N4, R4, N5, R5, N6, R6, N7, R7):-
    all_different([N1, N2, N3, N4, N5, N6, N7]),

    same_colour(N1, R1, 3, N2, R2, 0),
    same_colour(N1, R1, 4, N4, R4, 1),
    same_colour(N1, R1, 5, N3, R3, 2),
    same_colour(N2, R2, 4, N5, R5, 1),
    same_colour(N2, R2, 5, N4, R4, 2),
    same_colour(N3, R3, 3, N4, R4, 0),
    same_colour(N3, R3, 4, N6, R6, 1),
    same_colour(N4, R4, 3, N5, R5, 0),
    same_colour(N4, R4, 4, N7, R7, 1),
    same_colour(N4, R4, 5, N6, R6, 2),
    same_colour(N5, R5, 5, N7, R7, 2),
    same_colour(N6, R6, 3, N7, R7, 0).

show(N, R):-
    tile(N, Cs),
    rotate(Cs, R, Rs),
    format(&quot;~d    ~w~n&quot;, [N, Rs]).

    solve(N1, R1, N2, R2, N3, R3, N4, R4, N5, R5, N6, R6, N7, R7),
    show(N1, R1),
    show(N2, R2),
    show(N3, R3),
    show(N4, R4),
    show(N5, R5),
    show(N6, R6),
    show(N7, R7).

Sergii Dymchenko recently posted a blog showing how a “greater than” sudoku can be solved with constraint logic programming and ECLiPSe CLP.

Sergii’s post inspired me to do the same for answer setprogramming, with clasp/gringo. I’ve uploaded the code to github.

Brief notes on ASP (& Sudoku)

I am just getting started with answer set prolog. Here are some first impressions:

Syntactically, it is very similar to Good Old Fashioned Prolog, with one or two additions. For example:

syntactic sugar

There’s a lot of sugar enabling concise code. e.g.,


expands to


headless predicates

A predicate without a head is known as a constraint. The sense is that the specified conjunction is not true.

:- paint(R, C1, N), paint(R, C2, N), C1 != C2.

In the sudoku code, paint/3 is a fact signifying that a cell at Row and Column has Number. The constraint above states that in a given row, a number can be at most one column.

multi-headed predicates

There seem to be various kinds of multi-headed predicates, with accompanying sugar for concise representation. A common construct is

1 { paint(R, C, P) : number(P) } 1 :- square(R, C).

The part of the head inside brackets is like a set comprehension and expands to

paint(R, C, 1) | paint(R, C, 2) | ... | paint(R, C, 8) | paint(R, C, 9).

Having this kind of disjunction in the head gives a kind of indeterminism: this disjunction is true if the body of the predicate is true.

The numbers to either side of the brackets put lower and upper bounds on the number of facts that this disjunction can introduce. So, in plain English, this predicate says something like “every square should be given exactly one number”.


Semantically there is a difference too. We understand an answer set prolog program as representing a set of states of affairs, where a state of affairs is a set of true facts (i.e., including no facts of the form ‘not P’).

Things like how many states of affairs, and which facts from each state of affairs, are reported to the user are dealt with by declarations (like #show in the sudoku script) and command line arguments.

In practice, this means that instead of passing round a data structure between predicates (e.g., a list of lists for a sudoku grid), statements inside predicates can be made which directly affect the database (i.e., the state of affairs) — e.g., the paint/3 statements scattered about sudoku.lp.

Describing it just now, that sounds scarily like global variables.

Extras for “Greater Than”

As a “Greater Than” Sudoku is just an ordinary sudoku with an extra constraint, I’ve put the required extra predicate lessEqual/4 in a separate script, sudoku_extra_gt.lp

The question grid is just the set of facts that we have initially. With standard sudoku, it’s the cell that have been given numbers, e.g., puzzle_easy.lp:

paint(1, 1, 7).
paint(1, 3, 3).
paint(1, 5, 8).
paint(1, 8, 1).
paint(2, 5, 6).
paint(3, 1, 6).
% ...

QUESTION FOR ASP EXPERTS: at first I tried “positive” constraints with a greaterThan/4 predicate, like this

% ...

but these seemed to be ignored in the answer set. Why? How should I have phrased it?

Running the solver on this Greater Than sudoku shows the paint predicates which are true given all the constraints:

$ clingo 0 puzzle_gt.lp sudoku.lp sudoku_extra_gt.lp
clingo version 4.4.0
Reading from puzzle_gt.lp ...
Answer: 1
paint(8,1,1) paint(2,2,1) paint(6,3,1) paint(5,4,1) paint(9,5,1) paint(3,6,1)
paint(4,7,1) paint(7,8,1) paint(1,9,1) paint(3,1,2) paint(6,2,2) paint(8,3,2)
paint(2,4,2) paint(4,5,2) paint(7,6,2) paint(1,7,2) paint(5,8,2) paint(9,9,2)
paint(6,1,3) paint(1,2,3) paint(7,3,3) paint(4,4,3) paint(2,5,3) paint(8,6,3)
paint(9,7,3) paint(3,8,3) paint(5,9,3) paint(5,1,4) paint(7,2,4) paint(1,3,4)
paint(3,4,4) paint(6,5,4) paint(9,6,4) paint(8,7,4) paint(4,8,4) paint(2,9,4)
paint(9,1,5) paint(4,2,5) paint(2,3,5) paint(7,4,5) paint(3,5,5) paint(5,6,5)
paint(6,7,5) paint(1,8,5) paint(8,9,5) paint(4,1,6) paint(8,2,6) paint(3,3,6)
paint(9,4,6) paint(1,5,6) paint(6,6,6) paint(5,7,6) paint(2,8,6) paint(7,9,6)
paint(7,1,7) paint(3,2,7) paint(4,3,7) paint(8,4,7) paint(5,5,7) paint(1,6,7)
paint(2,7,7) paint(9,8,7) paint(6,9,7) paint(1,1,8) paint(5,2,8) paint(9,3,8)
paint(6,4,8) paint(7,5,8) paint(2,6,8) paint(3,7,8) paint(8,8,8) paint(4,9,8)
paint(2,1,9) paint(9,2,9) paint(5,3,9) paint(1,4,9) paint(8,5,9) paint(4,6,9)
paint(7,7,9) paint(6,8,9) paint(3,9,9)

Models : 1
Calls : 1
Time : 20.837s (Solving: 17.59s 1st Model: 17.45s Unsat: 0.14s)
CPU Time : 20.836s

Dependent Types in Prolog

Wednesday, 7th May, 2014

or, “Had we but world enough, and time …”

** intro

I’ve been occasionally looking into programming languages with dependent types, when a recent tweet gave me pause:


I got interested in dependent types because SO TOLD ME TO^W^W^W^W they seemed necessary to encode some constraints on types for some toy projects I was thinking of, namely:

  • for a Bayesian network: represent probabilities (positive floating point number less than or equal to 1.0) and discrete probability distributions (a {T, Probability} mapping where the sum of probabilities = 1.0);
  • for fast Fourier transformation: respresent a list whose length must be a power of 2.

Naively, I thought I might be able to do this kind of thing in Haskell. I don’t like the cult hype around Idris. I thought I might try it with ATS, which I like the look of a lot, but it’s proving slow getting into.

** prolog

In the meantime, here are the types represented in Prolog:

% some "dependent" types

%%%% X is a power of 2

    Y is X / 2,

%%%% X is a list whose length is a power of 2

    length(X, L),

%%%% X is a probability

    X >= 0,
    X =< 1.

%%%% X is a discrete probability distribution

    maplist(prob, Y),
    sum_list(Y, 1.0).

%%%% helpers

seconds([], []).
seconds([[_, Y] | Z], [Y | Z2]):-
    seconds(Z, Z2).

tuplist([[_X, _Y] | Z]):-

** next


I might yet try this with ATS.

On the other hand, I might try it with Mercury, which seems to be (among other things perhaps) a typed Prolog.

** p.s.

In case the above is a bit downbeat on ATS: I do think ATS is a very interesting language. If any reader can give a quick sketch of one of the simpler types above in ATS, I am definitely up for having a go at the others.