0
$\begingroup$

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?

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

The number of different ship positions that go through a given cell is the number of vertical ships plus the number of horizontal ships. So I will focus on the horizontal part, and the vertical part should be completely analogous.

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<m$, then of those $m$ positions we lose $m-k$ possibilities because we can't go past the left edge. And if $n-k<m$, 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 $k<m$\\ n-k & if $k>n-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.

$\endgroup$
  • $\begingroup$ Yeah that's actually annoyingly straightforward. Thanks! $\endgroup$ – user11128 Sep 8 at 21:53
  • 1
    $\begingroup$ I think it's a bit more complicated than just a truncated pyramid, because you have vertical "discretized trapezoidal" faces on each edge of the base square, and in each corner you have facet where the "gradient" is parallel to a diagonal of the square. $\endgroup$ – David K Sep 8 at 22:04
  • 1
    $\begingroup$ @DavidK Yes, of course. I changed the description. $\endgroup$ – Arthur Sep 8 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.