EN → DE A-AA+ Sitemap Search

# 2    Backtracking

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

## 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) :-
``````

The query

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

should find all admissible colors of the countries by backtracking.

## 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:

1. Which state is a neighbor of Switzerland?
2. Which state is a neighbor of France?
3. Is there a neighbor of Germany that has a bigger population and a larger area than Germany?
4. Is there a neighbor of Switzerland that has a higher density than Switzerland?