Solving a Logic Puzzle with Prolog

Have you ever run into a puzzle where you have a list of people that got scrambled up but you managed to keep track of some clues about who is who?

Here’s a simple one from brainzilla

Solve this logic puzzle to find out the name, the age and the favorite superhero of each kid.

1. Bryan likes Spiderman.
2. Tony doesn’t like Superman.
3. The youngest kid likes Spiderman.
4. The kid who likes Superman is 8.

It’s pretty easy to step through this one once you know that the kids are named Bryan, Tony, and Sean, that one of them is 6, one is 8, and one is 10, and that one like Superman, one like Spiderman, and one likes Batman, but the puzzles get a lot harder than this.

Give this one a try without writing any code and see how you fare. It’s definitely possible to solve, but you’ll probably find yourself taking some guesses and then working forward until you reach either a contradiction or you complete the puzzle. Dutifully trying all possibilities is not something humans are great at but fortunately computers excel at it.

Let’s start with a simple python version of the superhero puzzle

from itertools import permutations

boy1, boy2, boy3 = boys = 'Bryan', 'Tony', 'Sean'

for ages in permutations([6, 8, 10]):
    age1, age2, age3 = ages

    for heroes in permutations(['superman', 'spiderman', 'batman']):
        hero1, hero2, hero3 = heroes

        if hero1 != 'spiderman': continue
        if hero2 == 'superman': continue

        for age, hero in zip(ages, heroes):
            if age == 6 and hero != 'spiderman': break
            if age == 8 and hero != 'superman': break
        else:
            print('solved')
            print(boy1, age1, hero1)
            print(boy2, age2, hero2)
            print(boy3, age3, hero3)

> solved
> Bryan 6 spiderman
> Tony 10 batman
> Sean 8 superman

There are definitely a lot of ways to write the code for this puzzle, but this is a straightforward one where we propose a list of boys paired with their favorite hero, and age and then test it against each of the puzzle requirements.

Prolog Version

Here’s the same code using the logic programming language Prolog, which allows you to specify logical constraints and search for parameters that satisfy the equations. This version, like the python version, pairs each boy with a hero and age and then checks to see if the configuration satisfies the constraints.

valid(Name, Age, Hero):-
  (Name = bryan -> Hero = spiderman; true),
  (Name = tony -> Hero \= superman; true),
  (Age = 6 -> Hero = spiderman; true),
  (Age = 8 -> Hero = superman; true).

fans(BryanAge, TonyAge, SeanAge, BryanHero, TonyHero, SeanHero) :-
  permutation([BryanAge, TonyAge, SeanAge], [6, 8, 10]),
  permutation([BryanHero, TonyHero, SeanHero], [spiderman, batman, superman]),

  valid(bryan, tony, sean),
  valid(BryanAge, TonyAge, SeanAge),
  valid(BryanHero, TonyHero, SeanHero).

But this program doesn’t ever realize that Bryan’s hero is Spiderman; it just keeps testing potential solutions, guessing that Tony’s hero is Spiderman or Sean’s hero is Spiderman. As you can imagine, this type of solution can get really bad, but here’s an example

main([A, B, C, D, E, F, G, H, I]):-
  permutation(
    [A, B, C, D, E, F, G, H, I],
    [1, 2, 3, 4, 5, 6, 7, 8, 9]),
  B is A + 1,
  C is A + 2,
  D is A + 3,
  E is A + 4,
  F is A + 5,
  G is A + 6,
  H is A + 7,
  I is A + 8,
  write([A, B, C, D, E, F, G, H, I]).

:- initialization
  time(findall([A, B, C, D, E, F, G, H, I],
  main([A, B, C, D, E, F, G, H, I]), _)),
  halt.

> [1,2,3,4,5,6,7,8,9]
> % 3,005,523 inferences, 0.266 CPU in 0.266 seconds (100% CPU, 11300661 Lips)

With the first guess as [1, 2, 3, 4, 5, 6, 7, 8, 9] it’s actually blazingly fast to find a single solution so instead of randomizing the order or giving it a worst-possible initial guess to dig itself out of, I’ve asked the program to find all solutions. Just like you’d expect, prolog tries all of the posible combinations before determining it can’t find any more solutions so the time grows like n!.

Using a little bit of prolog constraint solving magic, this program gets a lot better.

:- use_module(library(clpfd)).

main([A, B, C, D, E, F, G, H, I]):-
  Vars = [A, B, C, D, E, F, G, H, I],
  Vars ins 1..9,
  B #= A + 1,
  C #= A + 2,
  D #= A + 3,
  E #= A + 4,
  F #= A + 5,
  G #= A + 6,
  H #= A + 7,
  I #= A + 8,
  write([A, B, C, D, E, F, G, H, I]).

:- initialization
  time(findall([A, B, C, D, E, F, G, H, I],
  main([A, B, C, D, E, F, G, H, I]), _)),
  halt.

> [1,2,3,4,5,6,7,8,9]
> % 7,448 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 12511612 Lips)

The core improvement in this version is that prolog keeps track of the domain of posible values for each variable and updates the domain as it reads each constraint, so after B #= A + 1, we know that A must be less than 9. You can confirm that the constraint solver has made the same conclusion with

?- [A, B] ins 1..9, B #= A + 1.
A in 1..8,
A+1#=B,
B in 2..9.

By the time the program has read through all of the constraints, there’s only one possible solution to consider and consequently, unlike the permutation version above finding, the program takes just as long to find one solution as it does to find all solutions.

Smarter Prolog Solver

Where does that leave us with logic puzzles? The constraint solving framework satisfies constraints in integer domains, so we have to convert the puzzle so before it can be solved. To do this, we label Bryan = 1, Tony = 2, and Sean = 3 and set an attribute like Superman to the label of the boy whose hero Superman is.

:- use_module(library(clpfd)).

main() :-
  Bryan = 1, Tony = 2, Sean = 3,
  Ages = [Six, Eight, Ten],
  Heroes = [Batman, Superman, Spiderman],

  Ages ins 1..3, all_distinct(Ages),
  Heroes ins 1..3, all_distinct(Heroes),

  Spiderman #= Bryan,  % bryan likes spiderman
  Superman #\= Tony,  % tony doesn like superman
  Six #= Spiderman,  % youngest likes spiderman
  Superman #= Eight,  % superman fan is 8 years old

  write(Ages), nl,
  write(Heroes), nl.

:- initialization time(main), halt.

> [1,3,2]
> [2,3,1]
> % 5,021 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 8919388 Lips)

Sorry about the weird printed output, I wrote up a version that printed the names and attributes, but it was distractingly complicated.

Back to the Kaiju

With the foundations in place, it’s possible to solve the difficult Kaiju puzzle quickly (though to be fair, the permutation based solution ended up at about 1/5 of a second). This puzzle is much more complicated than the superheroes puzzle and the code to solve it reflects that, but just like the superheroes puzzle, the clpdf based version below, is much faster than

:- use_module(library(clpfd)).

fans() :-
  Tables = [Sizes, Cities, Animals],

  Chaosus = 1, Gargatax = 2, Stovore = 3, Wazilla = 4,
  Sizes = [ThreeFifty, FourHundred, FourFifty, FiveHundred],
  Cities = [Caracas, Glasgow, Santiago, Washington],
  Animals = [Ant, Gorilla, Scorpion, Worm],

  % Only the monster in Washington has the same initial in its name and shape.
  ((Washington #= Gorilla,
    Gargatax #= Gorilla,
    Stovore #\= Scorpion,
    Wazilla #\= Worm);
   (Washington #= Scorpion,
    Gargatax #\= Gorilla,
    Stovore #= Scorpion,
    Wazilla #\= Worm);
   (Washington #= Worm,
    Gargatax #\= Gorilla,
    Stovore #\= Scorpion,
    Wazilla #= Worm)),

  % Only the shortest monster has the same initial in its name and in the city
  % it is in.
  ((ThreeFifty #= Gargatax,
    Gargatax #= Glasgow,
    Stovore #\= Santiago,
    Wazilla #\= Washington,
    Chaosus #\= Caracas);
   (ThreeFifty #= Stovore,
    Gargatax #\= Glasgow,
    Stovore #= Santiago,
    Wazilla #\= Washington,
    Chaosus #\= Caracas);
   (ThreeFifty #= Wazilla,
    Gargatax #\= Glasgow,
    Stovore #\= Santiago,
    Wazilla #= Washington,
    Chaosus #\= Caracas);
   (ThreeFifty #= Chaosus,
    Gargatax #\= Glasgow,
    Stovore #\= Santiago,
    Wazilla #\= Washington,
    Chaosus #= Caracas)),

  % The ant­like monster is Chaosus or is the 400 feet tall one.
  (Ant #= Chaosus; Ant #= FourHundred),

  % Glasgow's menace isn't just 350 feet tall.
  (Glasgow #\= ThreeFifty),

  % The giant scorpion is in Caracas or Glasgow.
  (Scorpion #= Caracas; Scorpion #= Glasgow),

  % The giant worm is 350 or 450 feet long.
  (Worm #= ThreeFifty; Worm #= FourFifty),

  % Stovore is in Caracas or is the worm.
  (Stovore #= Caracas; Stovore #= Worm),

  % Gargatax isn't in Santiago, and isn't 500 feet tall.
  Gargatax #\= Santiago,
  Gargatax #\= FiveHundred,

  % The scorpion is Chaosus or Stovore.
  (Scorpion #= Chaosus; Scorpion #= Stovore),

  append(Tables, Vs),
  Vs ins 1..4,
  maplist(all_distinct, Tables),
  label(Vs),  % force constraint solver to pick a value
  write(Sizes), nl,
  write(Cities), nl,
  write(Animals), nl.

:- initialization time(fans), halt.

% [3,4,2,1]
% [4,1,3,2]
% [4,2,1,3]
% % 14,688 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 8490841 Lips)

---

If this was interesting, definitely checkout this article by Markus Triska, which was an invaluable resource in jumping from the permutations version to the clpfd version.