Calcudoku

The obvious way to read a square off the Jacobson–Matthews chain is biased

Every board starts as a Latin square, and the square should be uniform over all of them — otherwise the bank quietly favours some structures over others. The standard tool is the Jacobson–Matthews chain (1996): treat the square as an n × n × n cube of 0s and 1s with exactly one 1 on every line, and let each move add and subtract 1 on the eight corners of a sub-box. Some moves leave a single -1 behind — an improper cube, not a square — and the next move starts from that cell. The chain is uniform over proper cubes at stationarity.

The obvious way to read a square off it is: run a while, and if the cube happens to be improper, keep stepping until it is proper. That is biased, and the bias is not a mixing problem — running ten times longer does not remove it. On 7 × 7, waiting for the first proper cube after 343 moves gives a mean of 10.110 intercalates against an exact 10.529; after 3,430 moves, 10.107. Total variation from the exact distribution is 0.0473 and 0.0472, against a noise floor of 0.0101 for 20,000 perfect draws.

The reason is where the square is sampled. Waiting for the chain to become proper samples it at the moment it re-enters the proper squares, and a square is re-entered from an improper cube more often when it has fewer proper-to-proper moves. A proper-to-proper move is exactly an intercalate swap — a 2 × 2 subsquare a b / b a flipped to b a / a b: the move lands on a proper cube only when the eighth corner of its box was already a 1, and those eight corners are the four cells of an intercalate. A square with k intercalates has 4k such moves out of n³ − n², so squares with few intercalates are left by the improper route, and re-entered by it, more often — and they are over-drawn. The fix is to condition at a fixed time instead: run exactly 343 moves, keep the square only if the cube is proper at that moment, otherwise throw the chain away. That lands at 10.570 (total variation 0.0105), and it costs 6.83 chains per square: the stationary chain is proper only about 15% of the time.

The naive generator — fill cells in reading order with shuffled values, backtrack on a dead end — is biased too, in the same direction: 9.909 intercalates on 7 × 7 (total variation 0.0659). Why it leans that way is a separate question; the table only shows that it does.

At every order measured, the fixed-time reader sits inside the 95th percentile of the noise floor and the first-proper reader sits outside it. The fixed-time reader is what the generator uses; the other two are kept only as foils.

The census every sampler is held to

"Exact" above means exact: every reduced Latin square of order 1 to 7 is enumerated — first row and first column in order — and its intercalates counted. Permuting rows and columns never changes the intercalate count, and every square is a row-and-column permutation of exactly one reduced square in exactly n!(n-1)! ways, so the reduced histogram is also the distribution over all squares. Order 7 is 16,942,080 reduced squares (61,479,419,904,000 in all) and takes 41 s.

The counts match OEIS A000315 and A002860 at every order, and the stats run recomputes orders 1 to 6 from scratch each time and stops if the stored histogram disagrees. An intercalate count of 2 × 2 subsquares costs n per row pair: send each column to the column where the second row holds the same symbol, and an intercalate is exactly a 2-cycle of that map.

An intercalate is a second answer waiting for a cage to miss it

Flip an intercalate and the square is still Latin. So if no cage notices the flip — every cage touched by the four cells still reaches its target — the board has a second answer, whatever else is true of it. A cage misses the flip when it holds one cell from each diagonal of the 2 × 2 (the multiset of its numbers does not change), or when it is a two-cell minus or divide cage whose other number happens to sit at the same distance, or the same ratio, from both symbols.

That makes a check that costs nothing next to a search. Across 16,000 boards cut at random, 8,704 came out with more than one answer, and on 6,658 of them (76.5%) a flipped intercalate was already one of the extra answers. The claim in the other direction is a theorem, so it is tested rather than sampled: 0 boards with a surviving flip ever came out unique.

It also predicts which squares make good boards. On 16 of 16 rows below, the squares whose raw cut came out unique had fewer intercalates on average than the squares whose cut did not. A generator that draws a uniform square, cuts it, and keeps only the cuts that come out unique would therefore ship a bank that leans away from intercalates — a biased sample of Latin squares, even with a perfect sampler underneath.

Counts are capped at 50 answers and 100,000 search nodes; a capped search counts as not unique, and the medians are over searches that finished.

Repair, don’t reject — and the bank keeps the sampler’s uniformity

So this generator never throws a square away for being hard to pin. It cuts random cages (sizes weighted towards two and three cells), labels them, and then repairs: while a second answer exists, it splits a cage that holds a cell where the two answers differ. Once the board is unique it tightens: it tries merging neighbouring cages and keeps a merge only if the answer stays unique, until a whole pass of merges is refused. Every search is node-capped, and a capped search refuses the candidate rather than guessing.

Repair always terminates — splitting enough cages turns every cell into a one-cell cage, which pins the answer outright — so every seed yields a board: 40/40, 40/40, 40/40, 40/40, 40/40, 40/40 across the runs below. Because nothing is rejected, the squares in the bank are exactly the squares the sampler drew. The mean intercalate count of the generated boards is within two standard errors of the exact mean on 3 of 3 sizes.

The intercalate check runs before every search. Over the runs with it switched on, it found 93 of 144 repairs (64.6%) without a search. It did not make the generator faster, and the table says so: on 7 × 7 the median board took 206 ms with the check and 224 ms without, and the worst board 26,448 ms against 12,514 ms. Search nodes are close either way (20,566 against 18,622 on 7 × 7), and the wall clock is set by a few slow boards that the node count does not explain. The check stays because it is a proof, not a speed-up: it names the second answer, and the four cells it names are where the split goes.

What an operation sign is worth

Some puzzle books sell Calcudoku with the signs left off as the harder version. Hiding a sign is a clean ablation: the same cages, the same targets, and a cage now holds if any operation its size allows reaches the target. Hiding can only add answers, never remove one, and the test suite checks both that and that every rung stays sound under both readings.

Cage by cage, the sign is worth little. Of 4,041 multi-cell cages cut at random, 2,043 (50.6%) admit exactly the same fillings with the sign hidden. The most informative sign is the quotient on a 2-cell cage: hiding it multiplies the fillings by 2.74 on average (1.46 bits). No 2-cell quotient cage survived hiding untouched: a quotient target is always reachable some other way too. On cages of four or more cells the sum and the product rarely collide, and the sign carries at most 0.11 bits.

Board by board the loss is small too. Over the same 16,000 random cuts as above, 7,296 were unique with the signs shown and 6,711 with them hidden: hiding every sign costs 8.0% of the unique boards. On the shipped bank, which was tightened with the signs shown, 19 of 20 boards still have exactly one answer with every sign hidden — the exception is 7x7-20, which opens up to 2 answers. Tick hide the signs on the page and try it.

The ladder, rung by rung

Each rung is priced twice on the 20 shipped boards (630 cells): climbing — how much the ladder settles with everything up to that rung — and leave-one-out — what the full ladder loses without it, and how much harder the search works without it.

Two things stand out. single is a special case of must: a settled cell sits in some cage, every filling of that cage puts the cell's number on the cell's row and column, so must already takes it off the rest of both lines outside the cage, and cage takes it off the cells inside. Leaving single out of the search leaves the node count exactly where it was, at 149. It stays on the ladder because it is the step a person takes first. Second, leave any one rung out and the rest still finish every board with no search, except probe: drop probe and 14 of 20 finish. The search itself leans on must and hidden: without them it needs 459 and 229 nodes.