# 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

• 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.

```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 = 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.