Many solutions to the "Lines of Fire"

 

This letter to Dr. Ecco answers the three questions of his puzzle "Lines of Fire," Dennis E. Shasha, Dr.Dobb's Journal, July 1998.

References
 

Lines-of-Fire.prl [7K]
A Prolog source code that was used to solve the puzzle. The letter below talks about this code and solutions it found.

Lines-of-Fire-DB.prl [5K]
A database of facts which are a premise of the puzzle: which hills can fire upon each other.

Dennis E. Shasha, Lines of Fire, Dr.Dobb's Journal, July 1998
The text of the puzzle itself.
 

Version
 The current version is 1.0, July 7, 1998.

 

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.
The result was:
	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]
This shows that if Col. Solo takes hills #24 and #5, no matter what the enemy picks (for example, hills #22, #18, #16 or #6), he can always find a safe hill that together with hills #24 and #5 dominates the valley. This hill along with #24 and #5 thus leaves no more than 5 hills for the enemy to land on, and the enemy from those hills can't hit more than 25-10=15 hills. Another solution is #5 and #14 (which was printed in your answer, DDJ August 1998). It took less than 10 seconds to compute these solutions, on my PowerMac 8500/132, OpenProlog 1.0.3d33.

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
The predicate find_two_enemy_hills(X,Y,Hills) in the source code above prints out this strategy for each two initial moves that Col. Solo could possibly make.

 


Last updated August 7, 1998

This site's top page is http://okmij.org/ftp/

oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!