Prolog/Solving a Logic Puzzle

Let's work with a fun logic problem. You can work out the solution in your head or on scratch paper, then we'll solve it using Prolog.

Consider a group of ten friends who want to visit a new city somewhere in the world. They vote on seven potential destinations:

1. Cairo
2. London
3. Beijing
4. Moscow
5. Mumbai
6. Nairobi
7. Jakarta

One city received four votes, two cities received two votes each, two cities received one vote each, and the remaining two cities received zero votes. How many votes did each of the cities receive?

• Beijing and Cairo got different numbers of votes.
• Moscow either got the most votes, or it got zero votes.
• Cairo got more votes than Jakarta did.
• In the list of cities above, each of the two cities that got two votes has a city that got no votes immediately above it in the list.
• Either Jakarta got one fewer votes than London did, or it got one fewer vote than Beijing did.

Solution in Prolog

Here is one possible solution in Prolog. We'll use the city names to represent the number of votes each received. With the generate-and-test paradigm that Prolog encourages, we'll generate all permutations of votes and test them against the puzzle rules.

Distribution of votes

One city received four votes, two cities received two votes each, two cities received one vote each, and the remaining two cities received zero votes. We can use the built-in permutation predicate.

permutation([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta],[4,2,2,1,1,0,0])

Rule 1

Beijing and Cairo got different numbers of votes. We can use built-in comparison operators. Recall that the semi-colon means OR.

(Cairo < Beijing; Cairo > Beijing)

Rule 2

Moscow either got the most votes, or it got zero votes.

(Moscow = 4; Moscow = 0)

Rule 3

Cairo got more votes than Jakarta did. This is a straight comparison operation.

(Cairo > Jakarta)

Rule 4

In the list of cities above, each of the two cities that got two votes has a city that got no votes immediately above it in the list. This rule is tougher to solve. You might consider modifying the built-in member predicate to look for pairs. Here instead we define a count predicate to count the number of times a pair appears in a list. Then we look for a list in which 0,2 appears twice. This is a special case pattern matcher for [X,Y], X \= Y. Will not work for the general case of [X,X] as it skips the matching 2 elements after a match.

 count([],_,0).
 count([X,Y|Rest],[X,Y],N) :- count(Rest,[X,Y],N1), N is N1 + 1.
 count([Z|Rest],[X,Y],N) :- Z \= X, count(Rest, [X,Y], N).

 count([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta], [0,2], 2)

Rule 5

Either Jakarta got one fewer votes than London did, or it got one fewer vote than Beijing did. Recall that 'is' evaluates the operation.

(Jakarta is (London-1); Jakarta is (Beijing-1))

Complete solution

count([],_,0).
count([X,Y|Rest],[X,Y],N) :- count(Rest,[X,Y],N1), N is N1 + 1.
count([Z|Rest],[X,Y],N) :- Z \= X, count(Rest, [X,Y], N).

votesFor([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta]) :-
    permutation([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta],[4,2,2,1,1,0,0]),
    (Cairo < Beijing; Cairo > Beijing),
    (Moscow = 4; Moscow = 0),
    (Cairo > Jakarta),
    count([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta], [0,2], 2),
    (Jakarta is (London-1); Jakarta is (Beijing-1)).

Prolog returns the following values:

?- votesFor([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta]).
Cairo = 4,
London = Moscow, Moscow = 0,
Beijing = Mumbai, Mumbai = 2,
Nairobi = Jakarta, Jakarta = 1 .

In fact, Prolog returns the solution above eight times. That's because two cities share a vote total in three separate places (2^3 = 8), and Prolog finds each different way of arriving at the same solution.