What the chip computes: the ASIC puzzle's Star Battle checker

Part 1 found the 121 bits that make the Jane Street puzzle chip print (* TWO STARS *). This post is about what those bits mean.

Start with the puzzle itself. The rules:

• Two stars in every row.
• Two stars in every column.
• Two stars in every region. The regions are the outlined areas.
• No two stars touch, not even at a corner.

Click or tap a cell to place a star. Check prints what the chip prints for the grid as drawn. The counts in the margins and the red cells are helpers; the chip itself only prints the message. Near miss loads a grid that breaks only the touching rule. Solution loads the key.

Those 121 cells are the chip’s 121 input bits, top left first, one row at a time. The chip is a checker for this exact puzzle, and the region map is baked into its gates. The rest of this post is how I found that out.

Two stray messages

After the solve I tried the two inputs anyone would try. 121 zeros prints EMPTY SKY. 121 ones prints BIG BANG. Everything else I tried printed TRY AGAIN.

I didn’t know what these meant, nor did I know what the chip computed. But another person who solved the puzzle asked me whether I recovered the Star Battle game. A published puzzle genre, two-star on 11 by 11 is a standard size, and the rules are the four at the top of this post.

Read the three messages again. An empty sky: no stars. A big bang: every cell a star. (* TWO STARS *): the rule. That pushed me to experiment more.

Counting the key

Lay the key out 11 wide, first bit top left.

Two per row. Two per column. No two sharing an edge or a corner. The grid under the key was the decoding the whole time.

There’s more constraints on the puzzle than these rules though. The solver finds more than a thousand grids meeting the criteria above. We know from Z3 in part 1 the chip has a unique solution. What shrinks the solution space is the Star Battle regions. Multiple regions satisfy the correct input, so I tried recovering them from the chip.

Where the regions live

A flip-flop is one bit of memory; it takes a new value on every clock edge. A gate computes a value from the wires feeding it and remembers nothing. This chip has 92 flip-flops and 636 gates. Everything it knows between one input bit and the next lives in those 92 bits.

That already kills the design I guessed in part 1, a stored answer compared against the input. 92 bits cannot hold a 121-bit key, or the 121-cell grid being checked. The chip has to judge the grid as it streams past, keeping running counts.

The whole state of the chip is the 92 squares on the right. The grouping is what the rest of this section works out.

So think about what a Star Battle checker has to keep, and look for it. Where the current cell sits: a row number and a column number. Stars per row, per column, per region. Whether a star has landed next to another. The total.

During the solve I had sorted the 92 flip-flops by their input cones, the gates between a flip-flop’s input and the flip-flops and pins that feed it. The size of a cone says how much logic decides that bit; its sources say what the bit depends on. With the checklist above, the groups read off:

• 9 flip-flops that depend only on enable and each other. A 5-bit counter that runs 0 to 10 and wraps, and a 4-bit counter that steps on each wrap. The column and row of the current cell.
• 22 flip-flops in eleven pairs, a handful of gates each, fed by the input bit and the column counter. A 2-bit tally per column.
• 22 flip-flops in eleven pairs, about 150 gates each, fed by the input bit and both counters. A 2-bit tally per region. The 150 gates in front of each pair decide, from row and column, whether the current cell belongs to that region. Eleven of those is a 121-entry lookup table. The region map, written in gates.
• 12 flip-flops in a chain fed from the input pin, plus one flag. The last twelve bits, and a bit that remembers whether a star ever landed next to another. Why twelve is below.
• 3 flip-flops: a row tally, cleared at each row end, and a latch that remembers if a row ever ended with a count other than 2.
• 8 flip-flops: the total star count.
• 15 flip-flops at the far end of the die: the output generator. A character counter, the 8-bit register that drives O, and success.

Placement backs the reading. Across the die, about 180 um wide:

Role	Flops	x (um)	Gates per flop
column position, 0 to 10	5	26-31	3-5
row position, 0 to 10	4	29-33	4-8
last 12 input bits	12	75-85	2
touch flag	1	88	8
row tally (2 bits) and row-error latch	3	79-82	6-8
total star count (7 bits used)	8	76-83	4-7
column tallies, 11 x 2 bits	22	113-116	4-7
region tallies, 11 x 2 bits	22	114-123	151-154
success and done	3	168-172	1-48
character counter	4	168-170	2-3
character register, drives O	8	167-175	9-15

Left to right: position, then the window and counts, then the tallies, then the output generator. The roles came from the cones. The placement agrees with them.

Watching it run

The simulator can print every flip-flop after every clock, so I fed the key and watched the groups. The bit order inside each counter was unknown, so the script tries every permutation of a group’s flops and keeps the one under which it counts up by one most often.

The key going in one bit per frame. Every number beside the grid is read from the flip-flops after that clock edge, nothing is computed by the animation.

The first two rows in detail:

Edge	Cell	Bit	Column tally	Region tally	Last 12 bits, newest left	Row tally	Total
11	(0, 7)	1	column 7: 1	C: 1	100000000000	1	1
12	(0, 8)	0			010000000000	1	1
13	(0, 9)	1	column 9: 1	D: 1	101000000000	2	2
14	(0, 10)	0			010100000000	0, row done	2
15	(1, 0)	1	column 0: 1	A: 1	101010000000	1	3
20	(1, 5)	1	column 5: 1	B: 1	100001010100	2	4
25	(2, 0)	0			000001000010	0, row done	4

Decoded state while the key’s first two rows go in. Region letters are the ones assigned when the regions are recovered.

The position counters behave as read. After cell 120 the column counter jumps to 16 and stays: done.

On every star the column tally, the region tally, the row tally and the total go up together, and the bit enters the chain. The row tally is checked against 2 and cleared at each row end. The total reads 22 at the end.

The key never puts a third star anywhere, so it cannot show what a 2-bit tally does past 2. A grid with row 0 and column 0 filled does. Column 0 takes eleven stars and reads 1, 2, 3, then 3 for the rest. The region and row tallies do the same. The tallies saturate. Otherwise six stars in a column would wrap round to 2 and pass.

Edge 125: enable has dropped, success goes high, and O shows (. One character per clock after that.

The touch check in 12 bits

The no-touching rule looks like it needs the whole grid. It needs twelve bits.

Where a star’s earlier neighbours sit in the stream. Moving up one row is eleven cells back, so the three cells above are 10, 11 and 12 back, and the cell to the left is 1 back.

The 12-flop chain is that window. When a star arrives, the flag sets if there is a star 1, 10, 11 or 12 cells back. Two stars that touch are always seen from whichever comes second, so those four directions cover all eight. A star in column 10 followed by one in column 0 of the next row is 1 bit back but not a neighbour, and the column counter excludes it. I probed two stars at every offset up to 13 against the plain rule, 1542 inputs: no disagreements. For the key the flag never sets. What the chip says when it does is in an appendix.

Recovering the regions

Reading the 150-gate lookups was unnecessary. Feeding the chip a grid with a single star shows which region tally moves, so that cell belongs to that region. 121 runs, one per cell, gave the whole map.

One star per cell, 121 runs. After each run the tally that moved names the cell’s region.

AAAAABBCDDE
AAFAABCCDDE
AAFBBBBCCDE
AAFBGGGECCE
FAFBGEEEEEE
FFFBGGGEHHH
BBBBBBGEHII
BJJJGGGEHII
BJJKEEEEHII
BBJKKEEEHHH
BJJKEEEEEEE

Region	A	B	C	D	E	F	G	H	I	J	K
Cells	14	21	7	5	28	8	11	9	6	8	4

Eleven regions, all edge-contiguous. These are the outlines in the grid at the top of this post. The key has two stars in each.

Then close the loop without the chip. Write down only the rules, two per row, column and region, no two stars sharing an edge or a corner, over this map, and ask Z3 for every solution. One. It is the key.

The uniqueness proof in part 1 unrolled 636 gates over 129 cycles. This one never mentions a gate. Two encodings that share nothing, one answer. The regions are the puzzle, and they are the one part of the chip a person designed by hand.

What I learnt

Step 3 of my plan in part 1 was “reconstruct chip function by hand, Minesweeper on steroids”. I never did it by hand, and the function turned out to be a cousin of Minesweeper.

The tools were enough on the day of the solve. The question was not. Once a comment on a post supplied the hypothesis, the same simulator gave the counters, the touch window, the message table and the region map, one experiment at a time. None of it came from reading the layout.

Each step was checked against something that did not depend on it. The extractor against the warmup and the simulator against the waveform in part 1. Here, the flop roles against the trace, the touch flag against the plain rule, and the regions against a solve that never mentions a gate.

Appendix: why the key does not fix the regions

Write the region rule as arithmetic. The key is a set of 22 cells. A region map is a partition of the 121 cells into eleven connected pieces . The map agrees with the key when for every , and it is a puzzle when the key is its only solution.

The first condition is not a very useful constraint. It says nothing about the 99 empty cells beyond keeping each region connected. The real map is one way to split them. Move one empty cell across a boundary and you have another map that agrees with the key just as well.

Uniqueness is a better condition, so the question is whether it singles out the real map. The test: take every empty cell, move it into each neighbouring region, discard any map where a region comes apart, and ask Z3 for all solutions of the altered puzzle under the four rules.

Left, the real map. Right, one of the alternatives: cell (0, 4) moved from region A to region B. Both have the key as their only solution.

Variant of the real map	Maps tried	Key is the unique solution
one empty cell moved	47	38
two of those moves applied together	677	671

Uniqueness is a property most nearby maps share, not a fingerprint of the real one. Nothing in the 121 input bits separates these maps from each other, so the boundaries cannot be recovered from the key. They had to come from the chip.

Appendix: the fifth message

The touch flag never set for the key. Rather than guess at grids that set it, ask for every message the chip can print.

The simulator can run with the 121 input bits symbolic, so the printed string is a formula over them. Ask Z3 for an input whose string is not TRY AGAIN. Run it, read what it printed, block that message, ask again. When Z3 answers unsat, every possible input prints one of the messages already found. It stopped at five:

Message	Inputs that print it
TRY AGAIN	almost everything
EMPTY SKY	all zeros, only
BIG BANG	all ones, only
TWO"NOT TOUCH	a family of near misses, every one with 22 ones
(* TWO STARS *)	the key, only

The quote mark is what the chip prints. Every input in the fourth row has two stars per row, column and region and at least one touching pair. This one has exactly one:

The near miss with the fewest touching pairs, found with Z3 and run through the simulator. The pair is in red.

Compare the chip’s flip-flops after the key and after this grid. A single one differs: the touch flag. Set it in the key’s final state and the chip prints TWO"NOT TOUCH. Clear it here and it prints (* TWO STARS *).

Traced, the star at (10, 3) arrives on edge 117 with a star ten cells back in the chain, at (9, 4), its up-right neighbour. The window reads 100000100010. The flag sets on that edge and stays. Every other group matches the key’s trace: every tally 2, total 22. On edge 125 success stays low and the output starts T, W, O.

The eight-flop total does one more job. It selects which of five fixed strings the output generator plays. Flip any one of those eight in the final state and the message turns into garbage like ,[.R..%>1...d, because the generator is reading a string that does not exist. Patch the total properly and replay:

State after 121 cells	Message
total star count 0	EMPTY SKY
total star count 121	BIG BANG
every row, column and region tally 2, touch flag set	TWO"NOT TOUCH
every tally 2, no touch, total 22	(* TWO STARS *), success
anything else	TRY AGAIN