Best way to fill a $8\times 8$ board

Question

You have an $8\times 8$ Battleships board and need to place battleships of sizes $1\times 1$, $1\times 2$, $1\times 3$, $1\times 4$, $1\times 5$ on the board to cover as much of the board as possible. The ships cannot touch another ship, even at the corners.

You can place as many of any size as you wish, what is the maximum number of squares you can fill? I believe the answer to this is 30, although not sure how you prove it is the highest.

Also how would you go about solving this for an $n\times n$ board. This probably relates to how you prove the answer for the first part.

Answer 1

EDIT:

It looks as though you can get 32:

Answer 2

Consider the graph with vertices corresponding to placements of a single battleship, and an edge between vertices if the corresponding placements are incompatible (overlapping or touching). Your problem is a Maximum Weighted Independent Set problem on this graph. This is a well-studied but difficult problem for which there are various algorithms. In general it is NP-complete. I don't know if this particular set of instances is NP-complete, but that doesn't inspire confidence that the $n \times n$ problem has an easy solution.

Answer 3

32 is the best you can get. You can replace every $k\times 1$ ship by a $(k+1)\times 2$ rectangle on a $9\times 9$ board, and the ships are legally positioned iff the rectangles don't overlap. If $n$ ships cover $m$ squares, then the rectangles cover $2(m+n)$ squares, so $m+n\le 40$. Hence, if there are at least 8 ships, they cannot cover more than 32 squares. OTOH, 6 ships cover at most 30 squares. If there are 7 ships and at most 4 of them are of size 5, then they cover at most 32 squares. So, consider 5 ships of size 5 placed on the board. At least 3 of them are parallel to each other. We may assume they are horizontal. Each of them is closer to one vertical edge of the board than the other. We may assume two of them are closer to the left edge. Then there cannot be a vertical 5-square ship in any of the 6 leftmost columns, so there are 4 horizontal ships and 1 vertical one. But then there is room for one other ship only.

I haven't checked carefully the details I left out, but I hope the above is an essentially correct sketch.