The project
This last lesson builds one program from the pieces of the course: a puzzle solver that reads puzzles written as plain text and solves them. It handles two kinds.
- Cryptarithms, word sums such as
MOON + MOON = NIGHT, in which each letter stands for a different digit. Lesson 7 solved one by hand-writing its equation; here the program reads any such puzzle with a grammar and builds the equation itself. - Sudoku, given as nine lines of digits and dots.
Along the way you will practise what makes Prolog code professional rather than merely working: a parser kept apart from the model, a model kept apart from the search, modules with documented interfaces, a test suite that a build server can run, and a command-line entry point. The lesson ends with a tour of where Prolog and its descendants are used today, as lesson 1 promised, and with suggestions for going further.
Step 1: cryptarithms from text
The first program has three layers. A grammar (lesson 6) turns text into a list of words, each word a list of letters. A model (lesson 7) turns the words into constraints: one variable per distinct letter, all different, no leading zeros, and the sum. A search labels the variables. A fourth predicate, report/1, deals with the outside world: it parses, solves, and prints.
:- initialization(main, main).
:- use_module(library(clpfd)).
:- use_module(library(dcg/basics)).
% equation(Addends, Total): text such as "MOON + MOON = NIGHT", where each
% word becomes a list of one-letter atoms.
equation([W|Ws], Total) -->
blanks, word(W), more_words(Ws), blanks, "=", blanks, word(Total), blanks.
more_words([W|Ws]) --> blanks, "+", blanks, word(W), more_words(Ws).
more_words([]) --> [].
word([L|Ls]) --> letter(L), letters(Ls).
letters([L|Ls]) --> letter(L), letters(Ls).
letters([]) --> [].
letter(L) --> [C], { code_type(C, upper), char_code(L, C) }.
% solve(Addends, Total, Numbers): Numbers are the values of the addends
% and the total, in order, with a different digit for each letter.
solve(Addends, Total, Numbers) :-
append([Total|Addends], AllLetters),
sort(AllLetters, Letters),
pairs_keys_values(Pairs, Letters, Digits),
Digits ins 0..9,
all_different(Digits),
maplist(word_value(Pairs), Addends, Values),
word_value(Pairs, Total, Sum),
sum(Values, #=, Sum),
labeling([ff], Digits),
append(Values, [Sum], Numbers).
% word_value(Pairs, Word, Value): Value is the number Word spells, given
% Letter-Digit pairs; a word may not start with 0.
word_value(Pairs, Word, Value) :-
maplist(digit_of(Pairs), Word, [D|Ds]),
D #\= 0,
foldl(shift, Ds, D, Value).
digit_of(Pairs, Letter, Digit) :-
memberchk(Letter-Digit, Pairs).
shift(D, Acc, Value) :-
Value #= 10 * Acc + D.
% report(Text): parse a puzzle, count its solutions and show the first.
report(Text) :-
string_codes(Text, Codes),
( phrase(equation(Addends, Total), Codes)
-> findall(Ns, solve(Addends, Total, Ns), Solutions),
length(Solutions, N),
( Solutions = [First|_]
-> append(Left, [Sum], First),
atomic_list_concat(Left, ' + ', Lhs),
format("~w: ~w solution(s), first ~w = ~w~n", [Text, N, Lhs, Sum])
; format("~w: no solution~n", [Text])
)
; format("~w: cannot read this puzzle~n", [Text])
).
main :-
report("LOGIC + LOGIC = PROLOG"),
report("MOON + MOON = NIGHT"),
report("CROSS + ROADS = DANGER"),
report("TWO + TWO = FOUR"),
report("SUN + SUN = STAR"),
report("MOON + = NIGHT").LOGIC + LOGIC = PROLOG: 1 solution(s), first 90452 + 90452 = 180904
MOON + MOON = NIGHT: 1 solution(s), first 6771 + 6771 = 13542
CROSS + ROADS = DANGER: 1 solution(s), first 96233 + 62513 = 158746
TWO + TWO = FOUR: 7 solution(s), first 734 + 734 = 1468
SUN + SUN = STAR: no solution
MOON + = NIGHT: cannot read this puzzleThe interesting moves:
- One variable per letter, shared through pairs.
sort/2gives the distinct letters, andpairs_keys_values/3pairs each with a fresh variable, for example['G'-G, 'H'-H, ...].digit_of/3looks a letter up withmemberchk/2, so everyOinMOONrefers to the same variable. That sharing is the whole puzzle, and unification provides it for free. - Numbers built by folding.
foldl(shift, Ds, D, Value)turns the digits[6, 7, 7, 1]into the constraint 10·(10·(10·6 + 7) + 7) + 1, the way you read a number left to right. Becauseshift/3uses#=, the value is a constraint on unknown digits, not a computation. sum(Values, #=, Sum)handles any number of addends, soA + A + A = BAworks as well as two-word puzzles.- Labelling strategy.
labeling([ff], Digits)labels the letter with the fewest remaining possibilities first. With plainlabel/1, the same program took several times as long in our test runs, almost all of it on CROSS + ROADS = DANGER, where nine letters and one long equation give propagation little to work with. Trying the strategy options of lesson 7 is a cheap first step whenever a constraint program is slow. - Three different outcomes are reported differently: a puzzle with solutions, a well-formed puzzle with none (SUN + SUN = STAR cannot work: twice a three-digit number is below 2,000, so STAR would have to start with 1, but then SUN would be below 200 and its double would have only three digits), and text that is not a puzzle at all. Distinguishing "no answer" from "bad question" is a habit worth keeping in every interface you write.
Step 2: Sudoku
A Sudoku grid is nine rows of nine cells, each from 1 to 9, with every row, column and 3×3 box all different. That sentence translates almost word for word into constraints. The puzzle below was generated for this course and has exactly one solution.
:- initialization(main, main).
:- use_module(library(clpfd)).
% puzzle(Rows): one string per row, '.' for an empty cell.
puzzle([ "4.7......",
".....1..8",
"...93...1",
"25....4..",
"..3.8.6..",
".7...5...",
"548....7.",
".....42..",
".....3.5." ]).
% grid(Strings, Rows): Rows is a list of rows of cells; a digit gives a
% number and '.' a fresh variable.
grid(Strings, Rows) :-
maplist(row, Strings, Rows).
row(String, Cells) :-
string_chars(String, Chars),
maplist(cell, Chars, Cells).
cell('.', _).
cell(C, N) :- char_type(C, digit(N)), N > 0.
% sudoku(Distinct, Rows): the rules of Sudoku, using Distinct
% (all_different or all_distinct) to say that nine cells differ.
sudoku(Distinct, Rows) :-
length(Rows, 9),
maplist(same_length(Rows), Rows),
append(Rows, Cells),
Cells ins 1..9,
maplist(Distinct, Rows),
transpose(Rows, Columns),
maplist(Distinct, Columns),
Rows = [A, B, C, D, E, F, G, H, I],
boxes(Distinct, A, B, C),
boxes(Distinct, D, E, F),
boxes(Distinct, G, H, I).
% boxes(Distinct, R1, R2, R3): the 3x3 boxes in three consecutive rows.
boxes(_, [], [], []).
boxes(Distinct, [A, B, C|R1], [D, E, F|R2], [G, H, I|R3]) :-
call(Distinct, [A, B, C, D, E, F, G, H, I]),
boxes(Distinct, R1, R2, R3).
% known(Distinct, K): K cells are fixed by propagation alone.
known(Distinct, K) :-
puzzle(Strings),
grid(Strings, Rows),
sudoku(Distinct, Rows),
append(Rows, Cells),
include(integer, Cells, Known),
length(Known, K).
print_grid(Rows) :-
forall(member(Row, Rows),
( atomic_list_concat(Row, ' ', Line),
format(" ~w~n", [Line]) )).
main :-
forall(member(D, [all_different, all_distinct]),
( known(D, K),
format("~w: ~w of 81 cells known before search~n", [D, K]) )),
puzzle(Strings),
grid(Strings, Rows),
sudoku(all_distinct, Rows),
append(Rows, Cells),
findall(Rows, label(Cells), Solutions),
length(Solutions, N),
format("Solutions: ~w~n", [N]),
Solutions = [Solution],
print_grid(Solution).all_different: 23 of 81 cells known before search
all_distinct: 81 of 81 cells known before search
Solutions: 1
4 1 7 5 6 8 9 3 2
3 2 9 7 4 1 5 6 8
6 8 5 9 3 2 7 4 1
2 5 6 3 1 9 4 8 7
1 9 3 4 8 7 6 2 5
8 7 4 6 2 5 3 1 9
5 4 8 2 9 6 1 7 3
7 3 1 8 5 4 2 9 6
9 6 2 1 7 3 8 5 4Points worth studying:
- The grid reader is the grammar of a trivial format.
cell('.', _)turns a dot into a fresh variable, andchar_type(C, digit(N))turns a digit character into its value. A malformed row (a letter, say) simply makesgrid/2fail. - Rows, columns and boxes come from list operations, not index arithmetic.
transpose/2(fromlibrary(clpfd)) gives the columns, andboxes/4walks three rows at a time, taking three cells from each. Nothing in the model mentions a row or column number. sudoku/2is higher-order. It takes the "all different" predicate as an argument, andmaplist(Distinct, Rows)andcall(Distinct, Box)apply it. That made the experiment inmaina two-line loop.- Propagation strength matters. With
all_different, which removes a value from other cells only once some cell is fixed to it, propagation learns nothing beyond the 23 given cells, and labelling has to search. Withall_distinct, which reasons about all nine cells together (a classic matching argument: if three cells of a row can only hold 4, 7 and 9, no other cell of that row can), propagation alone solves this whole puzzle before labelling starts. Stronger propagation costs more per step and often saves a vast amount of search; measuring both is the professional habit. - Counting solutions is a test of the puzzle.
findalloverlabel(Cells)found exactly one, which is what makes it a proper Sudoku. Puzzle setters use solvers in exactly this way.
Step 3: modules, tests and a command line
Project layout
So far every program has been one file. A real project splits into modules, one per responsibility, with tests and an entry point. A conventional layout looks like this; its pack.pl file and prolog/ directory are also what SWI-Prolog expects of a publishable pack:
puzzles/
pack.pl name, version, author, dependencies (for publishing)
prolog/
cryptarithm.pl :- module(cryptarithm, [puzzle_solution/2]).
sudoku.pl :- module(sudoku, [sudoku/2, grid/2]).
test/
test_cryptarithm.pl plunit tests for prolog/cryptarithm.pl
test_sudoku.pl
main.pl the command-line programA module is a file that begins with :- module(Name, Exports). Only the predicates in the export list are visible to code that loads it with use_module/1; everything else, such as shift/3 or letters//1, stays private, so you can rename or rewrite helpers without breaking anyone. Clashes between helper names in different files disappear too. Above each exported predicate goes a structured comment, starting %!, with the argument modes and determinism from lesson 4; SWI-Prolog's documentation tool, PlDoc, turns them into web pages, and they tell a reader in one line how to call the predicate.
The entry point uses library(main), which calls main/1 with the command-line arguments as a list of atoms:
:- use_module(library(main)).
:- use_module(prolog/cryptarithm).
:- initialization(main, main).
main(Argv) :-
( Argv = [Text]
-> forall(puzzle_solution(Text, Numbers),
format("~w~n", [Numbers]))
; format(user_error, "usage: swipl main.pl \"SEND + MORE = MONEY\"~n", []),
halt(2)
).Run as swipl main.pl "MOON + MOON = NIGHT", it prints [6771,6771,13542]; run with no argument, it prints the usage message and exits with status 2, the usual convention for "you called me wrongly".
A tested module
Here is the cryptarithm solver as a module with a test suite, in one file so that it runs on its own. The model is the one from step 1; what is new is the interface and the tests.
:- module(cryptarithm, [puzzle_solution/2]).
:- initialization(main, main).
:- use_module(library(clpfd)).
:- use_module(library(dcg/basics)).
:- use_module(library(plunit)).
%! puzzle_solution(+Text, -Numbers) is nondet.
%
% Numbers are the values of the words of the cryptarithm Text, such as
% "MOON + MOON = NIGHT", with the total last. Fails if the puzzle has no
% solution; raises a syntax error if Text is not a puzzle.
puzzle_solution(Text, Numbers) :-
string_codes(Text, Codes),
( phrase(equation(Addends, Total), Codes)
-> solve(Addends, Total, Numbers)
; syntax_error(cryptarithm(Text))
).
equation([W|Ws], Total) -->
blanks, word(W), more_words(Ws), blanks, "=", blanks, word(Total), blanks.
more_words([W|Ws]) --> blanks, "+", blanks, word(W), more_words(Ws).
more_words([]) --> [].
word([L|Ls]) --> letter(L), letters(Ls).
letters([L|Ls]) --> letter(L), letters(Ls).
letters([]) --> [].
letter(L) --> [C], { code_type(C, upper), char_code(L, C) }.
solve(Addends, Total, Numbers) :-
append([Total|Addends], AllLetters),
sort(AllLetters, Letters),
pairs_keys_values(Pairs, Letters, Digits),
Digits ins 0..9,
all_different(Digits),
maplist(word_value(Pairs), Addends, Values),
word_value(Pairs, Total, Sum),
sum(Values, #=, Sum),
labeling([ff], Digits),
append(Values, [Sum], Numbers).
word_value(Pairs, Word, Value) :-
maplist(digit_of(Pairs), Word, [D|Ds]),
D #\= 0,
foldl(shift, Ds, D, Value).
digit_of(Pairs, Letter, Digit) :-
memberchk(Letter-Digit, Pairs).
shift(D, Acc, Value) :-
Value #= 10 * Acc + D.
:- begin_tests(cryptarithm).
test(unique, all(Ns == [[90452, 90452, 180904]])) :-
puzzle_solution("LOGIC + LOGIC = PROLOG", Ns).
test(three_addends, all(Ns == [[5, 5, 5, 15]])) :-
puzzle_solution("A + A + A = BA", Ns).
test(spacing, all(Ns == [[6771, 6771, 13542]])) :-
puzzle_solution(" MOON+MOON =NIGHT ", Ns).
test(count, Count == 7) :-
aggregate_all(count, puzzle_solution("TWO + TWO = FOUR", _), Count).
test(sums_hold, forall(puzzle_solution("TWO + TWO = FOUR", [A, B, S]))) :-
S =:= A + B.
test(no_solution, fail) :-
puzzle_solution("SUN + SUN = STAR", _).
test(bad_input, error(syntax_error(cryptarithm(_)))) :-
puzzle_solution("MOON + = NIGHT", _).
:- end_tests(cryptarithm).
main :-
run_tests.One run printed this (the timings differ from run to run and machine to machine):
% Start unit: cryptarithm
% [1/7] cryptarithm:unique .......................... passed (0.391 sec)
% [2/7] cryptarithm:three_addends ................... passed (0.001 sec)
% [3/7] cryptarithm:spacing ......................... passed (0.066 sec)
% [4/7] cryptarithm:count ........................... passed (0.069 sec)
% [5-1/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-2/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-3/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-4/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-5/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-6/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [5-7/7] cryptarithm:sums_hold ..................... passed (0.000 sec)
% [6/7] cryptarithm:no_solution ..................... passed (0.001 sec)
% [7/7] cryptarithm:bad_input ....................... passed (0.001 sec)
% End unit cryptarithm: passed (0.592 sec CPU)
% All 7 (+6 sub-tests) tests passed in 0.601 seconds (0.593 cpu)How to read the tests:
- A test is a clause
test(Name, Options) :- Body.betweenbegin_testsandend_tests. The options say what counts as passing.all(Ns == [...])collects every solution of the body and compares the list, so the first three tests check not only the answer but that it is the only one.Count == 7checks a value after the body succeeds.failexpects failure, anderror(...)expects that exception. forall(Generator)turns one test into many: the body runs once for each solution of the generator, which is why the report shows seven sub-tests for the seven solutions of TWO + TWO = FOUR. It is a small taste of property-based testing: rather than listing expected answers, assert a property that every answer must have.syntax_error/1, fromlibrary(error), throwserror(syntax_error(Culprit), _). Raising an error for bad input, rather than failing, keeps "no solution" and "not a puzzle" apart for callers, asreport/1did by hand in step 1.run_testsfails if any test fails, somainfails andswiplexits with status 1, printing each failure with its file and line. A continuous-integration job needs nothing more. In the multi-file layout, the tests live intest/test_cryptarithm.pl, which loads../prolog/cryptarithmwithuse_module/1and is run withswipl -g run_tests -t halt test/test_cryptarithm.pl.- plunit also watches determinism: a test that succeeds but leaves a choice point behind gets a warning, which catches the leftover choice points discussed in lesson 5. Mark a test
nondetwhen several answers are intended.
Where Prolog and its relatives are used
Prolog did not become a mainstream language, and it is honest to say so. Its ideas spread anyway, often under other names. A tour, as of 2026:
- Logic programming itself. SWI-Prolog, SICStus, GNU Prolog, XSB, Scryer and Trealla are all maintained. Prolog is used for rule-heavy applications such as configuration, scheduling, verification tools and knowledge bases, and in research and teaching on logic, language and AI. The graph database TerminusDB is written largely in Prolog, and SWI-Prolog itself ships a web server, an RDF store for the Semantic Web and an interface to Python.
- Natural-language processing. Beyond the history of lesson 6, IBM's Watson system, which won the quiz show Jeopardy! in 2011, used Prolog to express pattern-matching rules over the parse trees of questions.
- Other languages. Erlang began as an interpreter written in Prolog, which is why Erlang's atoms, capitalised variables and clauses ending in full stops look familiar. Mercury and Curry combine logic programming with strong types or functional programming.
- Type checkers. Type inference in Haskell, OCaml and Rust is unification over types (lesson 2). Rust's experimental trait solver Chalk describes itself as an implementation of the Rust trait system "using a PROLOG-like logic solver", and Rust's next-generation borrow checker, Polonius, was prototyped as rules in Datalog.
- Datalog and its descendants. Datalog is Prolog without compound terms, usually evaluated bottom-up to a fixed point, much as tabling does, so every query terminates. It powers program analysis (Soufflé, an engine built for static analysis of programs; CodeQL, GitHub's code-analysis language, which grew from Semmle's Datalog-based QL), databases (Datomic's queries are Datalog) and policy engines (Open Policy Agent's Rego, whose documentation says it "was inspired by Datalog").
- Constraints and solvers. Constraint logic programming grew into the constraint solvers used for timetabling, rostering and logistics, many no longer written in Prolog, and answer set programming systems such as clingo carry the logic-programming idea into hard combinatorial search.
The common thread is the one this course started with: describe the problem as relations, and let a general mechanism search for the answers.
Where to go next
You now know the core of Prolog and the ideas that make it distinctive. To keep going:
- Practise. The Exercism Prolog track has graded exercises with tests. Puzzles from programming contests are a good fit for Prolog, especially with
library(clpfd)and tabling. - Read. Markus Triska's free online book The Power of Prolog goes deeper into pure, declarative style, constraints and DCGs. The Art of Prolog by Leon Sterling and Ehud Shapiro is the classic book on programming techniques, and Ivan Bratko's Prolog Programming for Artificial Intelligence applies Prolog to search, planning and expert systems. Learn Prolog Now! remains a gentle second pass over the basics.
- Explore the system. The SWI-Prolog manual documents the libraries this course only touched: strings and dicts, threads and engines, the HTTP server, Constraint Handling Rules. Packs add community libraries, and the SWI-Prolog Discourse forum is where to ask questions.
- Extend the project. Add a third puzzle type to the solver (a magic square, a KenKen grid, an N-queens board), give it its own module and tests, and let
main.plchoose the solver from the input's format.
Common misconceptions
Misconception
"Prolog programs can't be structured like real software." Modules, documentation comments, unit tests, packages and a command-line interface are all standard, as this lesson showed. The structure looks different from an object-oriented project, but the engineering habits are the same.
Misconception
"A constraint model that is correct is fast enough." Correctness is the first step. Propagation strength (all_different or all_distinct) and the labelling strategy (ff and friends) can change the running time by orders of magnitude on the same model, so measure.
Misconception
"Prolog is dead." It is a niche language, but an active one with several maintained systems, and its ideas, from unification to Datalog, are at work in compilers, databases and analysis tools that many programmers use every day.
Exercises
Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.
1. Project: a puzzle solver
CoreComputationalHow many solutions does the step 1 program report for I + I = ME? Try to work it out by hand first.
2. Project: a puzzle solver
CoreComputationalThe step 1 program reports exactly one solution for SO + SO = TOO. What is it? Write it as the program prints it after "first", for example 6771 + 6771 = 13542.
3. Project: a puzzle solver
Warm-upComputationalWhat is the first row of the Sudoku's solution? Write the nine digits with no spaces.
4. Project: a puzzle solver
CoreHumanWhy did all_distinct fix all 81 cells of the lesson's Sudoku before search, while all_different fixed only the 23 given ones?
5. Project: a puzzle solver
CoreComputationalWhat does the plunit test test(unique, all(Ns == [[90452, 90452, 180904]])) :- puzzle_solution("LOGIC + LOGIC = PROLOG", Ns). check?
6. Project: a puzzle solver
Warm-upHumanIn the tested module, main just calls run_tests. If one test fails, what exit status does swipl main.pl return?
7. Project: a puzzle solver
CoreHumanAccording to the lesson, which of these are built on Datalog or were inspired by it? Choose all that apply.
Further reading and resources
- SWI-Prolog manual, modulesModule declarations, import and export, and how goals are resolved across modules.
- Prolog Unit Tests (plunit)The test framework used here, with every test option.
- SWI-Prolog packsAdd-on libraries published by the community, installed with pack_install/1.
- SWI-Prolog DiscourseThe community forum, where users and the developers of SWI-Prolog answer questions.
- Datalog (Wikipedia)The language, its evaluation, and a long list of engines and products built on it.
- Exercism, Prolog trackFree practice exercises with tests, and optional feedback from volunteer mentors.
- The Art of Prolog · Leon Sterling and Ehud ShapiroA classic, thorough textbook on programming techniques in Prolog (MIT Press).
- Prolog Programming for Artificial Intelligence · Ivan BratkoA long-lived textbook pairing Prolog with search, planning and knowledge representation.