Under the hood

How our Star Battle solver works

Most solvers search for the answer and hand it over. Ours works the board the way a strong human solver does: it always takes the easiest deduction left, and every step says which rows, columns and regions it used and why the move follows.

Step through a real solve

This 10×10 board was made for our archive and retired before it was ever published. Press Play, or tap Next to go one step at a time. The rows, columns and regions a step talks about light up, the cells its argument rests on are dashed, and the cells it changes are ringed.

Solve walkthrough Step 1 of 60

The technique ladder

The solver tries techniques in a fixed order, easiest first, and starts again from the bottom after every step. So a move is only ever explained with a harder technique when nothing easier works at that moment. Our difficulty grades come from the same engine: every step scores by how hard its technique is, and a board’s grade adds those scores up.

How often each rung was needed, across 419 boards from our archive at every size and level. On 115 Inkwell Stars boards, which are made by hand, the harder rungs come up more: counting on half of them, a case split on one in five, and a what-if on 10, most of them finned counts.

  1. 1

    Crosses and full lines

    Every board

    A star rules out the eight cells around it. A row, column or region with both stars rules out the rest of itself, and one with exactly as many open cells as stars left fills them.

    In the solve above, step 6: Stars never touch, not even diagonally, so the 4 open cells around the star in row 10, column 8 can't hold a star.

  2. 2

    Small shapes

    Every board

    Patterns in the last few open cells of a row, column or region: the middle of three cells in a line can’t hold a star, a cell touching both of a region’s last two options can’t either, and a star that would touch all of a region’s other cells is impossible.

    In the solve above, step 2: Region 1 still needs two stars. A star here would touch every other open cell in it, leaving nowhere for the next star, so this cell stays empty.

  3. 3

    Groups of touching cells, and the squeeze

    61% of boards

    Open cells that touch each other can only hold so many stars between them, the way a 2×2 block holds at most one. When a row, column, region or pair of rows has only just enough room, every group must be full, and the cells next to them empty out.

    In the solve above, step 7: Region 3 still needs two stars, and its open cells form one group of touching cells that can't fit any more than that. Every way of placing them puts a star next to the highlighted cells, so they can't be stars.

  4. 4

    Counting

    28% of boards

    If three regions sit entirely inside three rows, those regions supply all six of the rows’ stars, so nothing else in those rows can be a star (undercounting). The mirror image works too (overcounting), and so do bands of any width.

    In the solve above, step 32: Rows 5–7 need 6 stars. Regions 3 and 6 can only finish inside them, so they add 3 stars there. That leaves exactly 3 stars for the band's other 7 open cells. A star on any highlighted cell would leave room for fewer than 3 stars that don't touch among those cells, so the highlighted cells are empty.

  5. 5

    Several lines and regions at once

    5% of boards

    Take a few rows, columns and regions that overlap and list every way their remaining stars can fit together. A cell no arrangement uses is empty; a cell every arrangement uses is a star.

  6. 6

    Case split

    9% of boards

    When a row, column or region has only two or three ways left to place its stars, follow each one a few forced moves. A way that breaks something is out; whatever every way that works agrees on is certain. It’s the “its last star is here or there, and either way…” argument.

    In the solve above, step 33: Row 8's last star can only go two ways: row 8, column 4 or row 8, column 6. At row 8, column 4, it forces 4 more stars. At row 8, column 6, it forces 3 more stars. Either way, the highlighted cells are ruled out, so they can't be stars.

  7. 7

    What if?

    1% of boards, all expert

    Suppose a cell held a star, follow what it forces, and see a row, column or region break. Kept short: at most eight forced moves, the kind of chain you can hold in your head. When the only fallout is crossed-out cells, solvers call it pressured exclusion or a finned count.

  8. 8

    Longer what-ifs

    Under 1% of boards

    The same idea with longer chains. This is computer-strength work, so it only runs when nothing easier is left.

  9. 9

    Guessing

    No boards

    Try a star, back up if it fails. A well-made puzzle never needs this, and the solver tells you if it ever does.

How it knows there’s one answer

A real Star Battle has exactly one solution, and some techniques lean on that. So before explaining a board you painted, the solver checks it. It runs the simple deductions, and when they stall it tries a star in the most constrained open cell, follows the board both ways, and keeps going until it has found every answer or a second one. One answer: it explains the solve. Two: it shows you both and outlines the cells where they disagree, which is almost always where a region was painted a cell off. None: it says no arrangement fits.

Speed and limits

Nearly every board, easy to hard, is solved in well under a tenth of a second. The hardest expert boards take longer, because the what-if and several-at-once techniques have more to check. Each board you paint gets a few seconds; if that isn’t enough the solver says so plainly instead of guessing. Boards from our daily puzzles, Two Not Touch and Inkwell Stars are worked out ahead of time, so they open instantly.

It handles two-star puzzles from 8×8 to 11×11. One-star puzzles like LinkedIn Queens and Netflix Starstruck count differently and aren’t supported here yet.

Where the names come from

Undercounting, overcounting, the squeeze, pressured exclusion and finned counts are the puzzle community’s names, as used in Kris De Asis’s Star Battle guide. Our Star Battle strategy guide walks through each technique on real boards.

Solve your own board