# Battleship Combinatorics

Imagine a 10x10 battleship grid that we are going to place a 1x5 or 5x1 ship on.

I want to consider the probability distribution for a square containing a ship which I'd then like to plot using software.

Essentially this should look kind of like a discrete Gaussian since

1, the corner squares have very low probability since there are only two possible ships that could touch these squares.

2, on the other hand the squares in the middle will be covered by a large number of ships. For example, square (5,5) seems to have 5 possible vertical and 5 possible horizontal ships if you draw it out. This is also true for squares (5,6), (6,5), (6,6).

In principle, for a 10x10 grid with a ship of length 5, I could conceive going through all 100 squares and explicitly counting the possible ship arrangements.

How would this generalise to an nxn grid with a ship of length m?

• Yep, you're right. I've edited. Thanks. – user11128 Sep 8 at 21:34

Given that a row has $$n$$ squares, and our ship is of length $$m$$ (assuming $$m\leq n$$), say we are interested in the number of horizontal ship positions that go through cell number $$k$$ in that row. By "default", that's $$m$$. However, if we are too close to the edge (either because $$k$$ is small, or because $$n-k$$ is small), then we lose possibilities.
Specifically, if $$k, then of those $$m$$ positions we lose $$m-k$$ possibilities because we can't go past the left edge. And if $$n-k, then we lose $$k+m-n$$ of the $$m$$ possibilities because we can't go past the right edge.
So in the end it looks like this: $$\text{Horizontal ships through cell k} = \cases{ k & if kn-m\\ m & otherwise}$$ You're thinking of it like a Gaussian, but it's actually an isosceles trapezium. Once you add together rows and vertices, the shape becomes a bit more complicated, but all edges and faces are straight and flat, and it's more pyramid-like than Gaussian-like.