# How many ways can we place these ships on this board?

I want to find out how many ways we can arrange these ships on this field. I just have no idea how to go about solving this. So I bring it to the Pros!

The board is an 8 by 8 Board. There are 5 pieces.

We have:

• 1x 5 box ship
• 1x 4 box ship
• 2x 3 box ship
• 1x 2 box ship.

The ships cannot overlap one another, and each item can be placed either horizontally or vertically.

How can we go about figuring this out?

-
Please also see this question on Mathoverflow: mathoverflow.net/questions/8374/battleship-permutations –  kuch nahi Aug 21 '11 at 7:28

I think the way you do this problem is you program a computer to do an exhaustive search.

-
Yeah, I was thinking this might need some computer programming. –  Rickmasta Aug 21 '11 at 8:32
Perhaps the person who downvoted this answer has a better idea? –  Gerry Myerson Aug 21 '11 at 10:10

In the original game the ships are not allowed to touch. If this applies to your problem, too, then the number of possibilities is 16546192. I found this number by dynamic programming and verified it by enumeration of all configurations.

Since in your image some ships touches other ones, so your problem might be different from the standard game. If yes, then I have to modify my program a little bit, which risks introducing bugs. I assume that your ships can even touch at the long edges, right?

An upper bound for the number of possibilities is 5.3e9. This is the number I get when ships are allowed to overlap: 2*4*8 * 2*5*8 * (2*6*8)^2 * 2*7*8.

-
By enumeration of all possibilities I got the number 571126760. It needed 42 minutes to run. The two ships of size 3 are not distinguished. If you want to distinguish them, then multiply the number of possibilities by 2. –  Lemming Jan 9 '12 at 18:00
Now I have confirmed this number by dynamic programming. It needed only three minutes to run. –  Lemming Jan 14 '12 at 22:35

I think the methods suggested in the MathOverflow question linked by kuch nahi in the comments are going to be more revealing than what I'm about to say, but it's an involved inclusion exclusion: add up all the ways of placing the ships individually, subtract configurations where two intersect, add configurations where three intersect back in and so on. The problem I see is working out how many configurations there are where a ship of size A and one of size B intersect--it seems like it would be easy to make a mistake (perhaps I am over-estimating the difficulty). At any rate, I'm firmly of the opinion that it can be done by hand.

-
This would indeed be the way to go for the general $n \times m$ board, but I suspect you're being optimistic in hoping for a by-hand computation. There are rather a lot of ways to have some of the 5 ships intersect. –  Robert Israel Aug 21 '11 at 18:33
Yeah, I realised that later. I do wonder if the brute force idea is better or worse than using a computer to do inclusion-exclusion. (For my somewhat naive coding skills, I could certainly code the brute force attack more easily. There are upwards of 5 billion positions to check, assuming I worked it out properly, but you can short-circuit many of them.) –  hoyland Aug 21 '11 at 21:25

I wrote this program and got 13,858,992. I have not tested the program so it might be buggy; you can manually check some cases with smaller numbers of ships and smaller grids if you want.

Edit: This mistakenly assumes there is a single 2x3 ship instead of two 1x3 ships. So this would have to be changed in the ship definition. Also, do you consider the two 1x3 ships distinguishable?

def genpoints(x, y, w, h):
for dx in range(w):
for dy in range(h):
yield x + dx, y + dy

def f(points, ships, width, height):
if not ships:
return 1
total = 0
for w, h in (ships[0], reversed(ships[0])):
for x in range(width - (w-1)):
for y in range(height - (h-1)):
p = set(genpoints(x, y, w, h))
if not (points & p):
total += f(points | p, ships[1:], width, height)

def main():
points = set()
ships = [(1, 5), (1, 4), (2, 3), (1, 2)]
print f(points, ships, 8, 8)

main()

-