how many ways can you place items on this board

Question

This is a programming (C#) and math related question.

I have a 4x4 battleship grid which contains 3 ships. These 3 ships have the size's 3x1, 2x1, 1x1.

I have to find out have many ship placements are possible on this board with the information I have so far. I know the expected output is supposed to be 132

The information I have.

Character 'x' means shots that missed.

Character 'o' means shots that hit.

Character '.' means where I have not yet taken a shot.

The grid looks like this then...

. . . .

. o x .

. . . .

o . . x

I have been going at this and trying to find mathematical formulas and what not for a good while but without any success.

How do I go about figuring this out? Do I need any though calculations or am I overthinking this?

Answer 1

A brute force approach will be fast enough. Ignoring the hit/miss data and the requirement that the ships don't overlap, there are:

• 16 possible locations for the 1x1 ship
• 12 x 2 possible placements of the 2x1 ship
• 8 x 2 possible placements of the 3x1 ship

for a total of only 6144 possible ship arrangements to test. You can improve this further by checking that the big ships don't overlap before placing the small ship. In any case, this program will finish in a fraction of a second.