Battleships: the clause that solves the board is the one it never prints

Solitaire Battleships (Bimaru) in the browser with a five-rung
solver. A Battleships board prints two things — the fleet, and the numbers
beside the rows and columns — and neither is what makes the genre
solvable. That is no two ships touch, **not even diagonally, which
appears nowhere on the board. Locally it means the four diagonal neighbours of
any ship cell belong to no ship at all, so one cell hands you four water cells
free. Globally it is worth **62.7× of the answer space on an 8×8 with the
standard armada (20,774,262,284 against 1,302,617,200,964). A row-at-a-time
profile DP counts the space exactly: the standard armada does not fit on a
6×6 at all, first fits at 7×7 in 406,664 ways, has
1,855,545,978,831,780 places to hide on 10×10 and
76,057,466,137,845,004 on 11×11 (24,536,651 frontier states, 518 s). Swap
the fleet spec and the same sweep degenerates to OEIS
A063443 and A006506,
and agrees with both. Forward weights times backward completions give the
exact probability that each cell holds a ship over the whole space — the
fleet crowds the border, and at 8×8 a corner beats the centre 2.50×.
Meanwhile the numbers are the weakest thing on the board: enumerate all
894,296 answers of a 6×6 and every number being visible still leaves a median
of 5, with only 8.22% pinned down by arithmetic alone; at 10×10, 120
uniform draws produced zero boards the numbers could finish. 37 tests.
Puzzle #66 in the solver series.

Live demo: https://sen.ltd/portfolio/battleships/
Source: https://github.com/sen-ltd/battleships

The rules

Solitaire Battleships — also sold as Bimaru — hides a fleet in a grid.

• The fleet is known. On the standard 10×10 board it is one battleship (4 cells), two cruisers (3), three destroyers (2) and four submarines (1) — ten ships, twenty cells.
• Every ship is a straight run of cells, horizontal or vertical.
• No two ships touch, not even diagonally.
• The number beside a row or column counts the ship cells in it.
• A few cells are revealed. What they reveal is the shape of the piece — water, a submarine, a rounded end that points, or a middle that does not say which way it runs.

I checked the rules against Battleship (puzzle)
before writing a line:

The ships are placed so that no ship touches any other ship, not even diagonally.

Everything below is about those last three words.

Here is a real 6×6 board out of the shipped bank (> is a right-hand end piece):

      the board                   the answer

     0 3 0 2 1 4                   0 3 0 2 1 4
  0  . . . . . .                0  . . . . . .
  3  . . . . . >                3  . # . . # #
  1  . . . . . .                1  . # . . . .
  2  . . . . . .                2  . . . # . #
  2  . . . . . .                2  . # . . . #
  2  . . . . . .                2  . . . # . #

One revealed cell and twelve numbers, and it has exactly one answer. One of the
36 shipped 6×6 boards needs no revealed cells at all — the twelve numbers do the
whole job on their own.

The clause that never gets printed does all the work

A Battleships board prints exactly two things: the fleet, and the numbers.
Neither is what makes the genre solvable.

Locally. Because a ship is a straight run, the four diagonal neighbours
of any ship cell can belong to no ship at all — the same ship would have to
bend, and a different ship would be touching. So every ship cell you write down
hands you up to four water cells, before you do any arithmetic.

Globally. Count the same fleet with the diagonal half of the clause dropped:

board and fleet	no two ships touch at all	ships may touch diagonally	what "even" is worth
5×5	1,428	31,196	21.8×
6×6	894,296	6,801,560	7.61×
7×7	52,038,088	206,437,716	3.97×
8×8	946,204,480	2,577,018,160	2.72×
8×8 standard fleet	20,774,262,284	1,302,617,200,964	62.7×

(The first four rows carry the small fleet 3, 2, 2, 1, 1, 1; only the last row is
the standard armada.)

The way the multiplier moves is the interesting part. For a fixed fleet, the
word gets cheaper as the board grows — 21.8× down to 2.72×. Put twice as much
ship on the same 8×8 and it jumps to 62.7×. What the clause rations is
space between ships, so it costs the most exactly where the ocean is crowded.

Counting the answer space exactly

An answer, before a single number is read, is a set of cells whose blocks are
straight runs, exactly matching the fleet, no two of them touching. That is
countable, and the no-touch rule is what makes it countable a row at a time:

1. a run of two or more cells inside one row must be a finished horizontal ship — anything above or below it would touch or bend it;
2. so the only thing that can cross the line between two rows is a single cell carrying straight on, in the same column;
3. and a vertical ship occupies the very same column in every row it covers.

The whole frontier is therefore: which columns the row above used, how far each
of its single-cell runs has grown downwards (three bits each), and which ships
are still unplaced. It packs into one integer per state.

grid	placements of the standard armada	frontier states	time
6×6	0	3,254	22 ms
7×7	406,664	123,454	380 ms
8×8	20,774,262,284	689,430	2.6 s
9×9	15,624,844,160,880	2,643,550	16.1 s
10×10	1,855,545,978,831,780	8,335,174	71.4 s
11×11	76,057,466,137,845,004	24,536,651	517.6 s

The standard armada is twenty cells of ship that may not touch, so it does not
fit on a 6×6 at all. The first square board it fits on is 7×7, in 406,664
ways. Searching the OEIS in September 2026 for the sequence returns nothing.

On the small boards the sweep is checked against a depth-first enumeration that
shares no code with it, and against a brute force that simply walks every subset
of the grid and tests it directly.

Two OEIS sequences as a check

A sequence you computed yourself is only as trustworthy as the published one it
reproduces. This sweep degenerates to two, by changing the fleet spec and
nothing else:

• shrink every ship to a single cell and make the fleet unlimited, and a placement is just a set of cells no two of which touch — non-attacking kings, which is A063443 (its 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 is the independent sets of the grid graph, A006506.

grid	one-cell ships, unlimited	A063443	…and without the diagonal clause	A006506
3×3	35	agrees	63	agrees
5×5	6,427	agrees	55,447	agrees
7×7	12,727,570	agrees	1,280,128,950	agrees
8×8	1,355,115,601	agrees	660,647,962,955	agrees
9×9	269,718,819,131	agrees	—	—

Same code path, different fleet. Both are in the test suite.

The fleet hides along the border

The sweep carries forward weights — how many ways each frontier state can be
reached. One backward pass gives every state the number of ways it can still be
finished. Multiply the two, divide by the total, and you get the exact
probability that a given cell holds a ship, over the entire answer space
rather than a sample of it.

board	corner cell	edge cell	centre cell	corner ÷ centre
6×6	43.06%	33.48%	25.39%	1.70×
8×8	53.66%	42.09%	21.42%	2.50×
10×10	23.63%	24.52%	18.25%	1.29×

Across all 1,855,545,978,831,780 placements, a border cell on the standard board
holds a ship 24.52% of the time and a cell in the middle only 18.25%. 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. The border is the cheap real estate,
so that is where the fleet ends up. Squeeze the same twenty ships onto an 8×8 and
the corner-to-centre gap widens to 2.50×, because crowding is what the clause
taxes.

The ordering is not quite monotone at 10×10: an edge cell (24.52%) just edges out
the corner (23.63%). There are only four corners, 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.

The page renders this as a heat map. A blank Battleships board is already
telling you where to look.

The sampler is uniform, and that is checked

The generator draws its answers uniformly from the whole space: walk the same
frontier forwards with each row weighted by how many finished placements it
leaves reachable. No rejection, no retries. The check is the exact marginals
above — over 20,000 draws at 10×10 no cell is off its exact probability by more
than 0.753% (200,000 draws at 6×6: 0.215%; 100,000 at 8×8: 0.498%).

The page also shows the heat map of the 36 shipped boards beside the exact one,
and the honest reading of that second grid is that 36 boards are not enough to
read anything from: its largest per-cell gap is 16.0%, while one-sigma
sampling noise for a bank that size is already 7.3% per cell. Only solvable
answers get shipped, so a selection effect is plausible — this bank simply
cannot show it.

The numbers are the weakest thing on the board

A 6×6 board carries the fleet 3, 2, 2, 1, 1, 1, and its entire answer space is
894,296 placements — small enough to hold in memory. So the twelve printed
numbers can be priced exactly: group every placement by the numbers it produces
and look at the groups.

the whole 6×6 answer space
placements	894,296
distinct sets of twelve numbers	254,877
placements the numbers alone pin down	73,536 (8.22%)
answers left for a typical placement (median)	5
answers left, at worst	36

Every number on the board, and a typical 6×6 still has five answers left.
Only 8.22% are settled by arithmetic alone. It gets worse with size:

board	draws	cells the numbers alone settle (median)	boards the numbers alone finish	answers left (median, capped at 12)
6×6	300	33.3%	9.0%	5
8×8	200	23.4%	0.5%	12
10×10	120	28.0%	0.0%	12

At 10×10, not one of 120 uniform draws was finished by its numbers. In this
genre the numbers are a filter, not a solution.

Which number is worth most

Group the whole space by what a single line prints, and the shares fall out
exactly. The result runs slightly against intuition:

a line that prints	share of the 6×6 answer space it leaves
0	17.38%
1	30.17%
2	27.98%
3	17.99%
4	5.83%
5	0.65%

The sharpest number is the biggest one. A line printing 5 leaves 0.65% of the
space, because a line that crowded is rare. A 0 leaves 17.38% — far blunter as a
filter.

And yet a 0 is the only value that settles its entire line on sight, with no
other information at all. That is the difference between information and usable
information: the number that cuts the space hardest is not the number you can act
on.

What a printed shape is worth

The pieces Bimaru prints are not counters. Water, a submarine, a pointing end, an
unoriented middle — each 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 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 — in
two dialects: the pieces Bimaru actually prints, and a weakened one where a ship
cell only admits to being a ship.

board	draws	reveals needed, as shapes	reveals needed, occupancy only	what the shape is worth
6×6	120	median 2 (mean 1.54)	median 2 (mean 1.83)	1.19×
8×8	60	median 2 (mean 2.60)	median 3 (mean 3.35)	1.29×
10×10	24	median 5 (mean 4.67)	median 5 (mean 5.88)	1.26×

At 10×10: 4.67 pieces against 5.88 cells, a premium of 1.26×. Real, and
smaller than it looks. A shape hint names its whole neighbourhood, so it ought
to be worth four or five cells; it is worth about a quarter of a cell extra.

The reason is the same clause once more: the no-touch rule was going to tell you
most of that neighbourhood anyway. The unprinted clause is not merely the
strongest thing on the board — it is strong enough to make the printed pieces
partly redundant.

The ladder

• count — the numbers and nothing else. A line whose ships are all placed is water the rest of the way; a line with exactly as many open cells as it still owes is ship the rest of the way.
• touch — the clause nobody prints. 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. An unoriented middle resolves the moment either axis closes — including by the edge of the board.
• line — read one row, or one column, the way a nonogram solver does: enumerate every filling consistent with what is known, with the 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; every length still owed has a list of berths. A cell no remaining ship can reach is water. A length with exactly as many berths as ships left is settled outright. 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, drop the assumption if the board dies.

rung	6×6 settled	6×6 finished	8×8 settled	8×8 finished	10×10 settled	10×10 finished
count	76.2%	9/36	48.9%	0/36	58.8%	0/36
touch	89.7%	20/36	81.0%	6/36	80.5%	2/36
line	90.3%	20/36	83.8%	7/36	80.6%	2/36
fleet	100.0%	36/36	100.0%	36/36	100.0%	36/36
probe	100.0%	36/36	100.0%	36/36	100.0%	36/36

Every shipped board is finished by fleet, by construction — the generator keeps
rubbing reveals out only for as long as propagation can still close the board
without guessing. The shape of the climb is what to read. At 10×10 the numbers
alone settle 58.8% of the grid; adding the clause that is never printed takes
it to 80.5%; reading the lines adds 0.1 points; the inventory closes the rest.

The same rungs, priced as pruning

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.

propagation allowed	6×6 branches (median)	6×6 worst	8×8 branches (median)	8×8 worst
up to count	4	67	805	19,613
up to touch	0	10	3	24
up to line	0	10	3	22
up to fleet	0	0	0	0

Arithmetic alone takes a median 805 branch points on an 8×8. Add the no-touch
clause and it is 3 — a 268× cut, against the 62.7× it was worth in the
answer-space table. A clause can be priced very differently by the two
accountings, and there is no way to know which without running both.

Three ways to misread the board

The two structural misreadings are flags on the same solver, so they can be
priced on the shipped boards directly.

misreading	board	intended answer still legal	answers (median, capped at 12)	still unique
ships may touch diagonally	6×6	36/36	1	27/36
the fleet is not fixed	6×6	36/36	1	20/36
a reveal only says a ship is there	6×6	36/36	2	18/36
ships may touch diagonally	8×8	36/36	2	18/36
the fleet is not fixed	8×8	36/36	2	13/36
a reveal only says a ship is there	8×8	36/36	4	8/36

All three are generous misreadings — each only relaxes a constraint, so the
intended answer stays legal on every board and nothing looks wrong until the
end. What breaks is uniqueness. Forget the word "even" and only 18 of 36 8×8
boards still have one answer; read the printed pieces as mere counters and it is
8 of 36.

You do not get stuck. You get a board with several answers and no way to tell
which one the setter meant — which is the failure mode actually worth guarding
against.

Tests

37 tests (npx vitest run). The ones that matter:

• sweep vs enumeration vs brute force — on small boards, the row-at-a-time DP, a depth-first enumeration, and a "walk every subset and test it" brute force all return the same number.
• search vs enumeration — on real 5×5 boards, the number of answers solve finds is exactly the number an enumeration finds, at every rung. If any rung proved something false the search would miss answers and call an ambiguous board unique, so this is the soundness test that matters.
• two OEIS sequences — checked both from the committed counts.json and recomputed on the spot.
• the sampler — every draw is legal; the exact marginals match a full enumeration to nine decimal places; 40,000 draws land within 2% of them.
• the shipped bank — exactly one answer per board, and it is the intended one; the numbers match the answer; every revealed piece is the shape the answer actually shows there; removing any one reveal breaks the board.
• the ladder — no rung ever proves anything the answer disagrees with, and each rung settles at least as much as the one below it.
• individual rules — including a regression test for a bug I shipped into the first draft: the count rung's "a line with exactly as many open cells as it owes is all ships" half never fired, thanks to a dangling else binding to the wrong if. It was sound — it never proved anything false — just silently missing. The ladder table and the pruning table both moved noticeably once it was fixed (8×8 pruning went from a median of 4,807 branch points to 805), which is a good argument for measuring rungs individually rather than trusting that a propagator does what you wrote.

Every number on the page and in the README is generated from counts.json and
stats.json by npm run notes. Nothing is transcribed by hand.

Takeaways

• Battleships prints the fleet and the numbers, and neither is what solves it.
• Not even diagonally — never printed — moves the answer space by 62.7× on an 8×8 standard board, and moves the search by 268×.
• The standard armada has 1,855,545,978,831,780 places to hide on a 10×10, and none at all on a 6×6.
• The exact marginals say the fleet crowds the border: a middle cell costs eight neighbours, a corner cell three.
• The numbers are weak. All twelve of them leave a median of five answers on a 6×6, and at 10×10 they finished none of 120 boards.
• A printed shape is worth only 1.26× a bare occupancy reveal — because the no-touch clause was already going to tell you the neighbourhood.

Puzzle #66 in the solver series. MIT licensed.