%%% Spring 99, CSE 428, Solution of Assignment #9

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercise 1

%%% Definition of the predicate brother(X,Y)
%%% (X is the brother of Y), auxiliary for uncle

brother(X,Y) :- father(Z,X), father(Z,Y), not(X=Y).

%%% (1) Definition of the predicate uncle(X,Y) (X is the uncle of Y)

uncle(X,Y) :- father(Z,Y), brother(Z,X).

%%% Definition of the reflexive closure of the relation ancestor, 
%%% auxiliary for relative

ancestor_ref(X,Y) :- X=Y.
ancestor_ref(X,Y) :- father(X,Z), ancestor_ref(Z,Y).

%%% (2) Definition of the predicate relative(X,Y) (X and Y are relatives)

relative(X,Y) :- ancestor_ref(Z,X), ancestor_ref(Z,Y), not(X=Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercise 2

%%% Definition of prefix(L,K) (L is a prefix of K), auxiliary for sublist

prefix([],_).
prefix([X|L],[X|K]) :- prefix(L,K).

%%% Definition of sublist(L,K)  (L is a sublist of K)

sublist(L,K) :- prefix(L,K).
sublist(L,[_|K]) :- sublist(L,K).

%%% Alternative definition sublist

sublist2(L,K) :- append(_,M,K), append(L,_,M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercise 3

flat([],[]).
flat([L|K],[L|M]) :- not_list(L), flat(K,M).
flat([L|K],M) :- flat(L,L1), flat(K,K1), append(L1,K1,M).
                      
not_list(X) :- not(X=[]), not(X=[_|_]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercise 4: Inefficient solution

queens(N,Pos) :- generate(N,Pos), safe(Pos).

%%% generate(N,Pos) generates an arbitrary permutation of 
%%% the list of integers fron 1 to N

generate(N,Pos) :- list_from_1_to_N(N,L), perm(L,Pos).

list_from_1_to_N(N,L) :- gen(1,N,L).
gen(J,N,[J|L]) :- J<N, J1 is J+1, gen(J1,N,L).
gen(N,N,[N]).

perm([],[]).
perm(L,[X|K]) :- append(L1,[X|L2],L), append(L1,L2,M), perm(M,K).

%%% safe(Pos) checks that the positions are safe, i.e. that 
%%% the queens are not attacking each other. Because of the 
%%% representation of the postions, it is sufficient to check
%%% that there is no check along the diagonals. 

safe(Pos) :- diagonal_safe(1,Pos). 
diagonal_safe(_,[_]).
diagonal_safe(I,[J|L]) :- not(diag_attack(I,J,L)), I1 is I+1,
                          diagonal_safe(I1,L).

diag_attack(I,J,L) :- I2 is I+1, occurs(J1,L,I2,I1), 
                      (J1+I1=:=J+I; J1-I1=:=J-I).

occurs(J1,[J1|_],I,I).
occurs(J1,[_|L],I,I1) :- I2 is I+1, occurs(J1,L,I2,I1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
