1# Space filling and the tile library23Design notes for phase 2. Two ideas that belong together: the daily board is4a packing of square tiles of mixed size, and tiles come from a long-lived5library that is generated locally and only stored and indexed in the cloud.67## 1. Pitch space89Tiles overlap by one cell, so a tile of side n occupies a square of side10s = n-1 in "pitch space". With n in 6..16, s is in 5..15. In pitch space11tiles are ordinary non-overlapping squares, seams are the shared borders,12and the board of side G in cells is a square of side G-1 in pitch space13(999 for G = 1000). Everything below is stated in pitch space.1415Useful arithmetic:1617- n is even, so pitch sides are odd: {5, 7, 9, 11, 13, 15}. Every odd18 length >= 5 and every even length >= 10 is a sum of those (6 and 8 are19 not, and neither is anything under 5). So a strip splits exactly into20 allowed sub-bands unless its size is 1..4, 6 or 8, which is the whole21 list of remainders a packer has to steer around.22- A rectangle a x b can be cut into squares by the Euclidean algorithm23 (repeatedly take the largest square). Sizes shrink toward gcd(a, b); when24 a piece would fall under 5 it stops and that piece is a zone (below).25- Tiling an integer rectangle with squares of side >= 2 is always possible26 once both sides are >= 10 [1]. With the side floor raised to 5 and a cap27 of 15 there is no such theorem; we do not need one because zones absorb28 the remainder, but the amount of remainder is the quality metric of a29 packer.30- Deciding whether a given multiset of squares tiles a rectangle is31 NP-complete [2]; guillotine (recursive straight cut) packings are the32 tractable family and lose little for squares [3]. Everything proposed33 here is guillotine or grown, never a search for an exact tiling.3435## 2. Packers3637Four candidate ways to choose the squares. All are seeded; the seed is the38daily seed and the seed tile is drawn first so packers can favour it.3940**Bands (Mondrian).** Split the height into bands with heights drawn from415..15; fill each band left to right with squares of the band height; the42last partial column of a band (width r < h) is cut by Euclid into smaller43squares, remainders under 5 become zones. Simple, fast, zone area is44bounded by roughly (number of bands) x 4 x 15 cells. Looks like a grid with45uneven rows, which is honest but dull. Variant: sub-bands, where a band of46height 15 sometimes holds two rows of 7 and 8, or three of 5, which breaks47the row look.4849**Grown from the seed.** Place the seed tile, then repeatedly pick a free50spot on the boundary of the placed region and drop the largest square that51fits there (or a random size that fits, with a bias). This is the packing52version of frontier expansion, so the layout has the same shape as a run:53concentric, irregular, big tiles where there was room, small ones in the54notches. Leftover notches become zones. Needs a boundary data structure55(skyline or maximal free rectangles [4]); free-rectangle packers are56standard for this and well understood.5758**Big first, then fill.** Draw a few large squares (13..15) at seeded59positions on a coarse grid, then fill the gaps with a bands or Euclid pass.60This is the packer that serves the library best (section 4): a large tile61placed first has free edges, and the small tiles that fill around it only62need to match one edge each, which is the cheap lookup.6364**Substitution.** A fixed recursive rule (a 15-square splits into a 9, a656 and three 5s, say) applied to a coarse grid. Deterministic, elegant, no66zones at all if the rule closes, but the size distribution is fixed by the67rule and the layout is self-similar, which an agent can learn. Keep as a68knob, not the default.6970Recommendation: big-first-then-fill as the default because of the library,71with grown-from-seed as the alternative layout when we want the map to72read as the run's own shape. Bands is the fallback and the test fixture.7374## 3. What mixed sizes change in the engine and the site7576- The manifest lists tiles explicitly: `{id, x0, y0, n, hash}` plus zones77 `{id, cells}`. `(tx, ty)` and a global `n` go away; phase 1's grid is the78 special case where every tile has the same n and the list is regular.79- Owners of a cell come from the tile list (an interval tree or a per-cell80 owner index built once per manifest). Hues come from a greedy 7-colouring81 of the tile adjacency graph (tiles sharing any cell), not from82 `(tx + 3ty) mod 7`.83- Seams become seam segments. A 15-tile abutting three 5-tiles has one84 side split three ways. The generator's per-side `pins` become per-segment:85 every alternative solution of a tile must differ on some seam segment,86 and the CSP for global uniqueness runs over segments. The rules engine87 already treats windows as arbitrary rectangles, so nothing changes there.88- T-junctions replace corners. A cell where three or four tiles meet is89 never planted and never a seam clue, same rule as today's corners, and90 that is what keeps independent tiles independent during generation.91- Generation order is a DAG, not a raster: a tile depends on every earlier92 tile it shares a segment with. Wavefront parallelism becomes antichains93 of that DAG. With a library, generation order matters only when94 draining misses (section 4); stitching is a lookup, not a generation.95- Zones: filler. Cells fully given, never on the frontier, no reward, drawn96 in the panel grey with no hue. Playable zones with reduced rules are a97 later knob; keep the manifest shape able to carry a rule set per zone.98- Reward per tile is n^2 cells; the analyzer records reward per batch and99 mean n of solved tiles over time so the "small tiles open the board,100 large tiles pin more" tradeoff is measurable rather than argued.101102## 4. The tile library103104A tile is a fixed-shape record for a given n and will not change:105106```107n 6..16108solution n*n bits109givens n*n bits (mask over solution)110seam_mask which sides were seams when the givens were chosen (4 bits)111edges four edge ints: top, right, bottom, left (n bits each)112features m, blank ratio, bifurcations, used_unique, needs_unique,113 needs_bifurcation, pins (4 bits), flip cells, generator version114hash sha256 of (n, solution, givens, seam_mask)115```116117Symmetries multiply the library by 16 at no generation cost: the four118rotations, reflection, and the 0/1 complement all preserve balance, runs and119line uniqueness, and they carry givens, planted cells, m and the ladder120rating along unchanged (row or column shuffles do not survive the no-three121rule, so 16 is the whole group). Store one canonical orientation per tile122and index all 16 edge tuples (edges transform by bit reversal and123complement), so a lookup by edge hits any orientation and the stitcher124applies the transform on the way out.125126At n = 16 the payload is 64 bytes plus ~40 bytes of features. A million127tiles is about 100 MB. The record is content-addressed and never mutated;128a new generator version adds rows, it does not rewrite old ones.129130What the index has to answer (the stitcher's questions):1311321. Tiles of size n whose top edge equals E (one constrained side).1332. Tiles of size n whose top edge equals E and left edge equals F.1343. Tiles of size n, any edges, filtered by difficulty features (m, ladder135 bifurcations, blank ratio) and by seam mask.1364. Given a tile, its neighbours' constraints for the next placement.137138Questions 1 and 3 are exact-match and range filters over small ints: an139index on `(n, top)`, `(n, left)`, `(n, right)`, `(n, bottom)` and on140`(n, bifurcations, m)` answers them. Question 2 is where library size141matters. Balanced edge patterns per n:142143| n | C(n, n/2) | one-side lookups | two-side pairs |144|----|-----------|------------------|----------------|145| 6 | 20 | trivial | 400 |146| 8 | 70 | trivial | 4,900 |147| 10 | 252 | cheap | 63,504 |148| 12 | 924 | ~10k tiles | 853,776 |149| 14 | 3,432 | ~50k tiles | 11.8 million |150| 16 | 12,870 | ~200k tiles | 165 million |151152("one-side lookups" is the library size at which a random edge value has153several matches.) So: a library of tens of thousands of tiles per n makes154one-sided placement of any size reliable; two-sided placement is only155reliable for n <= 10. That is the constraint the packer honours by placing156large tiles with free edges first and small tiles into the gaps. Where a157two-sided or three-sided placement of a large tile is unavoidable, the158stitcher records a miss and falls back to a smaller size or a zone.159160Partial-edge constraints (a big tile matching a concatenation of small161neighbours' edges) are just exact-match on the assembled edge int, so they162need no special index; they are the expensive case only because the163matching probability is low, which is the same table above.164165Misses are the DP part. Every miss is a row `(n, constrained sides and166their values, packing id)` in a misses table; the local generator drains it167by generating tiles that satisfy those exact edges (that is what the168seam-prefilled completion in `gen` already does), pushes them, and the169next stitch hits. "Failed to fit" entries are misses that the generator170also could not satisfy (no completion exists for those edges); they are171kept so the stitcher stops asking. The library therefore grows toward what172packings actually need, and refreshing it is running the generator against173the misses table, never a rebuild.174175## 5. Where it lives176177Nothing computes in the cloud. Generation, stitching, and the daily's178referee all run locally (or wherever the referee runs); the cloud holds the179library so it outlives any one machine and any collaborator can pull it.180The design question is only format and ease of access.181182**Format: one SQLite file.** A tile row is ~120 bytes (record + features +183edge ints); 1 GB is about 8 million tiles, several times what the edge184table says we need even at n = 16. SQLite gives the indexes (four edge185columns, difficulty features), the misses table, and an atomic file to copy186around. Schema in short:187188```189tiles(hash PRIMARY KEY, n, version, seam_mask, top, right, bottom, left,190 m, blank, bifurcations, used_unique, needs_unique, needs_bifurcation,191 pins, solution BLOB, givens BLOB, flip BLOB, created)192 INDEX (n, top), (n, right), (n, bottom), (n, left), (n, bifurcations, m)193misses(n, side_mask, top, right, bottom, left, packing, first_seen, nofit)194manifests(day, seed_commit, json)195```196197Rows are append-only and content-addressed; a generator version change adds198rows with a new `version`, and old rows stay valid because the game199representation for a given n does not change.200201**Access: R2 holds the file, optionally D1 mirrors the index.** The simplest202that works: the library is an object in R2 (no egress cost, range reads203supported [5]). A local job pulls the file, stitches, appends misses and any204newly generated tiles, and pushes it back; a small version stamp avoids two205writers clobbering each other, and since all writes are appends a conflict206is a merge of rows, not a rewrite. If the referee ever needs single-tile207lookups without holding the file, D1 is the same SQLite as a hosted208database with an HTTP API and a 10 GB ceiling [6]; loading the file into D1209is a one-off import, not a second source of truth. Workers, KV, and210Containers are not needed for this.211212Daily flow: pull library, draw the packing from the day's seed, resolve it213against the local file, record misses, run the generator on the misses,214emit the manifest (tile list with hashes, zones, seed commit), append it,215push. The referee reads tiles by hash from the same file. Anyone with the216manifest and the file rebuilds the board, which is the phase-3217verifiability story unchanged.218219## Open questions220221- Size distribution per day: uniform over 6..16, or weighted toward 12..16222 with small tiles only as fillers? The reward curve will look very223 different; start with big-first so large tiles dominate area.224- Zones: how much area is acceptable (target under 3%), and should a zone225 be allowed to be cut by seams of neighbouring tiles (it must, for the226 neighbours' rules to hold inside their windows; zone cells inside a tile227 window are simply given).228- Whether `m` should vary with n (2 for 6..8, 3 for 10..14, 4 for 16) so229 small tiles are not trivially pinned by a single seam.230- Seam clues in a packing: a large tile fully surrounded by small ones has231 many short seam segments; the "fewest seam clues to hold m" rule works232 per segment, but the count may be higher than in a grid. Measure.233234## Sources2352361. Tiling of rectangles with squares via Diophantine approximation,237 https://arxiv.org/pdf/2201.115452382. Minimum tiling of a rectangle by squares,239 https://www.researchgate.net/publication/322233241_Minimum_tiling_of_a_rectangle_by_squares2403. On Guillotine Separability of Squares and Rectangles,241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.472424. Jukka Jylanki, A thousand ways to pack the bin (maximal rectangles,243 skyline), the standard reference for free-rectangle packers.2445. R2 pricing, https://developers.cloudflare.com/r2/pricing2456. D1 limits, https://developers.cloudflare.com/d1/platform/limits