Week 1: Exercises

1. Dancing Pairs

(Clocksin, Clause and Effect, worksheet 1)

Consider this Prolog program:

male(honza).
male(karel).

female(eliska).
female(katka).

dance(P, Q) :- male(P), female(Q).

What answers will these queries produce, and in what order?

1. dance(karel, X).

2. dance(jakub, radka).

3. dance(katka, X).

4. dance(X, eliska).

5. dance(X, X).

6. dance(honza, eliska).

7. dance(X, jana).

8. dance(X, Y).

2. Drinking Pairs

(Clocksin, worksheet 2)

Consider this Prolog program:

drinks(tomas, whiskey).
drinks(sonya, beer).
drinks(lucie, wine).
drinks(radek, beer).
drinks(jarda, beer).

pair(P, Q, D) :- drinks(P, D), drinks(Q, D).

What answers will these queries produce, and in what order?

1. pair(P, tomas, whiskey).

2. pair(sonya, jarda, beer).

3. pair(tomas, sonya, beer).

4. pair(radek, radek, beer).

5. pair(X, Y, beer).

6. pair(X, Y, Z).

3. Directed Graph

(Clocksin, worksheet 4)

Consider an acyclic directed graph defined as follows:

edge(g, h).
edge(g, d).
edge(e, d).
edge(h, f).
edge(e, f).
edge(a, e).
edge(a, b).
edge(b, f).
edge(b, c).
edge(f, c).

1. Write a predicate path(V, W) that is true if there is some path from V to W in the directed graph.

2. Given your predicate, what answers will each of these queries produce?

   • path(f, f).

   • path(a, c).

   • path(g, e).

   • path(g, X).

   • path(X, h).

   • path(X, X).

   • path(X, Y).

4. Genealogy

Suppose that we define a family tree using predicates male, female and parent:

male(jan). male(karel). male(vaclav).

female(anna). female(eliska).

parent(vaclav, anna). parent(vaclav, karel).
parent(karel, jan). parent(karel, eliska).
...

Write Prolog predicates expressing the following relationships:

1. grandmother

2. sibling

   Two people are siblings if they have at least one parent in common.

3. full_sibling

   Full siblings share both parents.

4. first_cousin, second_cousin

   First cousins have parents who are full siblings. Second cousins have parents who are first cousins.

5. cousin

   Two people are cousins if they are N^th cousins for any N ≥ 1.

5. Map of Europe

Consider a map that shows 7 countries: the Czech Republic, Slovakia, Germany, Poland, Austria, Hungary, and Ukraine. Is it possible to color this map with 3 colors so that no bordering countries have the same color? Write a Prolog program that can answer this question.

6. Crosswords

Suppose that we'd like to fill in a 3 x 3 grid with letters so that every row and column contains one of these words:

AGE, AGO, CAN, CAR, NEW, RAN, ROW, WON

Write a Prolog program that can find all possible solutions.

7. Mini-Minesweeper

Consider the following tiny Minesweeper board of dimensions 5 x 2:

1?
2?
2?
2?
1?

A number N means that there are N mines in adjacent squares (which may be adjacent horizontally or diagonally).

Write a Prolog program that can find all possible positions for the mines.

8. Occupations and Instruments

(Levesque, Thinking as Computation, 5.5)

Write a Prolog program that can solve the following puzzle.

Katka, Maria and Roman have distinct occupations and play distinct musical instruments. Their occupations are doctor, lawyer, and teacher, and the instruments they play are piano, flute, and violin. Also:

1. Maria lives next to the doctor.

2. The lawyer plays the piano.

3. Maria is not the teacher.

4. Katka is a patient of the violinist.

Who plays the flute?