2    Backtracking

Solution of Exercise 2

2.1    Banknote Change

change( N10, N20, N50) :- 
    c1( N10), c2( N20), c5( N50),
    100 is N10 * 10 + N20 * 20 + N50 * 50.

c5( 0).
c5( 1).
c5( 2).

c2( N) :- c5( N).
c2( 3).
c2( 4).
c2( 5).

c1( N) :- c2( N).
c1( 6).
c1( 7).
c1( 8).
c1( 9).
c1( 10).

Back to example 2.1

2.2    The 4-Color Problem

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

color( red).
color( bue).
color( yellow).
color( green).

adjacent( X, Y) :- color( X), color (Y), X \= Y.

Back to example 2.2

2.3    Europe

density( S, D) :- population( S, E), area( S, F), D is E/F.

neighbors( S1, S2) :- neighbor( S1, S2).
neighbors( S1, S2) :- neighbor( S2, S1).

neighbor_ch( S) :- neighbors( ch, S).         /* Query 1 */

neighbor_f( S) :- neighbors( f, S).           /* Query 2 */

neighbor_d( S) :-                             /* Query 3 */
    neighbors( d, S), 
    population( d, ED), population( S, ES),
    area( d, FD), area( S, FS), 
    ES > ED, FS > FD.

neighbor_ch1( S) :-                           /* Query 4 */
    neighbors( ch, S),
    density( ch, DCH), density( S, DS), DS > DCH.

Back to example 2.3