I wrote a program to look for minimal submarine shooting strategies.
For N=3, 4, 5, 7, and 8, the minimal number of shots is 2N-1, and
the pattern 0, 0, 0, ..., 0, 1, 2, ..., N-1 (with N 0s) is the
lexicographically earliest solution. For N=6, there's a 10-shot
minimal solution, 0 0 0 1 0 2 3 4 3 5.
The 2N-1 pattern works for N=9, but my program isn't good enough to
show minimality in reasonable time. 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.)
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.
There's also a reflect-time morph, but I can't see how to use it to
make the program faster.
I'm including the program; it's small. The only trick is to retest
the previous escaping sub trajectory on the current shooting strategy.
Rich
------------------
/* submarine3.c */
/* submarine puzzle */
/* see Math-Fun, Oct 2007 */
/* I can assume any solution begins 0,0,D with D=0 or D a divisor of N */
#define N 10
#define Nshots 22
int shots[100];
int recheck, rchi, rchj;
nextshot()
{ int i;
for (i=Nshots-1;i>=0;i--)
{ a: shots[i]++;
if ((i==2) && (N % shots[2])) goto a;
if (shots[i]<N) return;
#if 1
if (i<=4) printf("%d,%d,%d,%d\n",shots[0],shots[1],shots[2],shots[3]);
#endif
shots[i]=0; recheck=0; }; }
int check()
{ int i,j,k;
for (i=0;i<N;i++)
{ for (j=0;j<N;j++)
{ for (k=0;k<Nshots;k++)
{ if (((i+j*k)%N) == shots[k]) break; };
if (k==Nshots) /* start i, velocity j has no hit */
{ rchi=i; rchj=j; recheck=1; return 0; }; };
};
return 1;
}
main()
{ int i,v;
printf("submarine3 N=%d Nshots=%d\n",N,Nshots);
for (i=0;i<100;i++) shots[i]=0;
recheck=0;
for (;;)
{ if (recheck) /* see if last failure is fixed */
{ if (((rchi+rchj*(Nshots-1))%N)!=shots[Nshots-1]) goto nxsh; };
v = check();
if (v) { printf("win N = %d, Nshots = %d\n", N, Nshots);
for (i=0;i<Nshots;i++) printf(" %d",shots[i]);
printf("\n"); exit(); };
nxsh:
nextshot();
if (shots[1]) { printf("lose N = %d, Nshots = %d\n", N, Nshots); exit(); };
};
}
