Star Battle: why every puzzle is checked for a single solution

A Star Battle puzzle asks for very little: put one star in every row, every column and every outlined region, and never let two stars touch. The rules fit in a sentence. What makes a puzzle good or bad is not the rules but the shape of the regions, and the most important property of that shape is invisible when you look at the grid. The puzzle has to have exactly one answer.

What goes wrong with two solutions

Imagine you have worked through a grid carefully. You crossed out cells, placed stars, and reached a point where two cells in the last region are both possible. Nothing in the rules tells you which one is right. You pick one, the board lights up, and you feel cheated rather than clever. Logic puzzles promise that thinking is enough. A grid with two answers breaks that promise, because the final step was a coin toss.

This is also why our hints never guess. A hint places a star from the known solution, and that only makes sense if there is one solution to draw from.

A region shape we threw away. Both boards obey every rule, so the puzzle cannot be solved by reasoning alone.

How a puzzle is born

We do not draw regions first and hope a solution exists. We work backwards.

1. 1Place the stars first. We pick a valid set of stars at random, one per row and column, none touching.
2. 2Grow the regions around them. Each star becomes the seed of a region. Regions then spread into neighbouring empty cells in random order until the grid is full.
3. 3Count the solutions. A solver looks for every star arrangement the regions allow. If it finds more than one, we move a single cell on the border between two regions and count again, keeping each change that brings the number down.
4. 4Start over when it gets stuck. If reshaping cannot get the grid down to one answer, the board is thrown away and a new one begins at step one. Most puzzles need a few fresh starts.

The solver in one paragraph

The checker walks the grid one row at a time. In each row it tries every column that is still free, skips any column next to the star in the row above, and skips any region that already has its star. When it reaches the bottom row it has found a solution and adds one to a counter. It keeps searching until it has seen enough to know whether the board is finished: one solution means we are done, more than one means another cell has to move. A single check on a 6×6 grid takes a few thousandths of a millisecond, so we can afford to run it well over a hundred times for every puzzle we keep.

Unique is not the same as fun

A single solution is the floor, not the ceiling. A puzzle can be unique and still be dull if the only way through is trying every option in your head. So after the uniqueness check we run a second pass that solves the puzzle the way a person would, using only the kind of deductions explained in the tips on starbattle.gg: small regions, crossing out neighbours, regions trapped in one row. If that pass gets stuck, the board is too hard for its size and we discard it too. On bigger grids we also refuse regions made of a single cell, which give the game away.

That second pass is strict. About two out of every three boards that reach a single solution still fail it and are replaced. The daily 6×6 puzzle is built from the date, so everyone in the world gets the same grid, and it only appears once it has passed both checks.

Try it yourself

Today’s puzzle is waiting at starbattle.gg. If you ever reach a point where two cells seem equally possible, look again at the regions around them. There is always a reason, and finding it is the whole game.