Star Battle

Click a cell to cycle blank → dot → star. Dots are just your own notes for cells you have ruled out. Two stars in every row, column and outlined region, and no two stars touching — not even at a corner. Everything runs in your browser; nothing is uploaded.

The no-touching rule throws away all but one arrangement in 9.4 million

Ignore the regions for a moment and ask only how many ways there are to put two stars in every row and column of a 10×10 grid. Counted exactly, there are 1,371,785,398,200. Now add the rule that no two stars may touch, diagonals included. What survives is 146,510 — one in 9,363,084.

That is the whole answer to how much work the rule does. It is not a filter that trims the edges of the problem; it is the rule that removes essentially all of it, and the regions then pick between the handful left standing.

Both columns can be checked against work published independently of this page. The middle column is the count of matrices with exactly two ones in every row and column, catalogued as A001499. The equivalent one-star column is Hertzsprung's problem, A002464 — the permutations with no two consecutive values next to each other. Our counts reproduce both, which is the reason to believe the figures beside them.

The tidy explanation is only half the story

There is a neat argument for why small boards are impossible. If no two stars touch, then any 2×2 block holds at most one, so the most stars an n×n board can hold is ⌈n/2⌉² — put them on every other row and column. A two-star board needs 2n. Compare the two and the small boards fall over: 4, 5, 6 all need more stars than fit.

And then the argument runs out. A 7×7 board needs 14 stars and has room for 16, so the ceiling raises no objection at all — yet there is not one valid arrangement. The bound is necessary and not sufficient, which is exactly why the counts above are counted rather than argued from the bound. The boards that are impossible are 4, 5, 6, 7; the ceiling only accounts for 4, 5, 6.

An 8×8 two-star puzzle has only one possible answer — whatever its regions

An 8×8 board needs 16 stars and has room for exactly 16, so it sits precisely at the limit. The count of arrangements is 2 — and those two are the same picture reflected, so up to rotation and reflection there is exactly one 8×8 two-star board:

That has a consequence worth pausing on. Every 8×8 two-star puzzle ever printed, whatever regions it draws, has that arrangement as its answer. The regions cannot change it; they can only make it easier or harder to find. It is the only size on the menu above where the puzzle is a formality. The board is also symmetric onto itself — its 2 distinct images under the eight rotations and reflections, rather than the full eight, mean it maps back to itself four ways.

The generator sees the same thing backwards

Puzzles here are made by drawing random regions and keeping the ones that admit exactly one arrangement. If 8×8 really has a single board, then any 8×8 partition that admits an arrangement at all should admit exactly one — and that is what happens:

Not one 8×8 partition in 400 had more than one answer. At 10×10, where there are 146,510 arrangements to choose between, nearly every solvable partition admits several and only about one in two hundred pins a single one. That is why a 10×10 puzzle takes a moment to generate and an 8×8 appears instantly.