5    Cut, Not, Backtracking

Solution of Exercise 5

5.1    A Tennis Tournament

beats( adam, bill).
beats( adam, carlo).
beats( bill, daniel).
beats( carlo, daniel).

/* 1st Implementation using 'cut' */
category1( S, 2) :- beats( S, _), beats( _, S), !.
category1( S, 3) :- beats( _, S), !.
category1( S, 1) :- beats( S, _), !.

/* 2nd Implementation using 'not' */
/* SWI Prolog uses '\+' for 'not' */

category2( S, 1) :- beats( S, _), \+ beats( _, S).
category2( S, 2) :- beats( S, _), beats( _, S).
category2( S, 3) :- beats( _, S), \+ beats( S, _).

/* Query 1
?- category1(adam, C). => C = 1 		-OK
?- category2(adam, C). => C = 1; C = 1	-NOK: double solutions
*/

/* Query 2
?- category1(P, 2). => P = bill			-NOK: carlo missing
?- category2(P, 2). => P = bill; carlo	-OK
*/

/* Query 3
?- category1(adam, 1). => true			-OK
?- category1(adam, 2). => false			-OK
?- category1(adam, 4). => false			-OK
?- category2(adam, 1). => true			-OK
?- category2(adam, 2). => false			-OK
?- category2(adam, 4). => false			-OK
*/

/* Query 4
?- category1(thomas, C). => false		-OK
?- category2(thomas, C). => false		-OK
*/

/* Query 5
?- category1(P, C). => P = bill, C = 2	-NOK: missing solutions
?- category2(P, C). => 
	P = adam, C = 1; P = adam, C = 1; 	-NOK: double solutions
	P = bill, C = 2; 
	P = carlo, C = 2;
	P = daniel, C = 3; P = daniel, C = 3	
*/

/* The implementations are not very satisfactory.
   An improvement would be to test the instantiation
   of variables using 'var'.
*/

Back to example 5.1

5.2    Three Friends

/*        p( Name,    Job,           City,    Rank) */
/* Solution: daniel,  sport_teacher, basel,   1
             michael, doctor,        zurich,  2
             bill,    officer,       bern,    3
*/

friends( S)  :- 
    S = [p( _, _, _, 1), p( _, _, _, 2), p( _, _, _, 3)],
    member( p( bill, _, _, _), S),
    member( p( _, _, zurich, _), S),
    member( p( michael, doctor, _, RM), S),
    member( p( _, _, bern, RB), S), RM < RB,
    member( p( daniel, _, basel, RD), S),
    member( p( _, officer, _, RBe), S), RD < RBe,
    member( p( _, sport_teacher, _, 1), S).

Back to example 5.2

5.3    The N Queens Problem

5.3.1    Generate and Test

queens( N, Pos) :- 
    list( 1, N, Columns), 
    permutation( Columns, Rows),
    positions( Columns, Rows, Pos), 
    test( Pos).

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

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

test1( _, []).
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    Stepwise Generate and Test

queens( N, Pos) :-
	queens_seq( N, RevPos),
	reverse_list(RevPos, Pos).

queens_seq( N, Pos) :- 
    list( 1, N, Rows), 
    queens_seq( Rows, [], Pos).

queens_seq( Free, Occupied, Pos) :- 
    delete( Row, Free, Free1), 
    test_seq( Row, Occupied),
    queens_seq( Free1, [ Row | Occupied], Pos).
queens_seq( [], Occupied, Occupied).

/* 'Occupied' is a partial solution with the occupied
columns in the reverse order of the rows, e.g. Occupied = [5, 3, 1]
means that the queens are positioned so far as: 
1. Column, 1. Row
2. Column, 3. Row
3. Column, 5. Row
*/

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( _, [], _).

reverse_list( X, Y) :- reverse_list( X, [], Y).        /* accumulator */
reverse_list( [ X1| X], Y0, Y) :- reverse_list( X, [ X1| Y0], Y).
reverse_list( [], Y, Y).

Back to example 5.3