A full search of the 16×16 is only worth discussing once its size is known.
This experiment measures it for the simplest strategy: place pieces row by
row, bottom row first, left to right, and count every valid partial board
(a node) until the whole tree is exhausted. The questions were how big that
tree is on the real pieces, whether a first-moment model of random boards
predicts it, and whether the official piece set looks unusual next to boards
painted from the same colour counts. Nothing here is a record attempt, and no
board is produced.
The tree has about 10^40 nodes, so it cannot be enumerated. It is
estimated by a population (sequential Monte Carlo) method: 1,000,000
particles are extended one cell at a time, resampled as they go, and the
estimate of each level's width is unbiased. The
estimator can fail low, because a population can collapse onto a few
families, so the work is in the checks before any real number is read.
Node means a valid partial board after a placement on a free cell, with the
rim grey, the clues on the board from the start, and the scan order rows 15
to 0, columns 0 to 15. The model is an analytic first-moment computation, not
a simulation, so agreement with it is not circular.
| Check | Result |
|---|
| 30 hard-ladder 6×6 boards, exact tree against estimate, 200 repetitions | 10 of 1,110 (instance, level) pairs more than 3 standard errors off (0.90%); median absolute log10 error 0.0050, maximum 0.023 |
| Exact count of complete official frames (the only exact 16×16 count in the repository) | estimate over exact 0.99994 |
| 40 generated 5×5 and 6×6 boards, N = 1000 | median absolute log10 error 0.0023, maximum 0.032 |
All three pass their preregistered limits. A second analysis then recomputed
every headline number from the raw rows and re-ran the five-clue N = 1e5
repetitions, with identical totals (independently re-checked).
Base-10 logarithm of the mean node count, five repetitions per row, 95%
t interval over repetitions.
| Clues | N | log10 nodes | 95% interval | Model | Measured minus model | Widest level (free depth) |
|---|
| five | 1e6 | 40.457 | 40.440 to 40.473 | 40.49 | -0.033 | 158 |
| five | 1e5 | 40.497 | 40.414 to 40.567 | 40.49 | +0.007 | 158 |
| centre clue only | 1e5 | 47.140 | 47.061 to 47.208 | 47.14 | +0.0004 | 160 |
| none | 1e5 | 50.039 | 50.017 to 50.059 | 50.03 | +0.009 | 161 |
With five clues the full tree is 10^40.457 nodes, or 2^134.4. The widest
level, at free depth 158, holds about 10^39.16 nodes. The four clues beyond
the centre one cut the tree by 10^6.68 (47.140 against 40.457).
With no clue the tree also carries the four-fold corner symmetry, since no
clue fixes the orientation. A search that stops at the first solution costs
about half the tree (one bit less) when there is one solution; the full-tree
figure is the right unit for the price.
The measurement agrees with the model to within 0.04 digits (differences in the table). At N = 1e6 the model value 40.49 sits just above the 95% interval (40.440 to 40.473); the N = 1e5 intervals contain it. The model figures are carried over from the earlier pricing, not recomputed here. A rerun of the same
estimator in a second experiment, on the same pieces, gave 10^40.453 with
interval 40.422 to 40.481, within 0.004 digits of the first.
Twenty boards were painted with the official colour counts exactly (frame
joints from the official frame-colour multiset, seam and inner joints a
uniform deal of the inner colours), five clues read off each, two estimates
of N = 1e5 each.
| log10 nodes |
|---|
| painted boards, median | 40.61 |
| painted boards, range of 20 | 40.33 to 40.76 |
| painted boards, standard deviation (about 0.05 of it estimator noise) | 0.125 |
| official set (N = 1e6) | 40.457, with 5 of the 20 painted boards below it |
On this one statistic the official set is ordinary: nothing in the tree size
distinguishes it from a board painted from the same colour census. Five
other painted boards, run at N = 1e6 in the second experiment, gave 40.515,
40.412, 40.464, 40.480 and 40.438. The painted boards sit 0.12 digits above
the model in the median; whether that is a planted-solution effect or a detail
of the colour census the model does not carry was not determined. The test
says nothing about any other property of the pieces.
The population falls to about 300 effective families by free depth 175 and
dies at depth 188 to 192, while the estimated width there is still about
10^35. Widths past that point are not measured. The remaining 60 levels are
argued to add at most about 10^-4 of the total (not measured); the sum to
free cell 175 is 10^40.453, so 99% of the estimate lies in the measured
part. The five-repetition interval cannot exclude a heavy-tailed subtree the
population never visits. The N = 1e5 and N = 1e6 estimates agree, larger N
giving a slightly lower value.
The row scan with five clues costs 2^134.4 nodes. The gap against the budgets of
2^78 and 2^61.5 nodes is 56 to 73 bits; the
series hub holds
those fixed numbers. This page contributes the left-hand side: the cost
of the plain method is a measured quantity, not a model output, and it is
huge. A constant-factor speedup cannot close 56 bits. Where the cost sits is
taken up in frame and corners,
and what one known extra tile saves in
the worth of a known tile.
For the expected number of solutions see
solution counting. Record
boards are on records.
- No tree was enumerated. Every figure is an estimate, with exact checks only
on small boards and on the official frame count.
- The one-clue and no-clue rows are N = 1e5 only, and the null boards used two
repetitions at N = 1e5 rather than N = 1e6; there is no centre-clue null.
- Only the row scan from row 15 is measured here. The second experiment
measured 18 other static fill orders on the same pieces: none is shown to
beat it (15 are shown not to, 3 are undecided because the estimator's
population dies early).
- Only the size of the exhaustive tree is priced. Stochastic record hunting,
where more throughput means more attempts, is a separate question (see
open problems and dead ends).
just experiments real-puzzle-profile build
just experiments real-puzzle-profile m2 # about 4 minutes
just experiments real-puzzle-profile paint # painted boards
python3 -I research/experiments/real-puzzle-profile/scripts/analyze.py
Estimates are deterministic given the seed and binary. RESULTS.md in the
experiment folder maps each number to its raw file.