Consider the following simpler problem: how many ways are there to place a length-m ship and a length-n ship on a r-by-s grid? I'll assume m and n are distinct. Also, I'll say the grid has r rows and s columns.

The number of ways to place the length-m ship is $(r-m+1)s + (s-m+1)r$. There are $(r-m+1)s$ ways to place the ship vertically (s columns, each having r-m+1 possible placements) and $(s-m+1)r$ ways to place the ship horizontally.

Similarly, the number of ways to place the length-n ship is $(r-n+1)s + (s-n+1)r$.

The total number of ways to place the two ships should be the product of these, except we have to consider the possiblity that the ships could intersect. If the two ships intersect, either:
- one is horizontal and one is vertical, and the intersection is a single square, or
- both have the same orientation, and the two ships lie in the same row or column.
In either case I suspect that the number of configurations with that intersection structure is a polynomial in m, n, r, s.

I conjecture, therefore, that the answer to this problem is a polynomial in m, n, r, s. Let m and n be constants and let r, s vary; then the leading term is $4 r^2 s^2$. Essentially there are $2rs$ ways to place each ship.

Similarly, I suspect that with the actual Battleship fleet on a grid of arbitrary size (ships of length 2, 3, 3, 4, 5 on an n-by-n grid) the number of ways to place the ships is a polynomial with leading term $32n^{10}$, and the actual number of possible placements is much less than this. In particular, the number of ways to place a length-k ship on a 10-by-10 grid is $20(11-k)$; thus the number of placements in actual Battleship is somewhat less than $20^5 \times 9 \times 8 \times 8 \times 7 \times 6 = 77414400000$. If I actually wanted a good approximation of this number, I would place ships at random on a Battleship grid and see with what frequency they don't intersect.

5more comments