I have a lot in the works for the this month's Logic for Programmers release. Among other things, I'm completely rewriting the chapter on Logic Programming Languages.

I originally showcased the paradigm with puzzle solvers, like eight queens or four-coloring. Lots of other demos do this too! It takes creativity and insight for humans to solve them, so a program doing it feels magical. But I'm trying to write a book about practical techniques and I want everything I talk about to be useful. So in v0.9 I'll be replacing these examples with a couple of new programs that might get people thinking that Prolog could help them in their day-to-day work.

On the other hand, for a newsletter, showcasing a puzzle solver is pretty cool. And recently I stumbled into this post by my friend Pablo Meier, where he solves a videogame puzzle with Prolog:

Summary for the text-only readers: We have a test with 10 true/false questions (denoted a/b) and four student attempts. Given the scores of the first three students, we have to figure out the fourth student's score.

bbababbabb = 7
baaababaaa = 5
baaabbbaba = 3
bbaaabbaaa = ???

You can see Pablo's solution here, and try it in SWI-prolog here. Pretty cool! But after way too long studying Prolog just to write this dang book chapter, I wanted to see if I could do it more elegantly than him. Code and puzzle spoilers to follow.

(Normally here's where I'd link to a gentler introduction I wrote but I think this is my first time writing about Prolog online? Uh here's a Picat intro instead)

The Program

You can try this all online at SWISH or just jump to my final version here.

:- use_module(library(dif)).    % Sound inequality
:- use_module(library(clpfd)).  % Finite domain constraints

First some imports. dif lets us write dif(A, B), which is true if A and B are not equal. clpfd lets us write A #= B + 1 to say "A is 1 more than B".

We'll say both the student submission and the key will be lists, where each value is a or b. In Prolog, lowercase identifiers are atoms (like symbols in other languages) and identifiers that start with a capital are variables. Prolog finds values for variables that match equations (unification). The pattern matching is real real good.

% ?- means query
?- L = [a,B,c], [Y|X] = [1,2|L], B + 1 #= 7.

B = 6,
L = [a, 6, c],
X = [2, a, 6, c],
Y = 1

Next, we define score/3 ^recursively.

% The student's test score
% score(student answers, answer key, score)
score([], [], 0).
score([A|As], [A|Ks], N) :-
   N #= M + 1, score(As, Ks, M).
score([A|As], [K|Ks], N) :- 
    dif(A, K), score(As, Ks, N).

First key is the student's answers, second is the answer key, third is the final score. The base case is the empty test, which has score 0. Otherwise, we take the head values of each list and compare them. If they're the same, we add one to the score, otherwise we keep the same score.

Notice we couldn't write if x then y else z, we instead used pattern matching to effectively express (x && y) || (!x && z). Prolog does have a conditional operator, but it prevents backtracking so what's the point???

A quick break about bidirectionality

One of the coolest things about Prolog: all purely logical predicates are bidirectional. We can use score to check if our expected score is correct:

?- score([a, b, b], [b, b, b], 2).
true

But we can also give it answers and a key and ask it for the score:

?- score([a, b, b], [b, b, b], X).
X = 2

Or we could give it a key and a score and ask "what test answers would have this score?"

?- score(X, [b, b, b], 2).
X = [b, b, _A],
dif(_A,b)
X = [b, _A, b],
dif(_A,b)
X = [_A, b, b],
dif(_A,b)

The different value is written _A because we never told Prolog that the array can only contain a and b. We'll fix this later.

Okay back to the program

Now that we have a way of computing scores, we want to find a possible answer key that matches all of our observations, ie gives everybody the correct scores.

key(Key) :-
    % Figure it out
    score([b, b, a, b, a, b, b, a, b, b], Key, 7),
    score([b, a, a, a, b, a, b, a, a, a], Key, 5),
    score([b, a, a, a, b, b, b, a, b, a], Key, 3).

So far we haven't explicitly said that the Key length matches the student answer lengths. This is implicitly verified by score (both lists need to be empty at the same time) but it's a good idea to explicitly add length(Key, 10) as a clause of key/1. We should also explicitly say that every element of Key is either a or b. ^{Now we could write a second predicate saying Key had the right 'type':}

keytype([]).
keytype([K|Ks]) :- member(K, [a, b]), keytype(Ks).

But "generating lists that match a constraint" is a thing that comes up often enough that we don't want to write a separate predicate for each constraint! So after some digging, I found a more elegant solution: maplist. Let L=[l1, l2]. Then maplist(p, L) is equivalent to the clause p(l1), p(l2). It also accepts partial predicates: maplist(p(x), L) is equivalent to p(x, l1), p(x, l2). So we could write

contains(L, X) :- member(X, L).

key(Key) :-
    length(Key, 10),
    maplist(contains([a,b]), L),
    % the score stuff

Now, let's query for the Key:

?- key(Key)
Key = [a, b, a, b, a, a, b, a, a, b]
Key = [b, b, a, b, a, a, a, a, a, b]
Key = [b, b, a, b, a, a, b, b, a, b]
Key = [b, b, b, b, a, a, b, a, a, b]

So there are actually four different keys that all explain our data. Does this mean the puzzle is broken and has multiple different answers?

Nope

The puzzle wasn't to find out what the answer key was, the point was to find the fourth student's score. And if we query for it, we see all four solutions give him the same score:

?- key(Key), score([b, b, a, a, a, b, b, a, a, a], Key, X).
X = 6
X = 6
X = 6
X = 6

Huh! I really like it when puzzles look like they're broken, but every "alternate" solution still gives the same puzzle answer.

Total program length: 15 lines of code, compared to the original's 80 lines. Suck it, Pablo.

(Incidentally, you can get all of the answer at once by writing findall(X, (key(Key), score($answer-array, Key, X)), L).)

I still don't like puzzles for teaching

The actual examples I'm using in the book are "analyzing a version control commit graph" and "planning a sequence of infrastructure changes", which are somewhat more likely to occur at work than needing to solve a puzzle. You'll see them in the next release!

If you're reading this on the web, you can subscribe here. Updates are once a week. My main website is here.

My new book, Logic for Programmers, is now in early access! Get it here.