Battleship Permutations

Question

Using the game of Battleship as an example, is there a general solution for determining the number of arrangements of a given set of 1xN rectangles on a X by Y grid?

Example: In Battleship, each player has a 10x10 grid on which they must place each of the following rectangular 1xN ships which may not overlap or be placed diagonally:

• 1x5-square "carrier"
• 1x4-square "battleship"
• 1x3-square "submarine"
• 1x3-square "cruiser"
• 1x2-square "destroyer"

A) How would one calculate the number of arrangements for this example that use each "ship" exactly once?
B) What is the general solution for a grid of height Y and width X, and a given set of 1xN "ships"?

Answer 1

1) Consider a fixed list of boats in the limit of a large grid. This is a model of a battle in the open Pacific, you know; it's not supposed to be Pearl Harbor. Then the inclusion-exclusion formula is much faster than a back-tracking search. Count all of the arrangements of ships, then add or subtract a term for each pattern of intersection when the ships have had an accident. Each term is a product of squares. Indeed, it is an explicit polynomial in the grid size.

2) As Gjergji says, Kasteleyn's method is only for perfect matchings. Even if the ships were all PT boats, you would not have a determinant formula unless they covered the whole grid. If you truly do want to count saturated traffic jams of PT boats, Kasteleyn himself evaluated the determinant for rectangles and established a trigonometric product formula.

3) If anyone wants to define a generalized $q$-Battleship with an interpretation over $\mathbb{F}_q$ — no, thank you! (You can make the product formula for each term work, but don't bother.)

Answer 2

I've recently done some coding to try and solve this problem, and I've arrived at the answer

30,093,975,536

where we consider the two length 3 ships as distinct. I can't say that I am certain of the result [edit: having received confirmation by a second party, I believe that I can say that I am certain now], and you can find my (python) code at

http://forums.xkcd.com/viewtopic.php?f=17&t=97981&p=3186720#p3186509

If someone can find a clear logical error in it, or has comments on the algorithm I use, I'd be keen to talk specifics.

@Lemming: Regarding the table found at

http://www.haskell.org/haskellwiki/Battleship_game_combinatorics

the second result there is wrong. If we consider placing 2 ships of length 2, there are 8 ways to put the first in a corner which blocks 4 moves for the second ship, 28 ways to place it along a side which blocks 5, 32 ways to place it perpendicular to a side which blocks 6 moves, and 112 ways to place the first ship in the middle of the board, which block 7 moves for the second ship ie there are (8*176 + 28 * 175 + 32 * 174 + 112 * 173)/2 = 15626 ways to place 2 indistinguishable 2s, and the table at the haskell wiki says there are 13952.

Edit: I believe I've determined where the disagreement in numbers comes from. If one assumes that ships can be placed in any way so long as they don't overlap anywhere, then you get the figures that I reported. But, if you assume that ships cannot be adjacent, neither horizontally, vertically or diagonally, then the numbers that arise are those reported by Lemmings.

Nobody is wrong, people are just using different sets of rules.

Answer 3

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.

Answer 4

I found the number of possibilities by dynamic programming: 1925751392. Computation time: 80s. Written in Haskell.

See count10x10 in http://code.haskell.org/~thielema/htam/src/Combinatorics/Battleship/Count/ShortenShip.hs