% member relation is true if X occurs in list L

%member( X, [X | _] ) :- write('TRUE'), !.
%member( X, [_ | Tail] ) :-
%  member( X, Tail ).

%concatenate two lists together
concat( [], L, L ).
concat( [X | L1], L2, [X | L3] ) :-
  concat( L1, L2, L3 ).

% concat( [a, b], [c, d], R )
% ==> concat( [a | [b]], [c, d], [a | R1] )
% ====> concat( [b | []], [c, d], [b | R2] )
% ======> concat( [], [c, d], [c, d] )
% ======>     R2 is [c, d]
% ====>       R1 is [b | R2] ... or [b, c, d]
% ==>         R  is [a | R1] ... or [a, b, c, d]

% redeclare member relation using concat
%member( X, L ) :-
%  concat( _, [X | _], L ).

% shift 

shift( [Head | Tail], S ) :-
  concat( Tail, [Head], S ).

% add X to head of List L
%add( X, L, L1 ) :-
%  L1 = [X | L].

%add( X, L, [X | L] ).

% add X to head to List L avoiding duplicates
% use cut ! to stop inference engine from matching
%   both relations
% also note ! always is TRUE
%addnodup( X, L, L1 ) :-
%  member( X, L ), !, L1 = L.
%addnodup( X, L, [X | L] ).

%addnodup( X, L, L1 ) :-
%  member( X, L ) -> L1 = L
%  ;
%  L1 = [X | L].

addnodup( X, L, L1 ) :-
  member( X, L ), !, L1 = L
  ;
  L1 = [X | L].


% delete X from list L
%del( X, [X | Tail], Tail ).
%del( X, [Y | Tail], [Y | Tail1] ) :-
%  del( X, Tail, Tail1 ).


%member( X, [X | _] ).
%member( X, [_ | Tail] ) :-
%  member( X, Tail ).
%del( X, L, R ) :-
%  member( X, L ), !, del2( X, L, R )
%  ;
%  R = L.
%del2( X, [X | Tail], Tail ) :- !.
%del2( X, [Y | Tail], [Y | Tail1] ) :-
%  del2( X, Tail, Tail1 ).


del( X, [X | Tail], Tail ).
del( X, [Y | Tail], [Y | Tail1] ) :-
  del( X, Tail, Tail1 ).

% insert X in list L
insert( X, L, R ) :-
  del( X, R, L ).

permutation( [], [] ).
permutation( [X | L], P ) :-
  permutation( L, L1 ),
  insert( X, L1, P ).


% [1:3, 2:1, 3:4, 4:2]
% n queens problem -- Attempt #1
queens( R ) :-
  permutation( [1, 2, 3, 4, 5, 6, 7, 8], Q ), 
  write('Permutation '), write(Q), nl, 
  q( Q, R, 1 ), 
  write('Testing '), write(R), nl, 
  nothreat(R).

nothreat( [] ).
nothreat( [Head | Tail] ) :-
  nothreat( Head, Tail ), 
  nothreat( Tail ).

% E1 =\= E2 is true if arithmetic expr E1 and E2 are not equal
nothreat( _, [] ).
nothreat( X:Y, [X1:Y1 | Tail] ) :-
  Y =\= Y1, 
  Y1-Y =\= X1-X, 
  Y1-Y =\= X-X1, 
  nothreat( X:Y, Tail ).

q( _, [], 9 ).
q( [X | Tail], [N:X | R], N ) :-
  N1 is N+1, 
  q( Tail, R, N1 ).