The Maths Behind Star Chart

Star Chart hides a fixed number of stars on a square grid. A numbered cell counts the stars in the eight cells touching it and never holds a star itself. Every puzzle has one solution, and a chain of deductions reaches it without guessing. Those two promises are not editorial claims about the puzzles. They are properties the generator checks on every board before it ships, and checking them requires writing the game down as arithmetic.

The board as a system of equations

Give every cell a variable x_c that takes the value 0 or 1, where 1 means a star sits there.

A clue cell k showing the value v_k then contributes two facts. The stars around it sum to its number, Σ x_n = v_k where n runs over the eight neighbours of k, and the clue cell itself is empty, x_k = 0. One more equation covers the whole board: Σ x_c = S, where S is the total star count. S is shown to the player, so it is available for deduction as legitimately as any clue.

Stack those rows and the puzzle is a linear system A·x = b, where A is the 0/1 adjacency matrix from clue cells to their neighbours and the solution vector is restricted to {0,1}ⁿ. “Exactly one solution” now means something checkable: the system has exactly one solution over the 0/1 cube.

Deciding whether such a system is satisfiable is NP-complete in general. Richard Kaye proved it for the equivalent Minesweeper question in “Minesweeper is NP-complete”, The Mathematical Intelligencer 22 (2000), by building logic gates out of grid configurations. That result governs boards of unbounded size. A Star Chart board has between 49 and 121 variables, and every clue equation touches at most eight of them, so the search never gets a chance to blow up. Backtracking with propagation finishes one board in milliseconds.

Three rules and one extra equation

The solver in src/games/star-chart/solver.ts does not run Gaussian elimination on the whole matrix. It applies three derivations that a person can carry out on a grid, and it can admit the total-star equation as one more constraint for those derivations to work on.

#	Rule	What it is mathematically
R1	Clue satisfied or clue exhausted	Bound propagation on one equation. Remaining requirement is 0, so every undecided neighbour is 0; or the undecided neighbour count equals the remaining requirement, so every one of them is 1
R2	Subset reasoning between clues	Subtract two equations. When A’s undecided cells sit inside B’s, B − A is a new equation over the cells only B covers, with right-hand side the difference between B’s remaining requirement and A’s
R3	Neighbourhood enumeration	Domain consistency on one constraint. Enumerate the configurations of that neighbourhood, discard those that contradict an overlapping constraint, and keep what every survivor agrees on
—	Global star budget	Admit Σ x_c = S as one more constraint, so R1, R2 and R3 operate on it alongside the clue equations

The last row is not a fourth inference rule, which is why the solver’s RuleId type has three values rather than four. It is a switch on the constraint set. Turn it on and the budget equation joins the pool; every deduction it takes part in is still labelled R1, R2 or R3, with the budget listed among the constraints that produced it.

R1 and R2 together are a restricted Gaussian elimination followed by sign analysis, which is the standard approach in Minesweeper solvers. Restricting subtraction to nested pairs is what keeps the derived equations legible, over a cell set a player can point at.

R3 is the expensive one, so the solver only enumerates constraints of at most ten undecided cells. A clue neighbourhood never exceeds eight and always qualifies. The global equation starts far larger and does not, though late in a solve, once ten or fewer cells remain undecided, it shrinks into range and can be enumerated like any other constraint. Rules run cheapest first: R2 is tried only when R1 stalls, R3 only when both stall, and any successful deduction sends the loop back to R1.

Difficulty is a property of the rule set

Counting clues or timing testers would produce an estimate. Defining difficulty on the operators makes it computable.

• D₁ = {R1}
• D₂ = {R1, R2, star budget}
• D₃ = {R1, R2, R3, star budget}

A puzzle’s rank is the smallest i whose closure under Dᵢ decides every cell. Run the closure, see whether anything is left undecided, and the answer is the same on every machine.

The three tiers are then bounded from both sides. Easy is 7x7 with ten stars and rank 1. Medium is 9x9 with sixteen stars and rank 2, meaning D₂ finishes it and D₁ does not. Hard is 11x11 with twenty-four stars and rank 3. Without the lower bound the hard tier would fill with boards that happen to fall to R1 alone, and the tiers would stop distinguishing anything. Each bank holds 500 puzzles.

Puzzles are built backwards

Building from the answer, the way Sudoku generators do, avoids hunting a large space for the rare grid of clues that happens to have a unique solution.

The script plants S stars at random, then writes the true neighbour count into every non-star cell. The blanks are now exactly the stars, so the solution is unique for free, and the board is as easy as it will ever be.

That baseline is not automatically solvable by the tier’s rules. A star whose eight neighbours are all stars has no clue looking at it, and D₁ has no way to place it. Removing clues only ever makes a board harder, so a baseline that stalls cannot be rescued by any removal sequence. The generator tests the baseline first and replants the stars when it fails. Over 20,000 random layouts that happened about once in 200 on the easy tier, and not once on medium or hard, where the star budget is in play and can place the cell no clue reaches.

Then clues come out, one pass in random order. Remove a clue, run the tier’s closure, and put the clue back if the closure no longer finishes. Because every kept removal makes the board strictly harder, a clue that was put back can never become removable later, so one pass leaves a clue set where no single further removal survives.

Last, the tier below has to fail. For a medium board, D₂ must solve it and D₁ must not, and a board that fails this second test is discarded rather than demoted.

Two solvers checking each other

An accepted puzzle then goes through a backtracking search that counts solutions and stops the moment it finds a second. This search shares no code with the rule solver and has no notion of R1, R2 or R3; it orders cells by how many clues touch them and prunes on remaining requirements.

The point of the second solver is disagreement. If backtracking reports two solutions for a board the rule solver claimed to have solved, or the rule solver derives a value the planted answer contradicts, one of the two implementations is wrong and the generator throws instead of writing the bank. The same check runs over every committed puzzle in the test suite, so a rule broken by a later edit turns the build red rather than quietly shipping unsolvable boards.

Watch it run

The demo below runs the trace on puzzle 25 of the medium bank, a 9x9 board with sixteen stars that D₂ closes in 19 deductions. Each click applies one, outlining the clues it used and shading the cells it decided.

R3 never fires in this trace. A medium board has rank 2, so R1 and R2 decide every cell between them, and the solver reaches the enumeration only once both have stalled, which here they never do. Seeing R3 run takes a hard board, where by construction the two cheaper rules stall at least once.

Steps 1 to 3 are pure R1 on the three zeros. Step 4 is the first subtraction: the 1 in the last column of row 7 needs its star among three cells, all of which lie inside the neighbourhood of the 1 beside it, so the difference is zero and the three cells only the second clue covers are empty. Steps 5 and 7 show R1 from the other direction: each of the two 4s has exactly four undecided neighbours left by then, so all four of them are stars.

Step 17 is the star budget earning its place. Fourteen cells are still undecided and one star is left to place. A 1 in the lower right still needs its star, and only three of those fourteen cells lie in its neighbourhood. Subtracting the clue from the budget clears the other eleven in a single deduction. Two ordinary R1 steps finish the board.

If you would rather do the work yourself, the strategy guide covers the same four moves as things to look for by eye.