17
$\begingroup$

I don't know the answer, I just state that this problem could be interesting.

Best estimate gets the tick.

"Battleships" game field (at least, in the USSR version I used to play) is a 10x10 grid, that has one ship four cells long, two three cells long, three two cells long, and four one-cellers.

You can place the ships on the board (as long as they don't touch even by the angles). Then you can shoot into the board, but only miss the ships. The 'independent audience' will only see the result of your shots (which are all misses), and not know the ships location (but know the rules). You cannot shoot into one cell twice.

Now, the optimization problems are those:

Sniper

What is the minimum amount of shots required to prove that the ships are located exactly as they are located (i.e., for every cell occupied by ship you can prove conclusively that it really is) ?

Ninja

What is the maximum amount of shots you can make, so that you cannot prove that any given cell is occupied by ship (i.e., for every cell that is not yet shot you can set an example of game field, where it is not occupied)?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I don't think I've ever seen a version of this with 1-cell ships. They generally range from 2-5. 1-cell ships would make the game pretty tedious since they could be literally anywhere and you'd have no way to tell if you're even close to them. Now that I think of it, they also didn't have a rule against placing ships adjacent, so that does alter things somewhat. $\endgroup$
    – Darrel Hoffman
    Commented Feb 18, 2021 at 21:03
  • 1
    $\begingroup$ @DarrelHoffman This version is generally played in Russia and other ex-USSR countries, where the American version with ships sized 2-5 is virtually unknown. $\endgroup$
    – trolley813
    Commented Feb 19, 2021 at 6:40
  • 2
    $\begingroup$ Can confirm, I've also always played OP's version (Poland, so not really ex-USSR, but close enough). The key to strategy is that once you sink a ship, you can mark all fields around it as blanks without shooting at them - but it's primarily a luck-based game, with some aspects of "put the ship in the most unlikely place" mind-games. $\endgroup$
    – Maciej Stachowski
    Commented Feb 19, 2021 at 10:48
  • 1
    $\begingroup$ By saying "minimum" and "maximum", do you mean for all possible and valid situations, or for a possible, valid and specific situation? $\endgroup$
    – atzlt
    Commented Feb 19, 2021 at 14:19
  • $\begingroup$ @SketchySketch I do mean for a possible, valid and specific situation. I thought I made it clear with "upi can place ships on board", and "you can only miss the ships". So, in the metaphor "Ninja" ships are somehow "wiggling" under your missing shots, always having an uncertain place, and in "Sniper" you "pin" this uncertainty. $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:47

5 Answers 5

Reset to default
8
$\begingroup$

For Ninja, I could get

77

For example:

 . . . . x . x . x .
 x x x x x x x x x x
 . . . . x . . x . .
 x x x x x x x x x x
 . . . x . . . x . .
 x x x x x x x x x x
 x x x x x x x x x x
 x x x x x x x x x x
 x x x x x x x x x x
 x x x x x x x x x x

This allows the following arrangements of ships:

A simple arrangement to leave any square of either of the size 4 gaps unoccupied (the remaining patterns will also leave at least one square of one of the size 4 gaps unoccupied). 

 4 4 4 4 x 1 x 1 x 1
 x x x x x x x x x x
 1 . . . x 2 2 x 2 2
 x x x x x x x x x x
 3 3 3 x 3 3 3 x 2 2

Any two squares of a size 3 gap unoccupied: 

 4 4 4 4 x 1 x 1 x 1
 x x x x x x x x x x
 3 3 3 . x 2 2 x 2 2
 x x x x x x x x x x
 3 3 3 x . . 1 x 2 2

One size-2 gap unoccupied. 

 4 4 4 4 x 1 x 1 x 1
 x x x x x x x x x x
 1 . 2 2 x 2 2 x 2 2
 x x x x x x x x x x
 3 3 3 x 3 3 3 x . .

Any one of the size-1 gaps unoccupied. 

 4 4 4 4 x . x 1 x 1
 x x x x x x x x x x
 1 . 1 . x 2 2 x 2 2
 x x x x x x x x x x
 3 3 3 x 3 3 3 x 2 2

There is also a near-solution for

78, by removing one of the size-1 gaps, but this fails because then both the remaining size-1 gaps must necessarily be occupied; or by converting one of the size-2 gaps to a size-1 gap, which fails because the middle square of both size 3 gaps must necessarily be occupied.

For Sniper, I could get a few improvements on the previous best answer posted, of which the best is:

46 45 44 43 42

The following pattern of missed shots can work for this total:

 . x . . . x . . x .
 . . . x . . . x . x
 . . x . x . x . x .
 x . . . x x . x . x
 . . . x . . x . x x
 . x . . x x . . x .
 x . x x . x . x . .
 . x x . x . x . . x
 x . . x x . x x . .
 . x x . . x . . x .

Placing the size-4 ship:

It fits trivially into the only size-4 gap. 

 o x o . . x . . x .
 o 4 o x . . . x . x
 o 4 x . x . x . x .
 x 4 o . x x . x . x
 o 4 o x . . x . x x
 o x o . x x . . x .
 x . x x . x . x . .
 . x x . x . x . . x
 x . . x x . x x . .
 . x x . . x . . x .

Placing the size-3 ships:

They fit trivially into the only size-3 gaps. 

 o x o o o x o o x .
 o 4 o x 3 3 3 x . x
 o 4 x o x o x o x .
 x 4 o . x x . x . x
 o 4 o x . . x . x x
 o x o . x x . o x o
 x . x x . x . x 3 o
 . x x . x . x o 3 x
 x . . x x . x x 3 o
 . x x . . x . o x o

Placing the size-2 ships:

There are 5 size-2 dominoes remaining, but as they are chained together there is only one way to fill 3 (same idea as Jaap Scherphuis answer) 

 o x o o o x o o x .
 o 4 o x 3 3 3 x . x
 o 4 x o x o x o x .
 x 4 o o x x o x . x
 o 4 o x 2 2 x . x x
 o x o o x x o o x o
 x . x x o x o x 3 o
 o x x o x 2 x o 3 x
 x 2 2 x x 2 x x 3 o
 o x x o o x o o x o

Placing the size-1 ships:

There are 6 gaps remaining, but as 5 of them are chained together there is only one way to fill 4: 

 o x o o o x o o x 1
 o 4 o x 3 3 3 x . x
 o 4 x o x o x o x 1
 x 4 o o x x o x . x
 o 4 o x 2 2 x 1 x x
 o x o o x x o o x o
 x 1 x x o x o x 3 o
 o x x o x 2 x o 3 x
 x 2 2 x x 2 x x 3 o
 o x x o o x o o x o

A lower bound for sniper

It will not be possible to have a solution for sniper challenge that uses fewer than

41 shots

This is because

  • At least 4 shots are required within the 3x6 region around the size-4 ship to prevent it being in any other place within that region (one at each "end" of the ship, and one to break up each of the 1x6 regions alongside the ship).

  • Similarly, at least 5 shots are required within the 3x5 region around each size-3 ship, and at least 6 shots are required within the 3x4 region around each size-2 ship, to prevent each being in any other place or orientation within that region.

  • After the locations of all other ships are forced, every square not adjacent to a ship must have a missed shot (otherwise a size-1 ship could be moved there). To minimise the number of shots at this stage, the regions blocked off by all ships of size-2 or larger must be non-overlapping.

  • The size-1 ships can only block off a maximum of 3 diagonally adjacent cells in total - otherwise the 4 ships could be moved to the 4 squares that are adjacent to the intended locations of the ships.

  • totalling this, we require a minimum of $4 + 2*5 + 3*6 = 32$ shots within the regions around the size-2 and larger ships, which together block off a maximum of $3*6 + 2*3*5 + 3*3*4 = 84$ squares. A maximum of 7 squares can be left not blocked off (to contain the size 1 ships) so $100 - 84 - 7 = 9$ more shots are required, for a total of $32 + 9 = 41$.

For a provably optimal result we would need

Either to prove that 42 shots are necessary, or that 41 shots are sufficient. The only way to improve on my current best solution would be to have a single chain of 7 diagonally-linked empty squares at the final step, whilst still minimising the number of shots in the regions around the other ships. This also places massive constraints on how the regions can be placed alongside each other so that no extra shots are needed within the regions... I doubt 41 is possible but I've not proved it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Legitness checked (x/77) $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:30
  • $\begingroup$ Could you remove a 2 instead of 1? $\endgroup$
    – Thomas Blue
    Commented Feb 20, 2021 at 9:46
  • $\begingroup$ @ThomasBlue No, because rot13(gurer vf gura ab jnl gb yrnir gur zvqqyr fdhner bs n fvmr guerr tnc habpphcvrq) - updated answer to clarify this $\endgroup$
    – Steve
    Commented Feb 22, 2021 at 10:11
10
$\begingroup$

For the sniper question I think here is an answer of only

47 shots.

The shots are:

 . x x . x x . x . x
 x . . x x x x . . x
 . x x . x x . . x .
 . x . x x . x . . x
 x . x x . x . x . .
 x . x x . x . x x x
 . x . . x . x . . x
 . . x . . x . . x .
 x . . . . x x . . x
 . . . x . . . x . .

There is only one way to place the size-4 ship between these shots:

 . x x . x x . x . x
 x . . x x x x . . x
 . x x . x x . . x .
 . x . x x . x . . x
 x . x x . x . x . .
 x . x x . x . x x x
 . x . . x . x . . x
 o o x o o x . . x .
 x 4 4 4 4 x x . . x
 o o o x o o . x . .

Then only one way to place the size-3 ships:

 . x x . x x o x o x
 x . . x x x x 3 o x
 . x x . x x o 3 x .
 . x . x x . x 3 o x
 x . x x . x o x o .
 x . x x . x o x x x
 . x . . x . x 3 o x
 o o x o o x o 3 x .
 x 4 4 4 4 x x 3 o x
 o o o x o o o x o .

Then only one way to place the three size-2 ships:

There is a chain of 5 domino-sized spaces, and the 3 ships cannot be adjacent, so they must alternate along that chain. 

 o x x o x x o x o x
 x 2 2 x x x x 3 o x
 o x x o x x o 3 x .
 o x o x x o x 3 o x
 x 2 x x 2 x o x o .
 x 2 x x 2 x o x x x
 o x o o x o x 3 o x
 o o x o o x o 3 x .
 x 4 4 4 4 x x 3 o x
 o o o x o o o x o .

And that leaves only 4 available spots for the small ships.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't think it's right; what if you exactly shot one ship? Then all your following strategies will be broken. In my opinion the question asked for the least shots for every possible and valid situation, not specific. I think I'll ask for clarification in OP. $\endgroup$
    – atzlt
    Commented Feb 19, 2021 at 14:15
  • 1
    $\begingroup$ @SketchySketch I think that whatever pattern you choose of 98 shots, there is an arrangement of ships where you have only one size-1 ship left that can be at either one of the unshot cells. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 19, 2021 at 14:57
  • $\begingroup$ Didn't count the x's, but otherwise it looks legit. Also, the 98 shots argument IS correct, assuming we don't get information on hit ships in return, as we do in the actual game. Anyways, Jaap's understanding of Sniper challenge is correct. $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:43
7
$\begingroup$

For Ninja it's

76

because

you can shoot all squares except the 20 which contain the actual ships and the 1x4 rectangle somewhere else (being nonadjacent to the ships, of course). Now, for each of the 20 squares with the ships you can "relocate" the ship occupying that square to the "reserve" 1x4 rectangle (which can fit any ship), making a configuration with that square empty, so you cannot be 100% sure that this square is occupied.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Legit 76 ninja. $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:38
5
$\begingroup$

The answers are, unfortunately,

80 and 79.

Why?

Because the ships in total cover twenty cells.
Sniper: The sixteen cells holding the multi-cell ships can certainly be determined with fewer than eighty shots, but if more than four cells remain to hold the one-cell ships then their locations cannot be determined - it's trivial to arrange them so that any particular cell is unoccupied.
Ninja: Fire into all squares not inside a given 3x7 rectangle. For any given cell inside the 3x7 rectangle, it is possible to arrange the ships as follows:
Fill the two seven-cell rows not containing the chosen cell with 3+4 and 3+2+2-cell ships.
Place a 2-cell ship in the last row then fill the remaining cells with the one-cell ships.
Therefore, the occupied cells cannot be determined.

[EDIT: The above is all wrong, because I missed the part about ships being nonadjacent.]

With that settled, I can get a score for Ninja of at least

seventy: Take three nonadjacent rows, and fire into every square not in those rows.
For any cell in the three remaining rows, place the ships as follows:
Fill the rows not containing the chosen cell with 4+2+1 and 3+2+2-cell ships.
In the remaining row, the chosen cell will be at least five cells from one of the ends - in this longer space, place the remaining 3-cell ship and as many 1-cell ships as will fit. The remaining 1-cell ships will fit on the other side of the chosen cell.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Legit Ninja (70), although I think your logic can be pushed a bit further, as your ship bays look not that tight. $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:37
4
$\begingroup$

Sniper:

It's 61. enter image description here

Ninja:

It's 70, because you can add one to the number of each type of ship, which cover 30 squares together, leaving 70 to miss.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Ah, missed your edit. Good job! $\endgroup$
    – AxiomaticSystem
    Commented Feb 18, 2021 at 15:42
  • $\begingroup$ Checked legitness for Ninja (70 legit), can't quite get it for sniper. The example to present should be a board with 64 misses, yet your last board has 76 cyan cells? $\endgroup$
    – Thomas Blue
    Commented Feb 19, 2021 at 18:34

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.