I first got into AI in the late 1980s while at Air Canada. At that time, AI research and applications were dominated by the languages LISP and Prolog. I experimented with both, and was fascinated with Prolog’s ability to solve problems that you defined as facts, and rules. During a recent visit to Bletchley Park north of London, I reflected on how this ability could have helped the tedious code-breaking efforts there, had it been available, and picked up a book of logic puzzles in the shop, with the intent of solving them using AI and Prolog.

---

A highlight was Alan Turing’s office at Bletchley Park:

---

And here is a reconstruction of the Bombe, an computer composed of electromagnetc switches, that tested many combination of code settings, an application that Prolog could handle with ease:

A sample problem

From the lofty codebreaking at Bletchley Park, here is more modest example, problem 4 from the book, Logic Puzzles 2, published by the Bletchley Park Trust in 2022 (volume 1 appears to be out of print):

Mixed Menus: Karen likes to serve up a three-course dinner each evening. Here are some clues as to what she gave her family on different evenings. Can you discover what was eaten from Monday to Thursday of last week?

• The melon was eaten on Tuesday, earlier in the week than the freshly made trifle

• The prawns and apple pie were eaten at the same meal, the evening before Karen served both garlic mushrooms and pan-fried steak

• Ice cream was the sweet course the evening before the vegetable curry, which was not served on Tuesday

• On one evening, Karen made tomato soup and followed this with a main course of roast chicken

A Prolog solution

While you could work out the solution using pencil and paper (that is indeed the point of the book!), you can also describe the problem using logic, and get Prolog to solve it.

Here is the program I came up with (percent signs mean the rest of the line is a comment):

solve(Meals) :-

  % Each meal, represented as Evening, Starter, Main, Dessert
  Meals = [
    meal(1, S1, M1, D1),
    meal(2, S2, M2, D2),
    meal(3, S3, M3, D3),
    meal(4, S4, M4, D4)
  ],

  % The possible values for each variable
  permutation([melon, mushrooms, prawns, soup], [S1, S2, S3, S4]),
  permutation([chicken, fish, steak, curry], [M1, M2, M3, M4]),
  permutation([applepie, icecream, profiteroles, trifle], [D1, D2, D3, D4]),

  % Clue 1: The melon was eaten on Tuesday, earlier in the week than the
  % freshly made trifle
  member(meal(2, melon, _, _), Meals),
  member(meal(X1, _, _, trifle), Meals),
  2 < X1,

  % Clue 2: The prawns and apple pie were eaten at the same meal, the evening
  % before Karen served both garlic mushrooms and pan-fried steak
  member(meal(X2, prawns, _, applepie), Meals),
  member(meal(X3, mushrooms, steak, _), Meals),
  X2 =:= X3 - 1,

  % Clue 3: Ice cream was the sweet course the evening before the vegetable
  % curry, which was not served on Tuesday
  member(meal(X4, _, _, icecream), Meals),
  member(meal(X5, _, curry, _), Meals),
  X4 =:= X5 - 1,
  X5 \== 2,

  % Clue 4: On one evening, Karen made tomato soup and followed this with a
  % main course of roast chicken
  member(meal(_, soup, chicken, _), Meals).

Running the program

You can install either SWI Prolog or GNU Prolog, or another implementation. These are open source, stable and actively maintained.

Start GNU Prolog, load the program, and then execute the solve predicate as follows:

> gprolog
GNU Prolog 1.5.0 (64 bits)
Compiled Apr 23 2022, 09:20:55 with gcc
Copyright (C) 1999-2022 Daniel Diaz

| ?- [p04].
compiling /home/ak/learn/prolog/logic_puzzles2/p04.pl for byte code...
yes

| ?- solve(X).
X = [meal(1,soup,chicken,profiteroles),meal(2,melon,fish,icecream),
meal(3,prawns,curry,applepie),meal(4,mushrooms,steak,trifle)] ? ;

(13 ms) no
| ?-

The line X = ... shows the solution it found. Press Enter to stop there, or hit the semicolon to search for alternate solutions (there is only one solution in this example, so it replies “no”).

Press Ctrl+D to exit the Prolog interpreter.

How it works

Prolog works by finding the values of variables that make the expressions True. Conditions connected by commas are considered “and”, and if an expression fails, the solver backtracks to the previous decision point and tries that route. So by default, Prolog uses depth-first search.

Here is a line-by line explanation:

solve(Meals) :- introduces a predicate, and the “:-” can be read as “if”. So “solve(Meals)” is True if the expressions are all true.

In this solution, we represent the final solution as a list of “meal” objects, one for each of the four days (the number at the beginning of each meal), and each day containing a distinct starter, main, and dessert (Sn, Mn, and Dn respectively). These courses start with upper-case letters, so they are variables that the Prolog solver tries to assign (“unify”) during the solving process:

  % Each meal, represented as Evening, Starter, Main, Dessert
  Meals = [
    meal(1, S1, M1, D1),
    meal(2, S2, M2, D2),
    meal(3, S3, M3, D3),
    meal(4, S4, M4, D4)
  ],

Next, we use permutation, a built-in predicate, to try each possible permutation of the options for each course, i.e., the options in each possible order. Due to Prolog’s backtracking, each possibility is attempted until a solution is found (so kind of brute force, but not as bad as an exhaustive search, see below):

  % The possible values for each variable
  permutation([melon, mushrooms, prawns, soup], [S1, S2, S3, S4]),
  permutation([chicken, fish, steak, curry], [M1, M2, M3, M4]),
  permutation([applepie, icecream, profiteroles, trifle], [D1, D2, D3, D4]),

The clues are coded as constraints, that test if the S/M/D values for each meal are valid. The first clue tests if the melon was eaten on Tuesday, earlier in the week than the freshly made trifle:

  member(meal(2, melon, _, _), Meals),
  member(meal(X1, _, _, trifle), Meals),
  2 < X1,

So this uses the built-in member predicate to check that the tentative solution has a meal on day 2 that has melon as a starter, with any main or dessert (the underscores accept any value). Remember, if any condition fails, the solver ignores the rest of the conditions, and backtracks to an earlier point (that’s why it’s more efficient than an exhaustive brute-force search, if the problem is formulated well).

Then, we check which day trifle was served for dessert, and assigns the day to X1 (uppercase, so a variable).

Finally, we check if Tuesday is before X1. So that’s Clue #1.

The second clue requires that prawns and apple pie were eaten at the same meal, the evening before Karen served both garlic mushrooms and pan-fried steak:

  member(meal(X2, prawns, _, applepie), Meals),
  member(meal(X3, mushrooms, steak, _), Meals),
  X2 =:= X3 - 1,

Here we check that there a day on which prawns were served as a starter and apple pie was for dessert, and the day on which this happens is assigned to X2.

Then,we check that there a day on which mushrooms were served as a starter and steak was the main dish, and the day on which this happens is assigned to X3.

Finally, which check that X2 is one day before X3 (the =:= operator tests equalities for numeric values).

The third clue tests ice cream was the sweet course the evening before the vegetable curry, which was not served on Tuesday:

  member(meal(X4, _, _, icecream), Meals),
  member(meal(X5, _, curry, _), Meals),
  X4 =:= X5 - 1,
  X5 \== 2,

Here, we find out which day ice cream was for dessert and which day curry was served as a main, and make sure that ice cream is the day before curry. We also use the same variable to test that curry was not on Tuesday.

Finally, clue 4 requires that on one evening, Karen made tomato soup and followed this with a main course of roast chicken, simple to test by checking that the solution includes a meal with soup and chicken, regardless of dessert:

  member(meal(_, soup, chicken, _), Meals).

The final clause has a period after it, which means it is the end of the conditions. Because all the conditions are separated by commas, each condition has to be true to reach the end, otherwise the solver backtracks to try an alternate solution.

There are other ways to formulate this problem, but this general structure works well where you are trying to find a combination of rows that satisfy certain conditions.

Useful in the real world?

For me, Prolog captures the imagination of what Artificial Intelligence could look like. It appears to be intelligent, allowing you to describe a problem, and solving it without you having to define the steps.

Of course, the unification, backtracking, commas for “and” and semicolons for “or” implicitely define a sequence, and you need to understand these things to use Prolog effectively, but it still looks somewhat magical.

Although it has lost some of its excitement, Prolog and its descendants have been applied to certain types of problems in the real world, such as:

• grammar parsing
• scheduling
• resource allocation
• combinatorial puzzles
• contract checking
• product or system configuration

One of the limitations of Prolog has been its strictly declarative nature, which makes it hard to adapt to the non-logic parts of applications, such as input/output, database retrieval, communications, and procedural logic. Most Prolog implementations have built-in predicates to handle these sorts of things, but Prolog applications in the real world tend to embed Prolog into another language or system. So Prolog is used to solve the logic parts of larger applications, and the broader application architecture will be a more conventional tech stack, with Prolog embedded as a component.

I think a larger force that has held Prolog back is that it is very different, and hard to learn. You can’t just start programming in Prolog using the approaches that work in Python, Go, or Java – it requires a new way of thinking. I have personally found this stretch to be fascinating, but I can see how it holds the language back.

An obvious question is, can’t you just use an LLM to solve these sorts of problems, or at least write the programs in Prolog? The answer is “sort of”, and I have had some success using Claude and ChatGPT to solve simple logic programs, including by writing Prolog programs. Still, if you understand the domain, and can define the facts and rules to describe a problem, it is helpful to be able to express the problem in something like Prolog, certainly for production applications where hallucination or incorrect specification is a risk.

That said, I believe that Prolog and related languages occupy an important niche in AI, that has not been replaced by newer developments, and that it is still relevant.

Resources for learning Prolog

Two books I have found useful for revisiting Prolog include

• Programming in Prolog, 5th edition by William Clocksin and Christopher Mellish (Springer, 2003)
• Prolog for Artificial Intelligence by Noah Sinclair (independent via Amazon, 2026)

The second is one of several very recent books on Prolog, showing that there is new and current interest in the language, despite all the focus on generative and agentic AI using LLMs.

There are many other classic texts that I will revisit, including Clause and Effect by William Clocksin, Art of Prolog by Leon Sterling and Ehud Shapiro, and The Craft of Prolog by Richard O’Keefe. These are all still in print!

Bletchley Park Logic Puzzles 2 (Bletchley Park Trust, 2022) is a good source of puzzles, although they all seem to be of the same basic structure.

The main open source Prolog systems are SWI Prolog and GNU Prolog; both have excellent documentation.