?

Log in

   Journal    Friends    Archive    Profile    Memories
 

Battleship theory - Problem-A-Day

nahtmmmMar. 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 3-square ships and one 5-square 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 best-percentage 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 commentPrevious Entry Share Next Entry

Comments:

From:nekura_ca
Date:March 14th, 2008 02:55 am (UTC)
(Link)
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 3-ships
connected, and the other 3-ship and the
5-ship are connected, so taking out the
group with the 5-ship 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.