The licence that weighs nothing

One half multiplies, the other adds gave the two halves of a substitution licence closed forms and found they grow at different orders — the component half geometrically in the number of boards, the subposition half linearly. It closed on the step it had measured once and never priced:

Its growth ought to be the flattest of the three, since a catalogue of regions does not grow with the sum or with the board, and if it is genuinely constant then the sequence of three licences is geometric, linear and constant.

It is constant, to every digit. That is the least interesting thing on this page.

The three licences #

A substitution licence is permission to replace one thing by another inside a sum without changing what the sum is worth, and each of the three replaces something coarser than the last.

The component licence says a component may be replaced by any position with the same value, so a solver keys its table on values rather than on product states. The subposition licence says a position may be replaced by any position with the same free squares, so the table is keyed on shapes. And the region licence — the third — says a position may be decomposed into its connected regions and each region substituted for, so the table is keyed on regions.

Each is a refinement of the one before, and the savings multiply.

At three copies of a $3 \times 3$ board, the component licence collapses 941,192 product states to 294 and is worth 3,201 times. The subposition licence takes those 294 to 17 and is worth 17 times. The region licence takes 17 to 7 and is worth 2.43 times.

Read as savings, the third licence is the one to drop.

One thing about that ordering needs stating, because it is what the whole page turns on. The three licences are nested: every pair of positions the region licence identifies, the subposition licence identifies as well, and every pair the subposition licence identifies, the component licence does. So applying them in order is applying successively coarser identifications, and the savings multiply to give the whole collapse — 941,192 states to 7 entries on the largest case measured.

That means each licence’s saving is measured on top of the ones before it, and the number a licence gets depends on where in the queue it sits. Keep that in view; it comes back at the end and it is the reason the third licence’s number is small.

It is constant #

The rung below’s prediction is confirmed with no qualification. The region saving on a $2 \times 3$ is $1{\cdot}750$ at one copy, at two copies and at three; on a $3 \times 3$ it is $2{\cdot}429$ throughout; on a $2 \times 4$, $2{\cdot}833$. The component saving over the same three columns goes $1$, $49$, $3{,}201$.

The reason is one sentence and it is the rung below’s: a catalogue of connected regions does not know how many boards are on the table. Adding a copy adds product states and adds table entries to the component licence; it adds no new region, because a region is a connected piece of one board and the boards are the same board.

Taken out to eight components — from the closed forms, past what the enumeration reaches — the component licence is worth seventy-six million times, the subposition licence twenty and a half, and the region licence one and three quarters. Geometric, linear, constant.

And that is the wrong way to price it #

A licence is not a number. It is a catalogue a solver has to build, store and consult, and the three catalogues are of quite different sizes and grow in quite different ways.

At three copies of a $3 \times 3$: the component licence’s table holds 294 entries, the subposition licence’s 17, and the region licence’s 7.

More to the point is what each is a function of. The component table is $k \cdot s$ — it grows with every board added, for ever. The shape table is $|\text{shapes}|$ — it grows with the board and not with the sum. The region table is $|\text{regions}|$ — 2, 4, 6, 7 for the four boards here — and grows with neither.

So the licence that saves least is the only one whose cost does not run away. Priced by savings the order is geometric, linear, constant; priced by tables it is unbounded, board-bounded, nearly constant. The two readings order the three licences oppositely, and only the second is a statement about whether a solver can carry the licence at all.

Mixing the boards #

The sharpest version of that is what happens when the boards are not copies of each other.

Across the six mixed sums, the component table runs from 36 to 170 entries and the shape table from 7 to 34. The region table runs from 4 to 9 — it spreads $2{\cdot}3$ times where the shape table spreads $4{\cdot}9$.

And one row explains why. A $2 \times 3$ board’s regions are 4; a $2 \times 4$ board’s are 6; a sum of the two has 6. Every connected shape a $2 \times 3$ can leave behind is a connected shape a $2 \times 4$ can leave behind, so mixing them adds nothing to the catalogue. The region catalogue of a sum is very nearly the region catalogue of its largest board.

That is what makes the third licence’s cost a property of one board rather than of a position, and it is the property the first two licences do not have.

What a region catalogue actually holds #

It is worth looking at the seven entries, because seven is a surprising number for a $3 \times 3$ board and the reason is the whole mechanism.

A region is a connected set of free squares that a Cram position can leave behind on that board. On a $3 \times 3$ there are seven of them up to congruence — the single square, the domino, the two trominoes, and so on up to the whole board — and every position of every sum of $3 \times 3$ boards decomposes into some multiset of those seven.

That is why the catalogue does not grow with the number of boards: a hundred boards leave a hundred regions, and each of the hundred is one of the seven. It is also why it barely grows when the boards differ: the regions of a smaller board tend to be regions a larger board can leave too, so the catalogues nest rather than accumulate.

Compare the shape table, which holds seventeen entries on the same board. A shape is a whole board’s free squares, connected or not, so the shape table has to hold every combination of regions the board can leave at once — and combinations are what multiply. The step from seventeen to seven is exactly the step from a combination to its parts, which is the board falls apart applied to a catalogue rather than to a position.

What this means for a solver #

Put the three together and the practical reading is not the one three rungs of this anchor have used.

A solver with memory to spare should take all three, and the arithmetic says why: the total collapse at three copies of a $3 \times 3$ is 941,192 states to 7 entries, and the first licence does almost all of it.

A solver without memory to spare faces a different question — which licence can it afford to keep? — and there the order inverts. The component licence’s table is the one that grows with the problem, so it is the one a solver runs out of room for first. The region licence’s table is seven entries on a $3 \times 3$ and seven entries on a hundred copies of a $3 \times 3$.

A product against a sum is where the first licence was priced and where the saving was the whole story, and it is the page this reframing is against. Nothing there is wrong; the quantity it priced is one of two, and the other one is the one that decides whether a licence is usable.

The anchor’s arithmetic, in one place #

Seven rungs in, the numbers on this anchor can be put in a single sentence, and it is worth doing because they have been arriving one at a time.

For $k$ copies of a Cram board with $s$ states, $|\text{shapes}|$ free-square configurations and $|\text{regions}|$ connected pieces, a solver’s state count falls

$$s^k \ \to\ k\,s \ \to\ |\text{shapes}| \ \to\ |\text{regions}|$$

with the three ratios $s^{k-1}/k$, $k\,s/|\text{shapes}|$ and $|\text{shapes}|/|\text{regions}|$. On three copies of a $3 \times 3$ that is $941{,}192 \to 294 \to 17 \to 7$.

Everything this anchor has measured is a value in that chain, and the chain’s last term is a constant of the board. That is a satisfying place for seven rungs of work to arrive, and it is worth noticing that the whole chain rests on a single earlier result — equal in this company’s apparatus for deciding equality inside a restricted universe, without which none of the three substitutions is legitimate at all.

Why a saving and a table pull opposite ways #

The inversion is not a coincidence of these three licences, and it is worth stating generally.

A substitution licence collapses a state space by identifying states, and its saving is the ratio of the space to the number of classes. So a licence saves a great deal exactly when the space is much larger than its table — which is another way of saying the saving is large when the table is small relative to the problem, not when the table is small absolutely.

The component licence has a large table and an enormous space above it. The region licence has a tiny table and, by the time it is applied, a tiny space above it too, because the other two licences have already collapsed almost everything. Its saving is small because it is last in the queue, not because it is weak.

Applied first, on the raw product states, the region licence would collapse 941,192 to 7 on its own — the whole of the total. So the order the licences are applied in is what assigns them their savings, and the tables are what does not depend on that order.

The figures, and the position not drawn #

Six tables of counts, and there is one picture that would carry more than all of them: a $3 \times 3$ board part-covered, drawn three times — once whole, once split into its connected regions, and once with each region replaced by its entry in a seven-item catalogue.

That is the third licence in a single image and it is not here. What the tables give instead is the arithmetic of the catalogue, which is the part that cannot be seen: seven entries is a small number and seven entries however many boards there are is the claim, and a claim with a quantifier in it does not fit in a drawing.

The board falls apart draws the decomposition itself, and which shapes are worth fighting over draws the regions and prices them by their values. A reader who wants to see what a region catalogue is made of should read those; this page is about how large it is and how that number moves.

What this does not settle #

Cram, and small boards. The four boards are $2 \times 2$, $2 \times 3$, $2 \times 4$ and $3 \times 3$, which is what the enumeration reaches with the product state space taken exhaustively. The closed forms extend and the enumeration does not.

A table size is not a cost. Counting entries ignores what an entry holds and what a lookup costs, and a region catalogue’s entries hold values that are cheap only because the regions are small. A fair accounting would price the work of decomposing a position into regions on every lookup, which the component licence does not have to do, and that is not measured here.

The order-independence claim is arithmetic and not a measurement. Applied first, the region licence collapses the whole space follows from the three licences being nested refinements; no solver has been run in that order, and a solver applying region substitution to raw product states would be doing the decomposition work at every node.

And the third licence is worth something on a mixed sum. The saving rises from $1{\cdot}75$ on copies of one board to $3{\cdot}78$ on the three-board sum, because mixing adds shapes faster than it adds regions. So worth under two times is a statement about copies, and the licence is worth more exactly where the boards differ — which is where a real game is.

The four boards do not separate the two readings much. Region tables of 2, 4, 6 and 7 against shape tables of 3, 7, 17 and 17 is a clear gap and it is four data points, and both grow with the board — the region table just grows more slowly. Grows with neither is exact for the number of components and approximate for the board, and the page says nearly constant for that reason.

Normal play, Cram throughout, and equality is equality in this company rather than in every company, which is what a restricted universe means.

What a licence is, once more #

There is a temptation to read all of this as bookkeeping about tables, and it is worth returning to what a substitution licence is for before the ladder moves on.

A solver searching a sum of Cram boards is trying to avoid looking at the same thing twice. What counts as the same thing is the whole question: two product states are the same if the solver can prove they behave identically in every continuation, and proving that is exactly what a restricted-universe equality argument does. So a licence is not an optimisation bolted on afterwards — it is the statement of what the solver’s table is a table of.

Read that way, the third licence says something quite strong about Cram: a position’s future is determined by the multiset of connected regions it leaves, and nothing else about how those regions are arranged on which boards. That is the disjunctive sum’s whole promise, applied at the finest grain the game allows, and the seven-entry catalogue is what the promise is worth in storage.

The saving being small is then not a disappointment. It is the measure of how much the first two licences had already exploited the same promise, and the fact that the catalogue does not grow is the measure of how completely the third one finishes the job.

Where the ladder goes next #

The universes anchor has seven rungs: equality made computable, which restrictions license rewriting a sum, which license rewriting a subposition, what the second licence is worth, what the first is worth on its own, how the two grow, and now the third and what a licence costs.

The rung above is the decomposition’s own price. Every number on this page counts table entries and none counts work, and the third licence is the one whose work is not in the table: a solver using it must decompose every position it meets into connected regions before it can look anything up. That is a flood fill over the free squares at every node, and whether it costs more than the lookups it saves is a measurement nobody on this anchor has made. It is also the measurement that would say whether the reframing here is a real reversal or an artefact of counting the wrong thing twice.

Two neighbours are worth the trip. One half multiplies, the other adds is where the two orders of growth were found and where the third was left, and it is the page this one completes. And the tree and the graph is the saving that is not a licence at all — the transposition table — and reading the three licences beside it is the site’s whole account of why a solver can do anything.