10
$\begingroup$

A (very peculiar version of the) game of battleship, is played in the following way:

  • The first player places as many ships as he wants on a very large $N \times N$ board. Every ship is of width $1$, and could be of any length up to $N$. Ships can be placed horizontally or vertically, and they must not touch each other (not even diagonally!).

  • The second player the proceeds to guess locations on the board, and the first player tells him whether the location is occupied by a ship or not.

  • The second player ends the game when he's completely sure of the number of ships on the board (not necessarily knowing where exactly are they).

Assume that the board is very large. What is the shortest possible game, in terms of percentage of locations checked on the board?

Example: If the first player does not place any ship on the board, then the second player will have to check 100% of the locations on the board. However, if the first player plays differently the second player can be lucky enough to check less than that.

Disclaimer: I have not proved that my solution is optimal.

$\endgroup$

5 Answers 5

7
$\begingroup$

Apart from the edges, which require a bit more attention (but whose effect can be made arbitrarily small by increasing the board size), I think this pattern will give an exact ship count with only

1/7

of the locations having been guessed:

H = hit
m = miss
. = not attempted

 m . H . m . . . . H . m . . . . H .
 m . . . . . H . . . . . . H . . . .
 . . . H . . . . . . H . . . . . . H
 H . . . . . . H . . . . . . H . . .
 . . . . H . . . . . . H . . . . . m
 . H . . . . . . H . . . . . . H . m
 . . . . . H . . . . . . H . . . . .
 m . H . . . . . . H . . . . . . H .
 m . . . . . H . . . . . . H . . . .
 . . . H . . . . . . H . . . . . . H
 H . . . . . . H . . . . . . H . . .
 . . . . H . . . . . . H . . . . . m
 . H . . . . m . H . . . . m . H . m

Notice in particular, how every hit must be to a distinct ship, and even though there could certainly be more possible hits between these ones, each of those can only be to a ship that has already been hit.

I was hoping the lower bound established in another (since deleted) post could be used to show optimality, but alas, this pattern turned out to be actually better than that lower bound, so I don't really have any optimality claims.


EDIT: Found an even better pattern of hits:

enter image description here

This has one more space between the hits on each row, for a total of

1/8, or 12.5%

of the locations guessed. There are very few locations where an extra ship's existence is redundantly eliminated by more than one shot, so this must be getting pretty close to optimal.

$\endgroup$
3
  • 1
    $\begingroup$ Well done! This is my best solution as well (the second one). My gut tells me that this is the optimal solution, but I don't know how to show it. $\endgroup$ Commented May 10 at 21:54
  • 2
    $\begingroup$ Note that 1/9 is a lower bound since every 3x3 subsquare needs a guess, so you're either there or very close. $\endgroup$ Commented May 10 at 22:10
  • 1
    $\begingroup$ Yeah, if it were somehow possible to show there are no entirely different strategies, it would be pretty easy to show that you can't do a staggered tiling (required for separating each hit to a distinct ship) with non-overlapping 3x3 pieces. $\endgroup$
    – Bass
    Commented May 10 at 22:24
5
$\begingroup$

Player 1 places a 1xN ship on every third row of the board, starting from the second row.

Player 2 can find each of these ships with N-2 guesses, by guessing the whole row except for the ends (since we only need to know the number of ships but not their length). In the process, every other square on the board is ruled out because it is adjacent to an existing ship, and therefore either cannot contain a ship, or continues the same ship.

Generally, we require

ceiling(N/3) * (N-2) guesses.

For a 7x7 board, this requires 15 guesses on 49 spaces, or guessing 30.6% of the board. For a 77x77 board, this requires 1875/5929 spaces, or 31.6% of the board.

In the limit of an arbitrarily large board, the modulo of the board size and the edges become irrelevant, and we effectively just need to hit all of

every third row, guessing 1/3 of the board in total.

$\endgroup$
3
$\begingroup$

Not sure if optimal, but a marked improvement on the baseline:

The first player:

Places a 1x1 ship on every coordinate with odd x and odd y (assuming 0 indexed. An example for a 7x7 grid, with '.' for empty and 'X' for ship:

 .......
 .X.X.X.
 .......
 .X.X.X.
 .......
 .X.X.X.
 .......

Then the second player guesses:

Each space with an odd x or y coordinate (here 'X' denotes a hit, 'x' a miss, and '.' an unguessed space

 .x.x.x.
 xXxXxXx
 .x.x.x.
 xXXXXXx
 .x.x.x.
 xXxXxXx
 .x.x.x.

This finds each ship, determines that they are not connected, and rules out all unguessed spaces as containing ships. We can actually do even better: since we only need to know number of ships, not exact locations or sizes, we can leave out all guesses on the edge, since if they were hits they would be extending existing ships but could not be showing two ships were actually one:

 .......
 .XxXxX.
 .x.x.x.
 .XxXxX.
 .x.x.x.
 .XxXxX.
 .......

This requires us to guess:

(n-1)^2 - (n-5)^2 spaces on an odd board. We have to do a bit of checking on the border if N is even, so we'd be able to do it in n^2 - (n-5)^2 - (n-1) guesses

$\endgroup$
1
  • $\begingroup$ Your formula for the geussed squares doesn't match the pattern. Ignoring the boundary, you pattern requires guessing 3/4 of all spaces. For a nxn board with n^2 spaces on the other hand your formula has the n^2 term cancel out and you get 8n-24 which for n going to infinity converges to 0%. $\endgroup$
    – quarague
    Commented May 12 at 17:02
3
$\begingroup$

I think this improves on StephenTG's answer.

The first player places

(again using a 0-indexed grid) a 1xN ship in columns 1, 4, etc., and then a 1xN ship in column N-1 if needed to avoid a two-column-wide gap at the right. Example for N = 7:

 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 

Then the second player guesses

every cell in these columns and rows 1 through N-2:

 .......
 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 .X..X.X
 .......
 

which identifies all ceiling(N/3) ships and leaves no room for others (again, it doesn't matter whether any ships extend into row 0 and/or row N-1).

This requires:

ceiling(N/3) * (N-2) guesses. I think StephenTG's method actually takes (N-1)^2 - (((N-1)/2 - 1)^2 guesses for odd N, and something similar for even N.

$\endgroup$
3
$\begingroup$

What about this strategy?

 O O O O O O O O
 O S S W O S S W
 O O O O O O O O
 O O O O O O O O
 O S S W O S S W
 O O O O O O O O
 O O O O O O O O
 O S S W O S S W
 

Key:

Here S is a guessed location with a ship, W is a guessed location with water, and O is unguessed.

Therefore

There are six ships shown, but could there be more? I don't see anywhere they could fit in. As $N \to \infty$, you'd need like $N^2/4 + O(N)$ guesses by repeating this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.