% 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).