In a standard game of battleships, what is the minimum number of strikes you will need to make to guarantee hitting at least one boat?

Battleships is played on a 10x10 Grid,
You are allowed:-
1 Battle Ship (4x1)
2 Cruisers (3x1)
3 Destroyers (2x1) and
3 Submarines (1x1)

NOTE:-These rules are slightly different than those of the board game, I am using these so that all members can give the same answer.

(In reply to My technique by Justin)

Using that technique, here is how many ways a battleship could be hit by firing on a specific cell:

2345555432
3456666543
4567777654
5678888765
5678888765
5678888765
5678888765
4567777654
3456666543
2345555432

Notice that the rows and columns on the sides get progressively smaller. There is only 1 way to hit a vertical battleship on the top row, 2 ways to hit it on the next row, and 3 ways to hit in on the next row. In order to hit a a possible battleship, you have to hit at least 2 spots in each row and column so this means you will lose 2*(1+2+3) = 12 on each of the 4 sides or 48 possiblities lost.

Since there are 10 rows and 7 columns at which the leftmost cell of a horizontal battleship could be, and a similar number for vertical positions, there are 140 places that the battleship could be. So the equation H * 8 - 48 = 140 means H - 23.5 and since we can't use fractional hits, we have to round up to 24. This means 24 hits are the fewest needed to be sure you will hit the battleship.

Upon a closer look, we notice that no battleship was prevented by more than one hit, so it seems H should be 24. The real reason for this is because if using only 2 hits per row, the hits can only be placed on columns 3, 4, 7, and 8, (called "inner" rows) so the other 6 rows and columns wouldn't be hit. Since you you need to cover 6 columns with these 3-per-row hits, and 2 hits per column, you need 12 hits, which means you need 4 rows of 3-per row hits. This means you need 4 extra hits in addition to the ones previously calculated and since these would take place in rows/colums 3 and 8, there are 4 more possibilities lost, so the equation would be H*8-52=140, which gives H is exactly equal to 24.

To figure out how many possible solutions exist with the fewest number of hits, realize that since H now exactly equals 24, no two hits may disallow the same possibility. Also, to minimize possiblities lost, the 3-per-column rows need to be on inner rows, and the 3-per-row columns need to be inner columns. If more possiblities were lost, H would need to be larger than 24 to accomodate this and that isn't allowed.

From these two rules, the hits must be placed on an inner row and outer column, or outer row and inner column. This is because having hit in an non-inner row and non-inner column would mean both the row and column containing that row would need to have 3 hits which is disallowed because it would make the number of hits needed over the minimum amount. If a hit occured in an inner row and inner column, then a cell in a non-inner row and non-inner column would need a hit to make up for this, which was just shown to be disallowed.

Think of the 12 intersections between pairs of rows and pairs columns of different types as 2x2 squares. There is a 2x3 grid of squares and a 3x2 grid of squares. The hits must be going in a diagonal way in each square or two hits will stop the same possibility. Also, the diagonal way must be the same in both individual grid of squares or two hits will have only two cells between them while two other hits have four cells between them, both of which are disallowed.

There are two possible diagonal patterns, and two grids of squares, so there are 4 possible solutions that use only 24 hits.

0010001000
0001000100
1000100010
0100010001
0010001000
0001000100
1000100010
0100010001
0010001000
0001000100

0001000100
0010001000
1000100010
0100010001
0001000100
0010001000
1000100010
0100010001
0001000100
0010001000

0010001000
0001000100
0100010001
1000100010
0010001000
0001000100
0100010001
1000100010
0010001000
0001000100

0001000100
0010001000
0100010001
1000100010
0001000100
0010001000
0100010001
1000100010
0001000100
0010001000

Posted by Gamer on 2005-07-25 02:24:39