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:

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?

Solution 2.3