# 2 Backtracking

## Solutions

## 2.1 Banknote Change

What are the possibilities to change the 100 Swiss Franc bank note into smaller notes 10 Fr., 20 Fr. and 50 Fr.

Hint: Conceive the predicate

```
change( N10, N20, N50)
```

that finds all solutions by backtracking, such that 10*N10 + 20*N20 + 50*N50 = 100. Save the possible values for N10, N20, N50 as facts, e.g. N10 can be one of 0, 1, 2, .., 10.

### Solution 2.1

## 2.2 The 4-Color Problem

Find an "admissible" coloring of a map such that all adjacent countries have different colors. It had been conjectured for a long time that such a coloring is possible with only 4 colors. This conjecture was formulated precisely by F. Guthrie already in 1852, but proved by K. Appel und W. Haken only in 1976 using a computer program.

Write a Prolog program that finds all admissible colorings of a given map using the colors red, blue, yellow and green.

Fig. 2.1: A Map

Hint: The map can be specified by the following rules:

```
map( A, B, C, D, E) :-
adjacent( A, B),
adjacent( A, D),
adjacent( A, E),
adjacent( B, C),
adjacent( B, D),
adjacent( B, E),
adjacent( C, D),
adjacent( C, E),
adjacent( D, E).
```

The query

```
?- map( A, B, C, D, E)
```

should find all admissible colors of the countries by backtracking.

### Solution 2.2

## 2.3 Europe

Write a database with European countries specifying the area, the population and the neighbors of the individual countries:

```
area( austria, 83858).
area( france, 547030).
area( germany, 357021).
area( italy, 301230).
area( liechtenstein, 160).
area( spain, 504851).
area( switzerland, 41290).
area( united_kingdom, 244820).
. . .
population( austria, 8169929).
poulation( france, 63182000).
poulation( germany, 83251851).
poulation( italy, 59530464).
poulation( liechtenstein, 32842).
poulation( spain, 47059533).
poulation( switzerland, 7507000).
poulation( united_kingdom, 61100835).
. . .
neighbor( austria, switzerland).
neighbor( france, switzerland).
neighbor( france, germany).
neighbor( france, spain).
neighbor( germany, switzerland).
neighbor( italy, switzerland).
neighbor( liechtenstein, switzerland).
. . .
```

Enhance the database with deduction rules, e.g.

```
density( S, D) /* D ist die population density of the state S */
```

such that the following queries are possible:

- Which state is a neighbor of Switzerland?
- Which state is a neighbor of France?
- Is there a neighbor of Germany that has a bigger population and a larger area than Germany?
- Is there a neighbor of Switzerland that has a higher density than Switzerland?