% Solving a Dr. Ecco's puzzle "Lines of Fire", Dennis E. Shasha, DDJ, July 1998
% http://www.ddj.com/ddj/1998/1998_07/SHAS/SHAS.htm
%
% Load the facts
% ['Lines-of-Fire-DB.prl'].
% and check to see they are properly loaded...
% ?- hill_fires(24,X), print(X), nl, fail.
% all_hills(X) generates a list of all hills, 0 through 24.
% It is a deterministic predicate!
all_hills(X) :- all_hills(0,25,[],X),!.
all_hills(I,I,X,X).
all_hills(I,Imax,C,X) :- I1 is I + 1, all_hills(I1,Imax,[I|C],X).
% ?- all_hills(X), print(X), nl.
% safe_from(Hill,Hills,SafeHills)
% Tell which hills from the list Hills can not be fired upon by a hovertank
% that occupies a given Hill.
% This predicate thus filters the list Hills to leave only hills that can not
% be hit from a Hill
% This is a deterministic predicate!
% We could've made it non-deterministic, but then we had to make sure that all
% the branches below are independent (mutually exclusive). It is easier
% to assume that when one branch is followed, the previous branches
% do not apply. It is easier thus to separate all non-determinism
% in a member() predicate.
safe_from(_,[],[]) :- !.
safe_from(Hill,[Hill|Tail],Remaining) :- !, safe_from(Hill,Tail,Remaining).
safe_from(Hill,[X|Tail],Remaining) :-
hill_fires(Hill,X), !, safe_from(Hill,Tail,Remaining).
safe_from(Hill,[X|Y],[X|Remaining]) :- safe_from(Hill,Y,Remaining).
% This is the only _non-deterministic_ predicate
member(X,[X|_]).
member(X,[H|T]) :- member(X,T).
% Find out if there are two hills that dominate the valley (that can hit
% all the other hills)?
% ?- nl, print('Looking for two dominant hills'), nl,
all_hills(Hills),
member(X,Hills), safe_from(X,Hills,Remaining),
member(Y,Hills), safe_from(Y,Remaining,[]),
print([X,Y]),nl.
% ?- nl, print('Looking for three dominant hills'), nl,
all_hills(Hills),
member(X,Hills), safe_from(X,Hills,Remaining),
member(Y,Hills), safe_from(Y,Remaining,R2),
member(Z,Hills), safe_from(Z,R2,[]),
print([X,Y,Z]), nl, fail.
% Just a helpful predicate - lists all hills safe from given ones.
all_safe_from(Hills,SafeHills) :-
all_hills(AllHills), all_safe_from(Hills,AllHills,SafeHills),!.
all_safe_from([],L,L).
all_safe_from([H|T],Hs,Shs) :-
safe_from(H,Hs,Sh1), all_safe_from(T,Sh1,Shs).
% list_length_at_least(L,N). Succeed if the size of L is at least N
list_length_at_least(_,0) :- !.
list_length_at_least([H|T],N) :- N1 is N - 1, list_length_at_least(T,N1).
% Looking for two party dominant hills A and B such that if we take
% A and B first and let the enemy take another hill C, then no matter
% what C is (safe from A and B), the enemy can't hit A and B.
% Moreover, we can take another safe hill D and dominate
% the whole valley.
two_partly_dominant_hills :-
nl, print('Looking for two partly dominant hills'), nl,
all_hills(Hills),
member(A,Hills), safe_from(A,Hills,Remaining),
member(B,Hills), not(A = B), safe_from(B,Remaining,R2),
two_partly_dominant_hills(A,B,R2,R2),
print([A,B]), nl,
fail.
two_partly_dominant_hills(_,_,_,[]) :- !.
two_partly_dominant_hills(A,B,Hills,[C|T]) :- !,
not(hill_fires(C,A)), not(hill_fires(C,B)),
safe_from(C,Hills,R3),
member(D,R3), safe_from(D,R3,[]),
all_safe_from([A,B,D],EnemyHills),
not(list_length_at_least(EnemyHills,5)),
all_safe_from(EnemyHills,SafeForUs),
list_length_at_least(SafeForUs,10),!,
two_partly_dominant_hills(A,B,Hills,T).
% Check the game condition
check_condition(MyHills,EnemyHills,SafeFromEnemy) :- !,
all_safe_from(MyHills,Available_for_enemy),
not(list_length_at_least(Available_for_enemy,6)),
list_length_at_least(SafeFromEnemy,10).
% A deterministic predicate to compute the difference between two lists.
diff(X,[],X) :- !.
diff([],_,[]) :- !.
diff([X|T],[X|T1],Z) :- !, diff(T,T1,Z).
diff([X|T],[_|D],Z) :- member(X,D), !, diff(T,D,Z).
diff([X|T],D,[X|Z]) :- diff(T,D,Z).
% Perform my turn of the game: choose a hill and make sure
% I will eventually win
% (no matter what hills the enemy takes in his turn).
my_turn(MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
member(X,SafeFromEnemy), not(member(X,MyHills)),
safe_from(X,Safe_from_me,NewSafe_from_me),
enemy_turn(NewSafe_from_me,[X|MyHills],
NewSafe_from_me,EnemyHills,SafeFromEnemy),
print_result([X|MyHills],EnemyHills).
enemy_turn([],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :- !.
enemy_turn([X|T],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
member(X,EnemyHills), !,
enemy_turn(T,MyHills,Safe_from_me,EnemyHills,SafeFromEnemy).
enemy_turn([X|T],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
!,
does_not_fire(X,MyHills),
not(list_length_at_least(EnemyHills,5)),
safe_from(X,SafeFromEnemy,NewSafeFromEnemy),
list_length_at_least(NewSafeFromEnemy,10), !,
% nl, print('my turn on:'),print(MyHills), print(X),
my_turn(MyHills,Safe_from_me,[X|EnemyHills],NewSafeFromEnemy), !,
enemy_turn(T,MyHills,Safe_from_me,EnemyHills,SafeFromEnemy).
% does_not_fire(Hill,List) succeeds if Hill does not fire
% on any of the hills in the List
does_not_fire(_,[]) :- !.
does_not_fire(Hill,[Hill|T]) :- !, fail.
does_not_fire(Hill,[H|T]) :- !,
not(hill_fires(Hill,H)), does_not_fire(Hill,T).
print_result([X],EnemyHills) :- !, nl, print([X]), print(EnemyHills).
print_result([X,Y],EnemyHills) :- !, nl, print([X,Y]), print(EnemyHills).
% print_result([X,Y,Z],EnemyHills) :- !, nl, print([X,Y,Z]), print(EnemyHills).
print_result(_,_).
% Find a winning strategy if I'm allowed to take two hills on the first move
main :-
all_hills(Hills),
member(My1,Hills), safe_from(My1,Hills,Remaining),
my_turn([My1],Remaining,[],Hills),
fail.
% Find a winning strategy if I'm allowed to take only one hill
% on the first move
main1 :- all_hills(Hills), my_turn([],Hills,[],Hills).
% Proof that for each distinct X and Y there exist such distinct E1 and E2 that
% - E1 and E2 are distinct from X and Y
% - X does not hit E1 nor E2; Y does not hit E2 nor E2
% and either
% E1 hits X or Y
% E2 hits X or Y
% the list of hills that cannot be hit from E1 and E2 is shorter than 10
%
main_aff :- all_hills(Hills), for_each(Hills,Hills).
for_each([],_).
for_each([X|T],Hills) :- !, for_each(Hills,X,Hills), !, for_each(T,Hills).
for_each([],_,_).
for_each([X|T],X,Hills) :- !, for_each(T,X,Hills).
for_each([Y|T],X,Hills) :- !,
find_two_enemy_hills(X,Y,Hills), !, for_each(T,X,Hills).
find_two_enemy_hills(X,Y,Hills) :-
member(E1,Hills), not(X = E1), not(hill_fires(X,E1)),
% nl, print('E1: '), print(E1),
(hill_fires(E1,X);
hill_fires(E1,Y);
not(E1 = Y), find_two_enemy_hills(X,Y,E1,Hills)).
find_two_enemy_hills(X,Y,E1,Hills) :-
member(E2,Hills), not(E2 = E1), not(E2 = X),
not(E2 = Y), not(hill_fires(X,E2)), not(hill_fires(Y,E2)),
% nl, print('E2: '), print(E2),
(hill_fires(E2,X); hill_fires(E2,Y);
all_safe_from([E1,E2],SafeForUs),
not(list_length_at_least(SafeForUs,10)),
nl, print([X,Y,E1,E2]), print(' '), print(SafeForUs)
).
% unknown(X,trace).