Many solutions to the "Lines of Fire"

Dear Dr. Ecco:

If Col. Solo can take three hills initially (which allow him to completely dominate the valley, that is, fire on all the other hills), he's got plenty of choice. For example, he can take hills [24,23,13] or [24,23,6] or [24,15,5] or [24,15,4] or [24,14,5] or [24,13,23] or [24,13,5] or [24,13,4] or [24,6,23] or [24,6,4] or [24,5,15] or [24,5,14] or [24,5,13] or [24,4,15] or [24,4,13] or [24,4,6]. These are the solutions if the first hill is #24. There are many solutions if the first hill taken is #23, or #20, etc. There are too many solutions to show in this message. The following Prolog predicate in the code Lines-of-Fire.prl above prints them all:

?- 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 out of curiosity, I wanted to see if there are two dominant 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.

	Looking for two dominant hills
	no

The second question was about Col. Solo's winning strategy if he can take initially two hills. Here's what my code printed:

Looking for two partly dominant hills
[24,5]
[14,5]
[5,24]
[5,14]

Note, the condition above is stronger than required: we have actually asked if the game is decided only after three our moves (with one move from the enemy). If we allow longer play (longer analyses), more solutions are possible. For example, Col. Solo can first land on hills #16 and #24, or #15 and #24, or #14 and #24, or #6 and #24, or #4 and #24, or #20 and #23, etc. There are too many solutions: I got tired watching my program's spitting them, and terminated it. I can let the program finish however and print all the solutions if necessary. In any case, if Col. Solo takes for example hills #16 and #24, he has a winning strategy no matter what hills the enemy can take. This strategy may require more than three moves to have the game decided, yet the result is just the same: the enemy can take no more than 5 hills, from which it can fire upon no more than 25-10=15 hills. Col. Solo, on the other hand, can fire on at least 25-5=20 hills from (some) of the 10 hills he has landed on.

What if Col. Solo is allowed to take only one hill on the first move? This was the third question in your puzzle. Is there a single hill that guarantees the victory? The answer is no. After some 5 minutes on my PowerMac 8500/132, the main1 predicate considered all combinations and said no. Thus there is no single hill Col. Solo can take and guarantee the victory regardless of enemy moves.

I felt the negative result was not very satisfactory; I wanted to get something affirmative. Thus I set out to prove a reverse theorem. Actually, a stronger version of it: no matter what Col. Solo's the first and the second moves are, his opponent can always leave fewer than 10 hills unhit in only two moves. Thus if Col. Solo is allowed to take only one hill on the first move, the enemy has a two-step winning strategy, as the following predicate shows:

	main_aff.
	yes

Last updated August 7, 1998