Solving a Zebra Puzzle using Prolog

In this challenge, we are aiming to get the computer to solve Zebra Puzzles by creating Prolog programs.

Zebra Puzzle?

Zebra Puzzles, also known as Einstein’s Riddles, are a type of logic puzzles where you have to use the clues to make logic deductions in order to solve a given problem.

The most famous Zebra Puzzle was created by Einstein and published in 1962. You can find out more about this puzzle on this page.

Our zebra puzzle will be based on the following scenario:

Three kids went to a superheroes fancy dress birthday party.
The names of the three kids are Ethan, Ali and Anya.
They dressed up as Spiderman, Captain America and Iron Man.
The kids are 6, 8 and 10 years old.

We don’t know how each kid dressed up or how old each kid is but we have the following clues:

• Anya was dressed up as Spiderman.
• Ethan was not dressed up as Captain America.
• The youngest kid dressed up as Spiderman.
• The kid who is 8 years old dressed up as Captain America.

You can solve this puzzle manually using the following grid:

Prolog?

Prolog is a declarative language that uses a recursive approach to solve logic puzzles. To solve a logic Puzzle using Prolog, a programmer first needs to declare a knowledge base consisting of a collection of facts and rules. This knowledge base can then be used to run queries to try to solve the puzzle.

Setting up the knowledge base

Let’s first focus on declaring the key facts of our puzzle as follows:

/* Facts */
kid(ethan).
kid(ali).
kid(anya).

hero(spiderman).
hero(captain_america).
hero(iron_man).

age(six).
age(eight).
age(ten).

We will then implement our clues as rules:

relation(K,H,A):- K=anya, H=spiderman, age(A).
relation(K,H,A):- K=ethan, hero(H), age(A), H\=captain_america.
relation(K,H,A):- kid(K), H=spiderman, A=six.
relation(K,H,A):- kid(K), H=captain_america, A=eight.

We will add two extra rules that will be used to solve this puzzle and to reinforce the fact that two kids cannot have the same age or the same costume.

different(X,Y,Z):-X\=Y,X\=Z,Y\=Z.
solve(K1,H1,A1,K2,H2,A2,K3,H3,A3):- relation(K1,H1,A1),relation(K2,H2,A2),relation(K3,H3,A3),different(K1,K2,K3),different(H1,H2,H3),different(A1,A2,A3).

Solving the puzzle…

We have created this knowledge base using an online Prolog Environment called Swish:
https://swish.swi-prolog.org/p/Superheroes%20Zebra%20Puzzle.pl

You can now run the following query to solve this puzzle:

?-solve(K1,H1,A1,K2,H2,A2,K3,H3,A3)

Your Turn!

Pick up any Logic Grid Puzzle from this website and build your own set of facts and rules in Prolog to solve your puzzle.