For a n X n board the minimum number of ships in the fleet so that no new ship can be added is \[ \big(\frac{n}{3}\big)^2\quad if\quad3|n\] \[ \big(\lfloor\frac{n}{3}\rfloor+1\big)^2\quad if \quad3\nmid n\] We start with observing that a 3 X 3 board requires exactly one ship in the fleet at the centre. Hence the case when $ 3|n$ is straightforward. When $ n=3k+1$ add an extra column to $ 3k$ board.Keeping the ships of the $ 3k$ board intact, we need to add exactly $ 3k+1$ ships. This suffices for $ 3k+2$ board too. If we rearrange the ships in the $ 3k$ board, we still end up requiring at least $ 2k+1$ ships. Consider a 3(m+1)+1 X 3(m+1)+1 board,rearrangement of the ships in the 3m X 3m (top left corner) would not yield to a configuration where one needs to add lesser ships ( than $ 2(m+1)+1$ ships) as the bound is tight in 3m X 3m board(this comes inductively by the bound in 3 X 3 board). We are left with a intersecting vertical and horizontal strips that can be broken down into $ m$ 4 X 3 (or 3 X 4) boards and one 4 x 4 board. It can seen that both 4 X 3 and 4 X 4 boards are tight bounds of 2 and 4 respectively, the 7 X 4 board has the tight bound of 7 and the result follows.