
Battleship theory  ProblemADay
nahtmmm  Mar. 12th, 2008 03:06 pm Battleship theory A few days ago, I happened to be playing an old "Battleship"style game. It was a bitterly fought struggle, but IIRC I prevailed over the computer in this contest. At one point my "attack grid" (showing the results of my shots) looked something like the following:
A B C D E F G H
_______________
1. . X . . . . . X = miss
2. X O . . . O . O = hit
3. . X . . . X . . = not fired upon yet
4. . . . . . . .
5. . . . O . X .
6. . . . O . O .
7. . . . . . X .
8. . . . X . . .
++
I don't remember the layout entirely, of course, but assume that I had inundated the grid sufficiently to be certain that I must have hit each enemy ship at least once by this point. In this particular round, my opponent had three 3square ships and one 5square ship to arrange horizontally and vertically (with no overlapping) in the 8x8 grid allotted.
Given the diagram shown, then:
1) List all of the possible layouts of the enemy fleet. (If you like, you can denote the poistion of a ship by listing the coordinates of its ends.)
2) At this point in the game I had the opportunity to use a special trick shot. I could fire upon a single square and, if a ship occupied that square, a chain reaction would start: The ship I hit would blow up, along with any ship occupying a square that was next to, above, or below a square occupied by the ship I hit, along with any ship immediately beside that ship, and if the fourth ship were unlucky enough to be beside any of these it would be blown up as well. Determine my bestpercentage shot in terms of expected damage done. (Obviously I would be sure to hit something at D2, for example, but would that necessarily do the best average damage?)1 comment  Leave a comment  
Hidden There are 8 possible setups for his ships:
++ ++ ++ ++
........ ........ ........ ........
..AAAAA. ..BBBCCC ..BBBCCC ..BBBCCC
....B... ....A... ........ ........
....B... ....A... ........ ........
....B... ....A... ..DDD... ..DDD...
..CCCDDD ....ADDD ..AAAAA. ...AAAAA
........ ....A... ........ ........
........ ........ ........ ........
++ ++ ++ ++
++ ++ ++ ++
........ ........ ........ ........
..BBBCCC ..BBBCCC ..BBBCCC ..BBBCCC
....D... ....D... ........ ........
....D... ....D... ........ ........
....D... ....D... ...DDD.. ...DDD..
..AAAAA. ...AAAAA ..AAAAA. ...AAAAA
........ ........ ........ ........
........ ........ ........ ........
++ ++ ++ ++
In four cases, everything is connected, so any shot that hits will kill everything, in the other four cases, there are two 3ships connected, and the other 3ship and the 5ship are connected, so taking out the group with the 5ship is best. Looking at the overlap of all the groups that we want to hit, we get this set of targets:
++
........
........
........
........
....*...
....***.
........
........
++
The only one that hasn't already been hit, and the one that does the most damage, is therefore F6.

