Lots of ships in the arbitrarily large battleship

Question

This question is inspired by Oray's puzzle Lots of ships in the battleship.

You have an $n\times n$ grid (a battleship board) and a certain number of $2\times2$ squares (ships) to place in the grid. The rules are, quoting from Oray's post complete with illustrative gifs, as follows:

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:

The method in ffao's answer establishes an upper bound of $1+\frac{n^2-4}{3}=\frac{n^2-1}{3}$, the theoretical maximum possible number of ships that could be placed on the board.

For which values of $n$ can this maximum be achieved?

E.g.:

• for $n=4$, the theoretical maximum of $5$ can be achieved as shown in the first gif above;

• for $n=8$, the theoretical maximum of $21$ can be achieved as follows:

  h h i i k k l l
h f f i k j j l
g f b b e e j m
g g b a a e m m
o o c a a d s s
o n c c d d r s
p n n q u r r t
p p q q u u t t

• for $n=14$ (Oray's puzzle), the theoretical maximum of $65$ apparently cannot be achieved (although we haven't seen a proof of this yet).

Is there a general rule for which $n$ it can be achieved and which it can't?

Answer 1

Firstly, instead of overwriting the overlapped square when placing a ship, we shall instead leave it as before, and only ever fill in free space. This does not change the mechanics of the puzzle but makes it easier to see certain important characteristics.

The case for $n=2^k$ can be shown to be possible (for an integer k greater than 0) by induction.

• (For $k = 0, n = 1$: no squares can be placed, $\frac{1^2-1}{3}$ = 0, but this case may not be satisfactory for all users.)

• For $k == 1, n = 2$: only one ship can be placed, $\frac{2^2-1}{3} = 1$.

• Suppose you have a solution for $n=2^k$: you can place it in the corner of a grid which is twice as large, and place a new square in the very centre, covering the very opposite corner of that square, and for the three remaining corners, you can place a copy of the $n=2^k$ solution. This gives you a new solution for $n=2^{k+1}$, which contains 4 times as many squares as the previous solution, plus an additional square.

  Now for the mathematics of this step: $4\times(\frac{k^2-1}{3}) + 1 = \frac{4*k^{2}-4+3}{3} = \frac{(2k)^2-1}{3}$.

Thus, since the first case is true, and the remaining cases can be constructed by using previous cases, each $2^k$ has a minimum solution which that follows that bound.

---

Notice that for each solution, every battleship except the first one that is placed has only 3 free spaces when it is placed, and every cell is filled in. You can chose any ship in the solution as a starting point, as long as each time you place a ship diagonally adjacent to an existing ship There also can't be any closed loops, such as this:

---

An attempted proof of impossiblility for all other cases

A solution cannot exist for an odd $n$, as on any given edge, you can only ever fill in every cell on that edge except for one, as pieces that are adjacent to that edge must take up exactly two unique cells, and cannot overlap.

---

Suppose $n$ is some number that is not a power of two. If even, that grid can be recursively broken down into four quadrants or sub grids of equal size until there are only odd dimensional grids remaining. In order to maximise the amount of ships you need at least one ship on the boundaries, otherwise there would be at least four ships placed where there are 4 free spaces. (Each indivudual quadrant would need a starting ship).

The only way to to do this which would allow for the maximum placed ships is right at the centre, intersecting with all four grids:

Placing a ship anywhere else along the boundaries would result in exposing a 2x1 block to the two touching grids, and I believe would lead to the necessity of forming a loop, which would not be possible to place down following the new or old rules.

---

Now, since all grids that are not powers of two can be broken down into a problem involving an odd by odd dimension grid, and they are not solvable to the upper bound, only the grids that have the same power of two for both dimensions follow the upper bound.

Answer 2

When $n$ is a multiple of three, the optimal value of $\lfloor (n^2-1)/3\rfloor=n^2/3-1$ is achievable.

The odd case

The solution is built out of several 3 x n layers which look like this. Every other layer needs to be reversed so the square jutting out fits into the missing square in the layer below. For the final layer, the black tile is removed and the gray one is replaced with the initial square.

The even case

Break then $n\times n$ grid into an $n/3\times n/3$ grid of $3\times 3$ blocks. Each of these blocks will be filled with some rotation/reflection of the following shape.

Every block has a jut and a gap. The juts and gaps are hooked up to each other to form a Hamiltonian cycle of the $n/3 \times n/3$ grid.

This tiles the grid with trominoes. In order to get a valid battleship placement, expand one of the trominoes in a jut into a square, deleting the trominoe it is "hugging" in order to make room.

Here is an example for the 18 x 18 grid.