Using the game of [Battleship](http://en.wikipedia.org/wiki/Battleship_(game)) 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"?



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


