Battleships

The clause that does the work is the word “even”

Battleships prints two kinds of information: the fleet, and the numbers beside the rows and columns. Neither is the clause that makes the genre solvable. That one is buried in the sentence no two ships touch, not even diagonally, and it never appears on the board at all. It pays twice. Locally, because a ship is a straight run, the four diagonal neighbours of any ship cell can belong to no ship whatsoever — so writing down one ship cell hands you up to four water cells before you have done any arithmetic. Globally, it is the difference between a puzzle and a haystack.

On an 8×8 board carrying the standard armada, dropping that one word multiplies the answer space by 62.7× — from 20,774,262,284 placements to 1,302,617,200,964. The same board with the smaller six-ship fleet only gains 2.72×, which is the whole point: the clause is worth more the more crowded the ocean is, because what it really rations is space between ships, and a crowded fleet spends most of the board on that rationing.

How much ocean the armada has, to the last digit

An answer, before a single number is read, is a set of cells whose blocks are straight runs, one per ship, no two of them touching. src/count.ts counts those exactly with a row-at-a-time sweep, and the no-touch rule is what makes the rows cheap. A run of two or more cells inside one row is necessarily a finished horizontal ship — nothing may sit above or below it — so the only thing that can cross the line between two rows is a single cell carrying straight on, in the very same column. The whole frontier is therefore: which columns the row above used, how far each of its single-cell runs has already grown downwards, and which ships are still unplaced.

The standard armada is twenty cells of ship that may not touch, and the first square board it fits on at all is 7×7, in 406,664 ways. On the board the game is actually played on it has 1,855,545,978,831,780 places to hide, and one size further up the number is 76,057,466,137,845,004. Searching the OEIS in September 2026 for either sequence returns nothing.

Two rows of it are somebody else's sequence, though, which is what makes them a check rather than a claim. Shrink every ship to a single cell and let the fleet be unlimited, and a placement is just a set of cells no two of which touch — non-attacking kings. That is A063443, whose own headline reading is “tile an n×n square with 1×1 and 2×2 tiles” (a 2×2 tile's top-left corner is a king). Drop the diagonal clause as well and it becomes the independent sets of the grid graph, A006506. The sweep reproduces both, with no special-casing: the same code path, a different fleet.

The fleet hides in the corners, and the blank board says so

The sweep carries forward weights, and a backward pass gives every frontier state the number of ways it can still be finished. Multiply the two and you get, exactly, the probability that any given cell holds a ship — averaged over the entire answer space rather than over a sample of it. The answer is not flat, and it is not close to flat.

Over all 1,855,545,978,831,780 placements of the standard armada on the standard board, a cell on the border holds a ship about 24.52% of the time and a cell in the middle only 18.25% — the corner beats the centre by 1.29×. The reason is the clause again: a ship cell in the middle has to keep eight neighbours clear, a ship cell in a corner only three, so the border is the cheap real estate and that is where the fleet ends up. Squeeze the same twenty ships onto an 8×8 and the corner pulls further ahead of the centre — 2.50× — because crowding is exactly what the clause taxes.

The one place the ordering is not monotone is the corner itself at 10×10, where an edge cell (24.52%) just edges out the corner (23.63%). A corner is the cheapest cell to occupy but there are only four of them, and a ship reaching out of one immediately leaves the border; on a board with room to spare that costs more than the corner saves. At 6×6 and 8×8, where there is no room to spare, the corner wins outright — 43.06% against 33.48%, and 53.66% against 42.09%.

The second grid is the 36 boards this page ships, and the honest reading of it is that 36 boards are not enough to read anything from. The largest per-cell gap against the exact probabilities is 16.0%, and the one-sigma sampling noise for a bank this size is already 7.3% per cell — so the gap is what a fair draw of 36 would look like anyway. There may well be a selection effect in there: the generator's answers are uniform, but only the answers that turn out to be solvable get shipped, and nothing guarantees that filter is neutral. This bank cannot show it. What the left-hand grid does show is not a sample at all — it is the whole space, and the border really is brighter than the middle.

That the sampler is uniform is not an assumption either. It draws by walking the same frontier forwards with each row weighted by how many finished placements it leaves reachable — no rejection, no retries — and over 20,000 draws at 10×10 no cell is off its exact probability by more than 0.753%.

The numbers are the weakest thing on the board

A 6×6 board carries a fleet of 3, 2, 2, 1, 1, 1 and its whole answer space is 894,296 placements, which fits in memory. So the twelve printed numbers can be priced exactly: group every placement by the row and column counts it produces, and look at the groups.

Every number on the board, and a typical 6×6 still has 5 answers left; only 8.22% of placements are pinned down by arithmetic alone. That is the genre's real shape: the numbers are a filter, not a solution, and everything that closes the gap comes from the revealed pieces and from the no-touch rule.

Not every number is worth the same. Group the whole space by what one line prints and the shares fall out exactly — and they say something slightly against intuition:

The sharpest number is the biggest one: a line printing 5 leaves only 0.65% of the space, because a line that crowded is rare. A 0 leaves 17.38% — much blunter as a filter. But a 0 is the only value that settles its entire line on sight, with no other information, and that is the difference between information and usable information. The number that cuts the space hardest is not the number you can act on.

The same measurement at the sizes too large to enumerate, over uniform draws instead of the whole space:

A revealed piece says more than “a ship is here”

The pieces Bimaru prints are not counters. A revealed cell shows water, a submarine, a rounded end that points one way, or an unoriented middle — and each of those is a statement about the cells next to it. A submarine is four water cells in disguise. A pointing end is three water cells and one ship cell. Only the middle keeps a secret, and it keeps exactly one bit of it: which axis it runs along.

That is measurable. Take a uniform answer, reveal every cell, then rub reveals out in a random order for as long as the board still has exactly one answer. Do it twice: once with the pieces Bimaru prints, once with a weakened dialect where a ship cell only admits to being a ship.

At 10×10 a minimal board needs 4.67 printed pieces on average; strip the shapes and the same answers need 5.88 — 1.26× as many cells to say the same thing. That is a real premium, and it is also smaller than it sounds. A shape hint looks like it should be worth four or five cells, because it names its whole neighbourhood; it is worth about a quarter of a cell extra, because the no-touch clause was going to tell you most of that neighbourhood anyway. The unprinted clause is not only the strongest thing on the board, it is strong enough to make the printed pieces partly redundant.

The ladder

• count — the numbers beside the rows and columns, and nothing else. A line whose ships are all placed is water the rest of the way; a line with exactly as many unknowns as it still owes is ship the rest of the way.
• touch — the clause that never gets printed. The four diagonals of a ship cell are water, always. A ship cell with a neighbour along one axis is water along the other. A run as long as the flagship is finished, so both of its ends are water. And an unoriented middle resolves the moment either axis is closed — including by the edge of the board.
• line — read one row, or one column, the way a nonogram solver does: enumerate every filling of it consistent with what is known, with its number, and with the ship lengths the fleet owns; keep what they all agree on.
• fleet — the armada is an inventory. Blocks sealed in on every side are spent ships; for each length still owed, list every berth it could still take. A cell no remaining ship can reach is water. A length with exactly as many berths as ships left is settled outright. And an unfinished block has to grow into some berth, so whatever all its candidate berths agree on is forced.
• probe — assume a cell, run the cheaper rungs, and drop the assumption if the board dies.

Every shipped board is finished by the fleet rung, by construction — the generator kept rubbing reveals out only for as long as propagation could still close the board without guessing. What the table shows is the shape of the climb. At 10×10 the numbers alone settle 58.8% of the grid and finish 0 boards; adding the unprinted no-touch clause takes it to 80.5%; reading the lines as nonogram lines takes it to 80.6% and finishes 2; the inventory closes the rest.

The same rungs, priced as pruning instead of as proof

Run the complete search, but only let it propagate up to a given rung between branch points, and count the branch points. The ceiling is 200,000.

The interesting part is the ordering. In the answer-space table the no-touch clause is worth tens of times over; here, as a pruning rule, touch takes an 8×8 from 805 to a median of 3 branch points, and the fleet rung finishes the job at 0. A clause can be cheap in one accounting and decisive in the other, and there is no way to know which without running both.

The shipped boards

Every reveal on these boards is load-bearing: they were built by revealing the whole grid and rubbing cells out in a random order for as long as the ladder could still finish without guessing, so removing any one of the survivors breaks the board. The tests re-derive that rather than trusting it.

Three ways to misread the board

All three misreadings are generous — each one only ever adds answers, so the intended answer stays legal on every board and nothing looks wrong until the end. Forgetting the word “even” leaves 18 of 36 8×8 boards unique; reading the printed pieces as mere counters leaves 8 of 36. A player who makes either mistake does not get stuck — they get a board with several answers and no way to tell which one was meant, which is the failure mode worth guarding against.