8
$\begingroup$

Two guys are playing regular battleship game with only one Aircraft Carrier, with dimensions $5\times1$. Their table is regular $10\times10$ Battleship game grid board.

enter image description here

One guy places his Aircraft Carrier somewhere, what is the minimum number of shots to guarantee to sink the opponent's Aircraft Carrier for the other guy?

$\endgroup$
  • 1
    $\begingroup$ Do you mean the maximum with an optimal strategy? $\endgroup$ – boboquack Oct 1 '17 at 8:16
  • $\begingroup$ @boboquack fixed it with "to guarantee". $\endgroup$ – Oray Oct 1 '17 at 8:17
7
$\begingroup$

(Ever more scan patterns.)

As this variation of Battleship has no other ships, the Aircraft Carrier can always be sunk in...

...25 shots or fewer, in two stages.

1.  The 5-cell-long ship is found by 20 shots taken in a scan pattern that leaves no gaps longer than 4 cells and is discontinued after the first hit.

2.  The ship is sunk by 4 to 6 follow-up shots. If the ship remains untouched until the 20th (last) scan shot, only 4 or 5 follow-up shots will be needed because that last scan shot is at the edge.

Here is a scan pattern and the counts of follow-up shots that could ensue from each possible scan hit. Scan shots are ordered to produce the smallest average number of total shots, 13.633, that sink a ship placed randomly in any of its 120 possible positions.
A.numbered


Can a smaller number of shots always be sufficient?

No.   See a neat and clear proof by Miles.


Five scan patterns (and their equivalents) are most efficient.

best-averages


Five more scan patterns guarantee the same maximum of shots but slightly less efficiently.

worse-averages


The four central cells can potentially require the most follow-up shots, 7, while other cells require at most 6 follow-ups and edge cells at most 5. The last scan displayed above labels three cells, A, H and T, as examples whose follow-up shots may, as laid out below, be diagrammed and counted. Lowercase letters, “a” through “f,” signify positions and order of follow-up shots that may be needed to determine a ship’s position. Dark cells indicate known or deduced cells of the ship.

A-H-T

Case studies such as those create a follow-up-shot-count chart that was used to calculate scan efficiencies.

          chart

$\endgroup$
  • $\begingroup$ What if it is in the middle of the board? I assume you start your pattern from the centre so that those more awkward ones are found earlier on but I'm not clear that this would guarantee doing it in 25 or less... eg if the battleship intersected your first pattern in the third column sixth row could it not then take more guesses if that spot was guessed too late in your sequence? $\endgroup$ – Chris Oct 1 '17 at 23:11
  • $\begingroup$ Taht's being covered in the revision too, @Chris. The worst case should take at most 7 follow-up guesses but that will never happen on the last two (or more, actually) initial guesses. $\endgroup$ – humn Oct 1 '17 at 23:36
  • 1
    $\begingroup$ The revision will have eyefuls devoted to some situations like that, I'll @Chris you when it's up. On a larger sea (11x11 might be large enough) the worst case would take 8 follow-up guesses. $\endgroup$ – humn Oct 1 '17 at 23:55
  • 1
    $\begingroup$ Here's the revision as advertised, @Chris, though the analysis of cell A at the end of this revision makes me now think that 7 follow-up shots are sufficient on any size board. (The main solution here never requires more than 6 follow-ups.) $\endgroup$ – humn Oct 4 '17 at 5:59
  • 2
    $\begingroup$ @humn you'll never need more than 7 follow-up shots. Once you get a hit just keep guessing in one of the four directions until you get a miss, then try another direction. You'll sink the ship before you miss in all four direction. So 3 misses plus 4 more hits is 7. $\endgroup$ – Kruga Oct 4 '17 at 7:48
7
$\begingroup$

battleship20
which is in 20, which is 2 per column and therefore minimal.

We can leave one corner to last, in that if we have a hit before this, we need 7 more shots, but have only used at most 18. If we don't hit until the last corner, we have one miss and 4 hits: Total: 25

$\endgroup$
6
$\begingroup$

Other answers have shown algorithms to sink the aircraft carrier in at most

25

shots. Here is a proof that no algorithm can achieve a lower maximum number of shots.

Initially, consider a $5 \times 5$ grid. There are 10 possible placements of the ship onto the grid: 5 horizontally, filling each row, and 5 vertically, filling each column. Each grid square touches exactly 2 possible ship placements, one horizontal and one vertical. In order to find the ship, up to 5 shots are required, as each miss can eliminate only two possibilities, with each shot in a unique row and column in order to touch every possible ship location. Once the ship is hit, the orientation of the ship is still unknown (since there are no other shots in the row or column of the "hit"), so in order to sink it, up to 5 additional shots are required: 4 to sink it, plus an additional possible miss if we guess the wrong direction initially.

Now consider a $10 \times 10$ grid. We can restrict the placement of the ship so that it lies entirely in a single quadrant, and doesn't cross one of the center lines of the grid—in other words, we repeat the $5 \times 5$ case once in each dimension, so that there are 40 possible ship locations, and each square still touches exactly 2 possible ship locations. Even with the restricted ship placement, an optimal algorithm must spend up to 20 shots to guarantee that it hits the ship once, and once it does, as with the $5 \times 5$ grid, it must spend up to 5 shots to sink it. Because 24 shots is insufficient to guarantee sinking the ship when we restrict the ship placement in this way, it's also insufficient if the ship could be placed anywhere else on the grid, meaning that algorithms that guarantee that the ship is sunk in 25 moves or less are optimal.

$\endgroup$
  • $\begingroup$ Very clean, to be cited in my solution, thank you Miles! $\endgroup$ – humn Oct 4 '17 at 11:04
2
$\begingroup$

26 is the minimum I've come up with.

As others have shows, using an ideal strategy, it would take 20 shots to find the battleship. However, it would take up to 3 shots to verify the direction, and an additional 3 to sink the battleship, as shown below, with blue as a miss, and red as a hit.

This also applies for other positioning along row J or if the battleship is last discovered to be in column 6.


enter image description here

$\endgroup$
  • 1
    $\begingroup$ Trick is to leave A10 and J1 as the last of the 20 moves. If so, if we need 20 moves to get the first hit we only need 2 moves to verify direction. $\endgroup$ – Taemyr Oct 1 '17 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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