Shortest battleship game, to find the ships

This is a variant of this riddle.

A (somewhat 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 by 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 then 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, and their sizes and exact locations.

What is the shortest possible game, in terms of percentage of locations checked on the board? Show that the solution is optimal (assume that the board is huge and give your answer as a fraction of the locations in the board that should be checked).

A quick baseline answer: it is possible to guess

1/5

of all locations on the grid to find the locations of every ship fragment.

It uses the fact that

a hit ensures that its four diagonally adjacent cells do not contain a ship fragment

and there are at least two ways to achieve it:

. H . . . . H . . .
. . . H . . . . H .
H . . . . H . . . .
. . H . . . . H . .
. . . . H . . . . H

This one is similar to the infinite periodic tiling of X pentomino.

. . H H . . . . . . . . H H
. . . . . H H . . . . . . .
. . . . . . . . H H . . . .
. H H . . . . . . . . H H .
. . . . H H . . . . . . . .
. . . . . . . H H . . . . .
H H . . . . . . . . H H . .
. . . H H . . . . . . . . H
. . . . . . H H . . . . . .

This one is a periodic tiling of the 10-mino formed by attaching two X-shapes together:

x x x x
. H H .
x x x x

After some more thought, I believe this is optimal because

a cell orthogonally adjacent to a hit cannot be determined unless it is itself a hit, a miss, or "crossed out" by a diagonally adjacent hit. This is actually a nontrivial statement, and possibly requires a thorough case-by-case analysis of every possible arrangement of hits around a fixed hit.

• For the second pattern, can you take the strips going down and right, and put more vertical space in between each pair?
– xnor
Commented May 13 at 2:52
• @xnor I made a mistake drawing the pattern. Should be fixed now. Commented May 13 at 3:16
• This finds all the ships but does not find sizes. Now you need to show what density is needed to finish the job in the worst case of ship density. One challenging case is alternate rows almost filled. Commented May 13 at 4:59
• @RossMillikan I was also confused a bit at first, but determining from the linked puzzle, OP wants the most optimistic scenarios. Otherwise the answer to both puzzles is "you need to try every single cell". Commented May 13 at 5:33

$$\frac{1}{5}$$ (asymptotically, that is).

Here is the reasoning:

For every play we make, we are able to place one of two tiles on the board, either an $$X$$-tile if we hit, namely

 X . X
. X .
X . X 

or a single point ($$P$$-tile) if we miss.

I now claim that

the collection of tiles we placed in any successful game must be a covering of the entire board. Indeed, if some square was not covered by them, we would neither have checked it or got a hit on a square diagonally adjacent. Thus, both possible states of that square would be consistent with our data.

Hence,

finding an optimal solution is at least as difficult as finding a minimal covering of the board with these tiles. Since the maximal size of any tile is $$5$$, we can clearly never achieve a covering that improves on the ratio $$\frac{1}{5}$$.

Actually, it is even clear that

this ratio can never be achieved on a finite rectangular grid. To do that we would have to place only non-overlapping $$X$$-tiles. But this is impossible, which can be easily seen by considering any $$2\times 2$$ in the corner of a board: This space can not be covered by just two tiles, and covering it with three necessarily creates an overlap. Thus, we either have to employ some $$P$$-tiles or allow some overlap. Either way, the perfect ratio is not achievable. (I have not figured out the optimal ratio for any finite board - this is likely very annoying to do.)

But since

the hit patterns in Bubblers answer give a non-overlapping covering that only needs to use $$P$$-tiles on the edges of the board, we can conclude that the infimum of the best ratios for finite boards is actually $$\frac{1}{5}$$.

• I think this works for isolated hits, but doesn't yet account for the possibility of two or more hits in a line eliminating orthogonally adjacent tiles that would create a crooked battleship that's not a straight line. However, I think this should be fine because length $n$ eliminates $3n+4$ tiles for $n\geq 2$, a ratio no better than $1/5$.
– xnor
Commented May 13 at 16:58
• I'm not sure I understand what you're getting at. Are crooked ships allowed? Commented May 14 at 9:14