A simplified Battleship game is played on a $4 \times 4$ grid. Two ships are placed on the board: a $3 \times 1$ ship (occupies 3 consecutive cells in a row or column) and a $2 \times 1$ ship (occupies 2 consecutive cells in a row or column). Ships must lie entirely within the grid and cannot overl…

How to Think About It: For the counting part, enumerate placements of the $3 \times 1$ ship first (this is the more constrained piece), then count valid non-overlapping placements for the $2 \times 1$ ship given each. For the targeting part, compute a coverage heatmap: the number of valid arrangements in which each cell is occupied by at least one ship. The highest-coverage cell is the optimal first shot. Quick Estimate for Total Arrangements: The $3 \times 1$ ship has 16 placements (8 horizontal, 8 vertical). The $2 \times 1$ ship has 24 possible placements on an empty board (12 horizontal, 12 vertical). On average about 3 of the 24 placements conflict with each $3 \times 1$ placement. So total $\approx 16 \times (24 - 3) \approx 16 \times 21 \approx 336$. The exact count requires enumeration and turns out to be lower, 264, because more placements conflict than this rough estimate suggests. Part 1 -- Counting Valid Arrangements: Placements of the $3 \times 1$ ship on a $4 \times 4$ grid: - Horizontal: 2 positions per row (columns 1-3 or 2-4) $\times$ 4 rows $= 8$ - Vertical: 2 posi…

Battleship on a 4x4 Board: Arrangements and Optimal Targeting

Combinatorics · Medium · Free problem

A simplified Battleship game is played on a $4 \times 4$ grid. Two ships are placed on the board: a $3 \times 1$ ship (occupies 3 consecutive cells in a row or column) and a

\times 1$ ship (occupies 2 consecutive cells in a row or column). Ships must lie entirely within the grid and cannot overlap.

How many distinct valid arrangements of both ships are there?

As the seeker (guessing cells), which cell should you target first to maximize your probability of hitting a ship, assuming the opponent places ships uniformly at random over all valid arrangements?

Briefly describe the optimal placement strategy for the hider.

Hints

Count $3 \times 1$ ship placements first (16 total: 8 horizontal, 8 vertical), then for each position count valid non-overlapping placements for the \times 1$ ship.
For the targeting question, compute a coverage heatmap: for each cell, how many of the 336 valid arrangements cover that cell? The cell with highest coverage is the optimal first shot.
By symmetry, the four center cells of a $4 \times 4$ board have the highest coverage -- they can be reached by more horizontal and vertical ship placements than corner or edge cells.

Worked Solution

How to Think About It: For the counting part, enumerate placements of the $3 \times 1$ ship first (this is the more constrained piece), then count valid non-overlapping placements for the \times 1$ ship given each. For the targeting part, compute a coverage heatmap: the number of valid arrangements in which each cell is occupied by at least one ship. The highest-coverage cell is the optimal first shot.

Quick Estimate for Total Arrangements: The $3 \times 1$ ship has 16 placements (8 horizontal, 8 vertical). The \times 1$ ship has 24 possible placements on an empty board (12 horizontal, 12 vertical). On average about 3 of the 24 placements conflict with each $3 \times 1$ placement. So total $\approx 16 \times (24 - 3) \approx 16 \times 21 \approx 336$. The exact count requires enumeration and turns out to be lower, 264, because more placements conflict than this rough estimate suggests.

Part 1 -- Counting Valid Arrangements:

Placements of the $3 \times 1$ ship on a $4 \times 4$ grid: - Horizontal: 2 positions per row (columns 1-3 or 2-4) $\times$ 4 rows $= 8$ - Vertical: 2 positions per column (rows 1-3 or 2-4) $\times$ 4 columns $= 8$ - Total:

6$ placements

Placements of the

\times 1$ ship on an empty $4 \times 4$ grid: - Horizontal: 3 positions per row $\times$ 4 rows $= 12$ - Vertical: 3 positions per column $\times$ 4 columns $= 12$ - Total: 4$ placements

Valid non-overlapping pairs: For each of the 16 positions of the $3 \times 1$ ship, count how many of the 24 positions for the \times 1$ ship do not overlap.

By symmetry, the $3 \times 1$ ship either covers cells in a row (horizontal) or a column (vertical). We can use the 8-fold symmetry of the board (rotations and reflections) to reduce the case analysis.

For a horizontal $3 \times 1$ ship occupying cells $(r, c), (r, c+1), (r, c+2)$, the 3 occupied cells invalidate every \times 1$ placement that touches them. Doing the full enumeration over all 16 placements of the $3 \times 1$ ship and, for each, counting the \times 1$ placements that do not overlap, the surviving counts sum to 264:

$\sum_{i=1}^{16} (\text{valid } 2 \times 1 \text{ placements for position } i) = 264$

Total valid arrangements: 264

(Note: this counts ordered pairs -- the two ships are distinguishable because they are different sizes. No division by 2 needed.)

Part 2 -- Optimal First Cell to Target:

To find the best first shot, compute the coverage count of each cell: the number of valid arrangements (out of 264) in which that cell is occupied by either ship.

By the symmetry of the $4 \times 4$ board, coverage counts form a symmetric pattern. The exact coverage heatmap (rows 1-4 top to bottom, columns 1-4 left to right) is:

$\begin{array}{cccc} 60 & 85 & 85 & 60 \\ 85 & 100 & 100 & 85 \\ 85 & 100 & 100 & 85 \\ 60 & 85 & 85 & 60 \end{array}$

The four center cells $(2,2), (2,3), (3,2), (3,3)$ (using 1-indexed rows and columns) have the highest coverage, 100 each, because both ships can reach them in the most ways. Edge cells have coverage 85 and corner cells 60.

The optimal first shot is any of the four center cells, e.g., $(2,2)$. Under uniform random placement, the probability of hitting a ship on the first shot at a center cell is

00/264 \approx 37.9\%$, compared to $60/264 \approx 22.7\%$ for a corner cell.

Part 3 -- Optimal Placement Strategy for the Hider:

Since the seeker targets high-coverage cells first (center cells), the optimal hider strategy is to avoid placing ships in ways that cover center cells. Specifically: - Place ships toward corners and edges, which have lower coverage probability. - Avoid placing both ships near the center simultaneously. - Use randomization: do not always use the same placement, as a deterministic strategy is exploitable.

In game-theoretic terms, if both players play optimally, the equilibrium involves the hider randomizing over low-coverage placements and the seeker randomizing over cells in decreasing order of coverage probability.

Answer: 1. Total valid arrangements: 264. 2. Optimal first shot: any center cell ($(2,2)$, $(2,3)$, $(3,2)$, or $(3,3)$), each covering

00/264 \approx 37.9\%$ of arrangements. 3. Hider should place ships in corners/edges and randomize to avoid exploitation.

Intuition

The Battleship problem is a classic example of information-theoretic targeting under uncertainty. The optimal first shot maximizes the probability of gaining information (a hit), which is equivalent to maximizing the expected coverage of the shot. The parity/checkerboard argument often cited for larger boards (where you must hit the \times 1$ ship before the $3 \times 1$) does not apply as strongly on a $4 \times 4$ board because the board is small enough that the center cells dominate coverage regardless of parity.

The hider/seeker equilibrium in this problem is a finite zero-sum game, and by Nash's theorem a mixed strategy equilibrium exists. In practice, the hider benefits from placing ships in configurations that look low-probability to an unsophisticated seeker (corners, edges) while still maintaining enough coverage randomness that systematic exploitation is hard. This type of adversarial search under uncertainty has direct analogs in quantitative trading: market makers hide large orders in unconventional venues and times to avoid being picked off by algorithmic seekers.

Open the full interactive solver →