5    Cut, Not, Backtracking

Lösung der Aufgaben

5.1    Ein Tennisturnier

schlaegt( adam, beat).
schlaegt( adam, carlo).
schlaegt( beat, daniel).
schlaegt( carlo, daniel).

klasse0( S, 2) :- 
    schlaegt( S, _), 
    schlaegt( _, S), !.
klasse0( S, 3) :- 
    schlaegt( _, S), !.
klasse0( S, 1) :- 
    schlaegt( S, _), !.

/* ?-klasse0( S, 2) und ?- klasse( S, K) 
werden falsch (unvollstaendig) beantwortet
*/

klasse( S, 1) :- 
    schlaegt( S, _), 
    not schlaegt( _, S).
klasse( S, 2) :- 
    schlaegt( S, _), 
    schlaegt( _, S).
klasse( S, 3) :- 
    schlaegt( _, S), 
    not schlaegt( S, _).

/* auch nicht ganz befriedigend; 
Moeglichkeit: die Instantiierung der Parameter mit var zu testen
*/

Back to example 5.1

5.2    Drei Freunde

/* p( Name, Beruf, Stadt, Rang) */
/* Loesung:
Daniel,  Sportlehrer, Basel,   1
Michael, Arzt,        Zuerich, 2
Beat,    Beamte,      Bern,    3
*/

freunde( S)  :- 
    S = [p( _, _, _, 1), 
    p( _, _, _, 2), 
    p( _, _, _, 3)],
    member( p( beat, _, _, _), S),
    member( p( _, _, zurich, _), S),
    member( p( michael, arzt, _, RM), S),
    member( p( _, _, bern, RB), S), 
    RM < RB,
    member( p( daniel, _, basel, RD), S),
    member( p( _, beamte, _, RBe), S), 
    RD < RBe,
    member( p( _, sportlehrer, _, 1), S).

Back to example 5.2

5.3    Das Damenproblem

5.3.1    Generate and Test

damen( N, Pos) :- 
	list( 1, N, Kolonnen), 
	permutation( Kolonnen, Reihen),
	positionen( Kolonnen, Reihen, Pos), 
	test( Pos).

positionen( [], [], []).
positionen( [ X| Y], [ U| V], 
	[ p( X, U)| W]) :- 
	positionen( Y, V, W).

test( []).
test( [ Q| R]) :- 
	test1( Q, R), 
	test( R).

test1( Q, []).
test1( Q, [ R| S]) :- 
	not_diagonal( Q, R), 
	test1( Q, S).

not_diagonal( p( C1, R1), p( C2, R2)) :-
    X is abs( C1 - C2) - abs( R1 - R2), 
	X \= 0.

list( N, N, [ N]).
list( N, M, [ N| Ns]) :- 
	N < M, N1 is N + 1, 
	list( N1, M, Ns).

permutation( [], []).
permutation( [ X| Y], [ U| V]) :-
    delete( U, [ X| Y], W), 
	permutation( W, V).

delete( X, [ X| Y], Y).
delete( U, [ X| Y], [ X| V]) :- 
	delete( U, Y, V).

Back to example 5.3

5.3.2    Schrittweises Generate and Test

damen_seq( N, Pos) :- 
    list( 1, N, Reihen), 
    damen_seq( Reihen, [], Pos).

damen_seq( Frei, Besetzt, Pos) :- 
    delete( Reihe, Frei, Frei1), 
    test_seq( Reihe, Besetzt),
    damen_seq( Frei1, [ Reihe | Besetzt], Pos).
damen_seq( [], Besetzt, Besetzt).

/* 'Besetzt' ist eine partielle Lösung mit den besetzten Kolonnen in der umgekehrten Reihenfolge, 
z.B. Besetzt = [5, 3, 1] bedeutet: 
1. Kolonne, 1. Reihe
2. Kolonne, 3. Reihe
3. Kolonne, 5. Reihe
*/

test_seq( D, Ds) :- 
    test_seq( D, Ds, 1).
test_seq( D, [ D1| Ds], N) :- 
    not( N is abs( D - D1)), 
    N1 is N + 1, 
    test_seq( D, Ds, N1).
test_seq( _, [], _).

Back to example 5.3