Personal tools

Talk:Battleship game combinatorics

From HaskellWiki

Revision as of 19:59, 9 November 2012 by Jestingrabbit (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

It seems like this table is really wrong. If you look at the second entry, the number of ways to place 2 ships of length 2, there are 8 ways to put the first in a corner which blocks 4 moves for the second ship, 28 ways to place it along a side which blocks 5, 32 ways to place it perpendicular to a side which blocks 6 moves, and 112 ways to place the first ship in the middle of the board, which block 7 moves for the second ship ie there are (8*176 + 28 * 175 + 32 * 174 + 112 * 173)/2 = 15626 ways to place 2 indistinguishable length 2 ships, and the table says there are 13952.

For the actual game configuration, with ships of length 5, 4, 3, 3 and 2, with length 3 ships distinct, I get 30,093,975,536. As a lower bound for that bound for that problem, consider that a ship of length m can eliminate at most (n+1)(m+1)-2 placements of the length n ship. Placing the ships in order 5, 4, 3, 3, 2, there are 120 placements for the 5, at least 140-28=112 for the 4, at least 160-22-18=120 for the first 3, at least 160-22-18-14=106 for the second 3 and 180-16-13-10-10=131 for the 2. This gives a lower bound of 120*112*120*106*131=22395340800. That's for distinct 3s, but this gives a lower bound of more than 5 times your answer. Jestingrabbit 08:39, 9 November 2012 (UTC)

Ah, I see what's going on. I'll edit the page to reflect what's happening. Jestingrabbit 19:59, 9 November 2012 (UTC)