From: "Schroeppel, Richard" <rschroe@sandia.gov>
The 2N-1 pattern works for N=9, but my program isn't good enough to show minimality in reasonable time.
Mine, too (still running).
For N=10, the program hasn't found any solutions so far with 19-22 shots. (This doesn't mean much, since the space is huge.)
So far, for n=10 I have these solutions: n=10, 19 shots: 0 0 0 0 0 0 0 1 1 1 1 2 5 7 8 9 6 4 3 n=10, 18 shots: 0 0 0 0 0 0 1 1 1 1 2 5 7 8 9 6 4 3 n=10, 17 shots: 0 0 0 0 0 1 1 6 1 4 8 5 3 9 2 7 7 (trying for 16 shots now) Interesting similarity between the first two solutions. Almost makes me want to try a search starting from the reverse of any solution...
There are a few obvious morphs of a solution: Increment each shot by a constant C; or increment each shot by the number of the shot; or multiply all shots by anything prime to N. This allows me to restrict the search to begin 0, 0, D, with either D=0 or D divides N.
Thanks for the inspiration & clues. I wrote a C program (longer) http://www.tiac.net/~sw/math-fun/subsolve.c that updates its status as it makes and retracts moves. I use an additional constraint that can cut off searches earlier: If there are m unsunk subs at a given velocity, then at least m additional shots will be needed to sink them. This is a generalization of the observation that you have to shoot at least once at every position to catch all the stationary subs.
From: Scott Huddleston <scotth@ichips.intel.com>
For p an odd prime, I give a solution for the size N = 2p submarine problem in 2N-1 = 4p-1 steps using 2N-2 shots.
Since 17 shots works for n=10, an unused shot may indicate that you can do with less time...or maybe not always. --Steve