This letter to Dr. Ecco answers the three questions of his puzzle "Lines of Fire," Dennis E. Shasha, Dr.Dobb's Journal, July 1998.
Dennis E. Shasha, Lines of Fire, Dr.Dobb's Journal, July 1998
|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,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. yesThe 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.
oleg-at-pobox.com or oleg-at-okmij.org