Battleship

Overview

Battleship is the classic naval-strategy game played on a 10x10 grid. A fleet of five ships — typically a Carrier (5 cells), Battleship (4), Cruiser (3), Submarine (3), and Destroyer (2) — is placed randomly each new game with no overlap. Your job is to find and sink every ship by calling out coordinates, one shot at a time.

The board reveals only what you've shot at: misses show as water, hits show as ship segments, and a fully revealed ship is marked sunk. Because the fleet is hidden, the game becomes a search problem with no fog-of-war for the computer-placed ships, so every shot you take builds a clearer probability picture of where the remaining vessels can still fit.

How it works

Ship placement uses rejection sampling — the engine picks a random orientation and starting cell for each ship and re-rolls until none of its cells overlap an existing ship or fall off the board. This produces uniformly random legal configurations without favouring corners or edges.

A shot resolves in one step: the targeted cell flips to "hit" if it intersects any ship, otherwise "miss". Once every cell of a ship has been hit, the ship is reported as sunk along with its type. Optimal hunting alternates two modes: a parity-based search that targets every other cell in a checkerboard, exploiting the fact that the shortest ship is two cells long, and a focused hunt that fires along the line of a recent hit until the ship is destroyed.

Examples

• An opening shot at E5 misses — you've learned that one cell of 100 is empty, narrowing the placement space slightly.
• A hit at D7 followed by another at D8 confirms a vertical orientation; the smart next shot is D6 or D9, not C7 or E7.
• After sinking the 2-cell Destroyer early, you can drop the parity strategy because every remaining ship covers at least three cells, so a sparser search grid still catches them.
• A fleet of 5+4+3+3+2 = 17 ship cells means the best-case theoretical game finishes in 17 shots; in practice a strong player finishes in the mid-40s.

FAQ

Can ships touch diagonally or end-to-end?
This version allows ships to sit adjacent to each other, including end-to-end, but never overlapping.

Does the computer cheat by relocating ships?
No. All ships are placed once at the start and stay fixed.

Why does parity searching work?
The smallest ship is two cells, so any ship must cover at least one cell of any checkerboard half. Shooting one colour halves your wasted shots in the search phase.

Can I undo a shot?
No — each shot is committed, mirroring the pen-and-paper original.

What's the average number of shots to clear the board?
With purely random shooting it's about 96. With parity plus focused hunting most players finish well under 60.

Try Battleship