7
$\begingroup$

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.

enter image description here

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?

  • 1
    Please also see this question on Mathoverflow: http://mathoverflow.net/questions/8374/battleship-permutations2011-08-21

4 Answers 4

3

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

  • 0
    @Joshua, depends what you mean by "too long". Evidently it wasn't too long for the two people who posted answers based on running programs.2016-04-11
2

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.

  • 0
    Now I have confirmed this number by dynamic programming. It needed only three minutes to run.2012-01-14
0

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.

  • 0
    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.)2011-08-21
0

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)     return total  def main():     points = set()     ships = [(1, 5), (1, 4), (2, 3), (1, 2)]     print f(points, ships, 8, 8)  main()