Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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"?

share|improve this question
    
If you're curious, here's a keyword: en.wikipedia.org/wiki/Domino_tiling –  Qiaochu Yuan Dec 9 '09 at 17:32
2  
I highly doubt that you can do better than a backtracking search, exploiting symmetries. –  David Speyer Dec 9 '09 at 17:39
    
Qiaochu, how would domino tilings help in this case? –  Gjergji Zaimi Dec 9 '09 at 17:42
2  
Wait, I think some people are interpreting the problem differently than I am. As I understand it, we only want to place a total of 5 ships on the board (like in the game!), not enough ships to cover every square. –  Reid Barton Dec 9 '09 at 17:45
1  
Whoops! I completely misread the problem. –  Qiaochu Yuan Dec 9 '09 at 17:55
show 4 more comments

4 Answers

up vote 13 down vote accepted

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.)

share|improve this answer
1  
Isn't there a generalization of Kasteleyn's method to the monomer-dimer problem (i. e. counting tilings into 1-by-1 and 2-by-1 rectangles, or matchings which are not necessarily perfect)? –  Michael Lugo Dec 9 '09 at 18:28
2  
For any fixed set of monomer locations, you can recognize the number of matchings of everything else as a minor of the dimer-only matrix. This is a wonderful refinement of Kasteleyn (or Kasteleyn-Percus in the bipartite case) that was found and used to great purpose by Rick Kenyon. However, if the monomers are free to travel, Mark Jerrum showed #P-hardness for the exact number for a general planar graph. springerlink.com/content/w335r5523437h466 –  Greg Kuperberg Dec 9 '09 at 18:41
    
q-Analogue of battleships? Upvote! –  Per Alexandersson Nov 8 '12 at 21:40
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
3  
The number of placements will only be polynomial for sufficiently large r and s, since there aren't some negative number of ways to place a 1x5 ship on a 3x3 board. –  Reid Barton Dec 9 '09 at 18:36
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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