# Lots of ships in the battleship

We have enough amount of $2$x$2$ grid ships where you can put them on the $14$x$14$ grid battleship board. If this was a real battleship game, you could simply put $49$ of these $2$x$2$ grid ships into the board without any grid shared.

This time, you are going to put the ships one by one shown as the example below. Every time you put a ship, it cannot share more than 1 grid with other ships. That is, it must occupy at least three empty grids. In this case,

At most how many ships can you put into the board?

If this question was asked for $4$x$4$, the answer would be $5$ as shown below:

Here is the wrong way playing the game where you put the green ship, it shares two grid at the same time when you put it:

• So to clarify, it's ok for a ship to share different cells with different ships as long as its at most one cell per other ship? Just like how green is sharing all its 4 cells with 4 different ships? – votbear Apr 2 '18 at 19:07
• You mean the green one is sharing squares with both the red and the yellow one, which both share a difference square with the orange one, so the green one is indirectly sharing two squares with the orange one, which is disallowed? – Glorfindel Apr 2 '18 at 19:56
• when you put the green ship, it shares two grids with other ship or ships, which is not allowed. every time you put a ship on the board, at most one grid can be occupied from other ships. the other 3 or 4 grids needs to be empty while putting the ships. – Oray Apr 2 '18 at 19:59
• Be sure to let the Navy know how you got ships to violate the Pauli Exclusion Principle. – jpmc26 Apr 3 '18 at 2:44
• Nice puzzle! I've posted a follow-up/generalisation; maybe you know the answer? :-) – Rand al'Thor Apr 4 '18 at 0:30

An obvious upper bound is

65, because each new ship after the first must occupy at least empty 3 squares, and $1 + \frac{196 - 4}{3} = 65$.

I couldn't do that well, however, so this might be suboptimal. My best arrangement so far gets to

64 ships:

• I'm 95% certain that your proposed upper bound is not possible, but I'm not sure how to prove it... – ETHproductions Apr 3 '18 at 2:57

15x15 + 14x14 = 421

by

filling the grid completely with 15x15 squares, and then starting from position (1, 1) (zero based) superpositioning the other 14x14?

I haven't got a proof (yet) that this is optimal, but it shouldn't be that hard.

• Right, I think you meant the solution described by NetJohn. I'd argue that the ships in the third layer still share (all four) grids with those in the first layer, but it's your question and you set the rules. – Glorfindel Apr 2 '18 at 19:20

7^2 + 3^2 = 58

The format is:

The stacking pattern is exactly as shown in the "acceptable" version, whereby you form a stack of five (5) then place the next one to the right (or below) of the set you just made, starting another set of five (5), and repeat.

Because 2x2 ships take up 4x4 squares, and the 14x14 box is not evenly divisible by 4x4 squares, there is an L-shaped "strip" of ships that have no overlap. Since a 2x2 ship can't overlap any on those without violated the rules, these ships do not have a stack.

15^2 + 14^2 + ... +2^2 + 1^2 = 1240

The format is:

A pyramid, whereby each dimensions of each level is reduced by one in both X and Y ensuring no more than a single overlap with the square (ship) below.