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

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.

• I can only get $28$ with four rows of $5$ blank $2$ or $4$ blank $3$ – Ross Millikan Dec 22 '17 at 19:09
• If I place a 5 blank 2 along one outer length, then a 5 on the two adjacent outer lengths and then a four on the one remaining outer length, I get 21. This leaves me with a 4x4 square in the middle, where I can place two 4s. I think this gets me 29 - but I'm not sure. – Matt Dec 22 '17 at 21:08
• Scratch that, I think I can get 30: imgur.com/a/KDiYm – Matt Dec 22 '17 at 21:19

EDIT:

It looks as though you can get 32: • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Stefan4024 Dec 22 '17 at 23:16
• Editted, as recommended. – Matt Dec 22 '17 at 23:36

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.

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.

• There is a lot of structure to this problem which gets lost when you do the graph translation. I strongly suspect the problem here is not NP-complete because of that. – Ross Millikan Dec 25 '17 at 3:46
• Yes, I think you're right. – Robert Israel Dec 25 '17 at 5:55