Space filling and the tile library

Design notes for phase 2. Two ideas that belong together: the daily board is a packing of square tiles of mixed size, and tiles come from a long-lived library that is generated locally and only stored and indexed in the cloud.

1. Pitch space

Tiles overlap by one cell, so a tile of side n occupies a square of side s = n-1 in "pitch space". With n in 6..16, s is in 5..15. In pitch space tiles are ordinary non-overlapping squares, seams are the shared borders, and the board of side G in cells is a square of side G-1 in pitch space (999 for G = 1000). Everything below is stated in pitch space.

Useful arithmetic:

• n is even, so pitch sides are odd: {5, 7, 9, 11, 13, 15}. Every odd length >= 5 and every even length >= 10 is a sum of those (6 and 8 are not, and neither is anything under 5). So a strip splits exactly into allowed sub-bands unless its size is 1..4, 6 or 8, which is the whole list of remainders a packer has to steer around.
• A rectangle a x b can be cut into squares by the Euclidean algorithm (repeatedly take the largest square). Sizes shrink toward gcd(a, b); when a piece would fall under 5 it stops and that piece is a zone (below).
• Tiling an integer rectangle with squares of side >= 2 is always possible once both sides are >= 10 [1]. With the side floor raised to 5 and a cap of 15 there is no such theorem; we do not need one because zones absorb the remainder, but the amount of remainder is the quality metric of a packer.
• Deciding whether a given multiset of squares tiles a rectangle is NP-complete [2]; guillotine (recursive straight cut) packings are the tractable family and lose little for squares [3]. Everything proposed here is guillotine or grown, never a search for an exact tiling.

2. Packers

Four candidate ways to choose the squares. All are seeded; the seed is the daily seed and the seed tile is drawn first so packers can favour it.

Bands (Mondrian). Split the height into bands with heights drawn from 5..15; fill each band left to right with squares of the band height; the last partial column of a band (width r < h) is cut by Euclid into smaller squares, remainders under 5 become zones. Simple, fast, zone area is bounded by roughly (number of bands) x 4 x 15 cells. Looks like a grid with uneven rows, which is honest but dull. Variant: sub-bands, where a band of height 15 sometimes holds two rows of 7 and 8, or three of 5, which breaks the row look.

Grown from the seed. Place the seed tile, then repeatedly pick a free spot on the boundary of the placed region and drop the largest square that fits there (or a random size that fits, with a bias). This is the packing version of frontier expansion, so the layout has the same shape as a run: concentric, irregular, big tiles where there was room, small ones in the notches. Leftover notches become zones. Needs a boundary data structure (skyline or maximal free rectangles [4]); free-rectangle packers are standard for this and well understood.

Big first, then fill. Draw a few large squares (13..15) at seeded positions on a coarse grid, then fill the gaps with a bands or Euclid pass. This is the packer that serves the library best (section 4): a large tile placed first has free edges, and the small tiles that fill around it only need to match one edge each, which is the cheap lookup.

Substitution. A fixed recursive rule (a 15-square splits into a 9, a 6 and three 5s, say) applied to a coarse grid. Deterministic, elegant, no zones at all if the rule closes, but the size distribution is fixed by the rule and the layout is self-similar, which an agent can learn. Keep as a knob, not the default.

Recommendation: big-first-then-fill as the default because of the library, with grown-from-seed as the alternative layout when we want the map to read as the run's own shape. Bands is the fallback and the test fixture.

3. What mixed sizes change in the engine and the site

• The manifest lists tiles explicitly: {id, x0, y0, n, hash} plus zones {id, cells}. (tx, ty) and a global n go away; phase 1's grid is the special case where every tile has the same n and the list is regular.
• Owners of a cell come from the tile list (an interval tree or a per-cell owner index built once per manifest). Hues come from a greedy 7-colouring of the tile adjacency graph (tiles sharing any cell), not from (tx + 3ty) mod 7.
• Seams become seam segments. A 15-tile abutting three 5-tiles has one side split three ways. The generator's per-side pins become per-segment: every alternative solution of a tile must differ on some seam segment, and the CSP for global uniqueness runs over segments. The rules engine already treats windows as arbitrary rectangles, so nothing changes there.
• T-junctions replace corners. A cell where three or four tiles meet is never planted and never a seam clue, same rule as today's corners, and that is what keeps independent tiles independent during generation.
• Generation order is a DAG, not a raster: a tile depends on every earlier tile it shares a segment with. Wavefront parallelism becomes antichains of that DAG. With a library, generation order matters only when draining misses (section 4); stitching is a lookup, not a generation.
• Zones: filler. Cells fully given, never on the frontier, no reward, drawn in the panel grey with no hue. Playable zones with reduced rules are a later knob; keep the manifest shape able to carry a rule set per zone.
• Reward per tile is n^2 cells; the analyzer records reward per batch and mean n of solved tiles over time so the "small tiles open the board, large tiles pin more" tradeoff is measurable rather than argued.

4. The tile library

A tile is a fixed-shape record for a given n and will not change:

n            6..16
solution     n*n bits
givens       n*n bits (mask over solution)
seam_mask    which sides were seams when the givens were chosen (4 bits)
edges        four edge ints: top, right, bottom, left (n bits each)
features     m, blank ratio, bifurcations, used_unique, needs_unique,
             needs_bifurcation, pins (4 bits), flip cells, generator version
hash         sha256 of (n, solution, givens, seam_mask)

Symmetries multiply the library by 16 at no generation cost: the four rotations, reflection, and the 0/1 complement all preserve balance, runs and line uniqueness, and they carry givens, planted cells, m and the ladder rating along unchanged (row or column shuffles do not survive the no-three rule, so 16 is the whole group). Store one canonical orientation per tile and index all 16 edge tuples (edges transform by bit reversal and complement), so a lookup by edge hits any orientation and the stitcher applies the transform on the way out.

At n = 16 the payload is 64 bytes plus ~40 bytes of features. A million tiles is about 100 MB. The record is content-addressed and never mutated; a new generator version adds rows, it does not rewrite old ones.

What the index has to answer (the stitcher's questions):

1. Tiles of size n whose top edge equals E (one constrained side).
2. Tiles of size n whose top edge equals E and left edge equals F.
3. Tiles of size n, any edges, filtered by difficulty features (m, ladder bifurcations, blank ratio) and by seam mask.
4. Given a tile, its neighbours' constraints for the next placement.

Questions 1 and 3 are exact-match and range filters over small ints: an index on (n, top), (n, left), (n, right), (n, bottom) and on (n, bifurcations, m) answers them. Question 2 is where library size matters. Balanced edge patterns per n:

n	C(n, n/2)	one-side lookups	two-side pairs
6	20	trivial	400
8	70	trivial	4,900
10	252	cheap	63,504
12	924	~10k tiles	853,776
14	3,432	~50k tiles	11.8 million
16	12,870	~200k tiles	165 million

("one-side lookups" is the library size at which a random edge value has several matches.) So: a library of tens of thousands of tiles per n makes one-sided placement of any size reliable; two-sided placement is only reliable for n <= 10. That is the constraint the packer honours by placing large tiles with free edges first and small tiles into the gaps. Where a two-sided or three-sided placement of a large tile is unavoidable, the stitcher records a miss and falls back to a smaller size or a zone.

Partial-edge constraints (a big tile matching a concatenation of small neighbours' edges) are just exact-match on the assembled edge int, so they need no special index; they are the expensive case only because the matching probability is low, which is the same table above.

Misses are the DP part. Every miss is a row (n, constrained sides and their values, packing id) in a misses table; the local generator drains it by generating tiles that satisfy those exact edges (that is what the seam-prefilled completion in gen already does), pushes them, and the next stitch hits. "Failed to fit" entries are misses that the generator also could not satisfy (no completion exists for those edges); they are kept so the stitcher stops asking. The library therefore grows toward what packings actually need, and refreshing it is running the generator against the misses table, never a rebuild.

5. Where it lives

Nothing computes in the cloud. Generation, stitching, and the daily's referee all run locally (or wherever the referee runs); the cloud holds the library so it outlives any one machine and any collaborator can pull it. The design question is only format and ease of access.

Format: one SQLite file. A tile row is ~120 bytes (record + features + edge ints); 1 GB is about 8 million tiles, several times what the edge table says we need even at n = 16. SQLite gives the indexes (four edge columns, difficulty features), the misses table, and an atomic file to copy around. Schema in short:

tiles(hash PRIMARY KEY, n, version, seam_mask, top, right, bottom, left,
      m, blank, bifurcations, used_unique, needs_unique, needs_bifurcation,
      pins, solution BLOB, givens BLOB, flip BLOB, created)
  INDEX (n, top), (n, right), (n, bottom), (n, left), (n, bifurcations, m)
misses(n, side_mask, top, right, bottom, left, packing, first_seen, nofit)
manifests(day, seed_commit, json)

Rows are append-only and content-addressed; a generator version change adds rows with a new version, and old rows stay valid because the game representation for a given n does not change.

Access: R2 holds the file, optionally D1 mirrors the index. The simplest that works: the library is an object in R2 (no egress cost, range reads supported [5]). A local job pulls the file, stitches, appends misses and any newly generated tiles, and pushes it back; a small version stamp avoids two writers clobbering each other, and since all writes are appends a conflict is a merge of rows, not a rewrite. If the referee ever needs single-tile lookups without holding the file, D1 is the same SQLite as a hosted database with an HTTP API and a 10 GB ceiling [6]; loading the file into D1 is a one-off import, not a second source of truth. Workers, KV, and Containers are not needed for this.

Daily flow: pull library, draw the packing from the day's seed, resolve it against the local file, record misses, run the generator on the misses, emit the manifest (tile list with hashes, zones, seed commit), append it, push. The referee reads tiles by hash from the same file. Anyone with the manifest and the file rebuilds the board, which is the phase-3 verifiability story unchanged.

Open questions

• Size distribution per day: uniform over 6..16, or weighted toward 12..16 with small tiles only as fillers? The reward curve will look very different; start with big-first so large tiles dominate area.
• Zones: how much area is acceptable (target under 3%), and should a zone be allowed to be cut by seams of neighbouring tiles (it must, for the neighbours' rules to hold inside their windows; zone cells inside a tile window are simply given).
• Whether m should vary with n (2 for 6..8, 3 for 10..14, 4 for 16) so small tiles are not trivially pinned by a single seam.
• Seam clues in a packing: a large tile fully surrounded by small ones has many short seam segments; the "fewest seam clues to hold m" rule works per segment, but the count may be higher than in a grid. Measure.

Sources

1. Tiling of rectangles with squares via Diophantine approximation, https://arxiv.org/pdf/2201.11545
2. Minimum tiling of a rectangle by squares, https://www.researchgate.net/publication/322233241_Minimum_tiling_of_a_rectangle_by_squares
3. On Guillotine Separability of Squares and Rectangles, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.47
4. Jukka Jylanki, A thousand ways to pack the bin (maximal rectangles, skyline), the standard reference for free-rectangle packers.
5. R2 pricing, https://developers.cloudflare.com/r2/pricing
6. D1 limits, https://developers.cloudflare.com/d1/platform/limits