1// Package gen builds a mosaic over a layout: Takuzu tiles of any valid2// shape (unions of rectangles whose lines are even and at least 4 long)3// scattered on a field, overlapping by arbitrary regions. Every tile alone4// has 2..m solutions and every alternative differs from the truth inside5// some overlap region; the mosaic as a whole has exactly one solution.6// Deterministic per seed. The phase-1 X-by-X grid is the packer kind7// "grid".8package gen910import (11 "bytes"12 "context"13 "crypto/hmac"14 "crypto/sha256"15 "encoding/binary"16 "encoding/hex"17 "errors"18 "fmt"19 "math/rand/v2"20 "os"21 "runtime"22 "sort"23 "strings"24 "sync"25 "time"2627 "mosaic-engine/pack"28 "mosaic-engine/rules"29 "mosaic-engine/sat"30)3132// Policy is what the generator asserts for a tile of a given cell count.33// Small tiles are fillers around the hard ones: they still have 2..m34// solutions that differ inside an overlap, but the technique checks and35// the blank floor scale up with size, and only tiles of 144 cells and36// more (a 12x12) are held to the canonical hard standard.37type Policy struct {38 M int39 BlankMin float6440 BlankMax float6441 NeedsUnique bool42 NeedsBifurcation bool43}4445func PolicyFor(cells int) Policy {46 switch {47 case cells <= 64:48 return Policy{M: pack.MFor(cells), BlankMin: 0.55, BlankMax: 0.70}49 case cells <= 100:50 return Policy{M: pack.MFor(cells), BlankMin: 0.65, BlankMax: 0.75}51 case cells < 144:52 return Policy{M: pack.MFor(cells), BlankMin: 0.70, BlankMax: 0.75}53 case cells <= 196:54 return Policy{M: pack.MFor(cells), BlankMin: 0.70, BlankMax: 0.75, NeedsUnique: true, NeedsBifurcation: true}55 default:56 // counting past ~73% blank at 256 cells is where single counts take seconds57 return Policy{M: pack.MFor(cells), BlankMin: 0.70, BlankMax: 0.73, NeedsUnique: true, NeedsBifurcation: true}58 }59}6061// Verbose logs failed attempts to stderr.62var Verbose = os.Getenv("MOSAIC_DEBUG") != ""6364// Version changes whenever the generator's output for a seed could change.65const Version = "gen-v7" // v7: tile hashes are HMAC commitments (v6: chunks filled by one joint SAT completion)6667type Params struct {68 Seed string `json:"seed"`69 Nonce string `json:"nonce,omitempty"`70 G int `json:"G"`71 Kind string `json:"kind"` // scatter | grid72 N int `json:"n,omitempty"`73 // legacy grid shorthand: X tiles per side of size N74 X int `json:"X,omitempty"`75 Coverage float64 `json:"coverage,omitempty"`76 Compound float64 `json:"compound,omitempty"`77 BandUnique bool `json:"band_unique"`78 MaxAttempts int `json:"max_attempts,omitempty"`79 // chunk mode (scatter): place tiles inside Region against Fixed context80 // tiles from neighbouring chunks, whose cells are prefilled and never81 // changed; emitted tile ids start at IDBase; Chunk is the chunk's index82 // in its field (informational; the orchestrator sets Nonce per chunk).83 Region [4]int `json:"region,omitempty"`84 Fixed []FixedTile `json:"fixed,omitempty"`85 IDBase int `json:"id_base,omitempty"`86 Chunk int `json:"chunk,omitempty"`87}8889// FixedTile is a context tile from another chunk: its shape (field90// coordinates, real id) and its solution as local W*H cells (Empty outside91// the shape).92type FixedTile struct {93 Tile pack.Tile `json:"tile"`94 Cells []rules.Cell `json:"cells"`95}9697// FieldPublic describes a field assembled from chunks (manifest.field).98type FieldPublic struct {99 Chunks int `json:"chunks"` // chunks per side of the initial grid100 ChunkG int `json:"chunk_g"` // cells per side of a chunk region101 Band int `json:"band"` // overlap band between neighbouring regions102 Origin [2]int `json:"origin"` // cells: lattice chunk (0,0) starts here; chunk (cx,cy) at origin + (cx,cy)*(chunk_g-band)103 Occupied [][2]int `json:"occupied"` // lattice chunks generated so far104 Grown int `json:"grown"` // rings added by GrowField105 SeedTiles []int `json:"seed_tiles"`106}107108type Rules struct {109 Overlaps bool `json:"overlaps"`110 CrossTile bool `json:"cross_tile"`111 SeamClues bool `json:"seam_clues"`112 BandUnique bool `json:"band_unique"`113}114115type PackerInfo struct {116 Kind string `json:"kind"`117 Params map[string]any `json:"params"`118}119120// OverlapPublic is what the manifest says about a shared region: the121// partner and how many cells; the cell set is the intersection of the two122// shapes.123type OverlapPublic struct {124 With int `json:"with"`125 Cells int `json:"cells"`126}127128// TilePublic is what the manifest carries about a tile.129type TilePublic struct {130 ID int `json:"id"`131 X0 int `json:"x0"`132 Y0 int `json:"y0"`133 W int `json:"w"`134 H int `json:"h"`135 Rects [][4]int `json:"rects"`136 Cells int `json:"cells"`137 Hash string `json:"hash"`138 M int `json:"m"`139 Overlaps []OverlapPublic `json:"overlaps"`140 Pins []int `json:"pins"` // indexes into Overlaps some alternative differs on141}142143type Manifest struct {144 Version int `json:"version"`145 ID string `json:"id"`146 SeedCommit string `json:"seed_commit"`147 G int `json:"G"`148 Packer PackerInfo `json:"packer"`149 MByN map[string]int `json:"m_by_n"`150 Rules Rules `json:"rules"`151 SeedTile int `json:"seed_tile"`152 Tiles []TilePublic `json:"tiles"`153 K string `json:"k"`154 Generator string `json:"generator"`155 Library *string `json:"library"`156 Field *FieldPublic `json:"field,omitempty"`157 HashScheme string `json:"hash_scheme"` // "mosaic-tile-v1"158 HashKeyCommit string `json:"hash_key_commit"` // sha256 of the day key, released at archive159}160161// TilePrivate is the generator's per-tile record: never in the public log.162type TilePrivate struct {163 ID int `json:"id"`164 Givens [][2]int `json:"givens"` // [global cell id, value]165 Blank float64 `json:"blank"`166 NeedsUnique bool `json:"needs_unique"`167 NeedsBifurcation bool `json:"needs_bifurcation"`168 Flip []int `json:"flip"` // global ids of the planted ambiguity169 Ladder Ladder `json:"ladder"`170}171172// Ladder is what the technique-ladder solver used on the pinned tile173// (analyzer data; not asserted).174type Ladder struct {175 UsedUnique bool `json:"used_unique"`176 UsedBifurcation bool `json:"used_bifurcation"`177 Bifurcations int `json:"bifurcations"`178 Complete bool `json:"complete"`179}180181// errBackjumps: the fill phase thrashed; the attempt redraws it with a new182// salt (maxFillRetries times) before giving up.183var errBackjumps = errors.New("too many backjumps")184185const maxFillRetries = 4186187// jointFillMax: boards with at most this many new tiles are filled by one188// joint SAT completion (fillSolution); larger ones tile by tile.189const jointFillMax = 48190191// errLayout: the failure is a property of the layout; Generate re-packs192// with a new salt instead of attempting the same layout again.193var errLayout = errors.New("layout")194195func isLayoutClass(err error) bool {196 msg := err.Error()197 return strings.Contains(msg, "differs inside no overlap region") ||198 strings.Contains(msg, "falls to propagation alone") ||199 strings.Contains(msg, "shared cells stay ambiguous")200}201202const maxPackSalts = 3203204// maxLayoutSalts bounds the re-draws of a chunk layout that admits no joint205// completion against its context (a SAT verdict each, milliseconds).206const maxLayoutSalts = 12207208// maxRepairRounds bounds the coupled-uniqueness repair loop; each round209// costs a makeGivens, so 3*tiles at G=200 was effectively unbounded.210const maxRepairRounds = 60211212type Stats struct {213 Ms int64 `json:"ms"`214 Attempts int `json:"attempts"`215 Refills int `json:"refills"`216 Backjumps int `json:"backjumps"`217 Regivens int `json:"regivens"`218 Releases int `json:"releases"` // repairs that took back neighbours' seam clues219 Waves int `json:"waves"`220 WaveRetries int `json:"wave_retries"` // tiles whose givens needed a fresh draw within the attempt221 Redraws int `json:"redraws"` // stuck tiles whose interior solution was redrawn in repair222 FillRetries int `json:"fill_retries"` // fill phases redrawn after thrashing on backjumps223 Exhausted bool `json:"exhausted,omitempty"` // GrowField: no chunk of the ring fits on the field224 // phase timings of the successful attempt (wall clock) and of the225 // attempts wasted before it226 FillMs int64 `json:"fill_ms"`227 GivensMs int64 `json:"givens_ms"`228 SettleMs int64 `json:"settle_ms"`229 WastedMs int64 `json:"wasted_ms"`230 Wasted int `json:"wasted"` // attempts that failed231 SatCalls int64 `json:"sat_calls"`232 SatMs int64 `json:"sat_ms"` // time inside the SAT solver (serialised)233 LadderMs int64 `json:"ladder_ms"`234 RemoveMs int64 `json:"remove_ms"` // clue removal loops, summed over tiles (parallel)235 TileTimers []TileTimer `json:"tile_timers,omitempty"`236}237238// TileTimer is what one tile cost in the successful attempt.239type TileTimer struct {240 ID int `json:"id"`241 Cells int `json:"cells"`242 FillMs int64 `json:"fill_ms"`243 GivensMs int64 `json:"givens_ms"` // buildGivens wall, all rounds and refills244 Rounds int `json:"rounds"` // makeGivens rounds245 Trials int `json:"trials"` // removeClues candidates tried246 SatCalls int `json:"sat_calls"` // counts by this tile's removal loops247 LadderMs int64 `json:"ladder_ms"`248 RemoveMs int64 `json:"remove_ms"`249}250251type Output struct {252 Manifest Manifest `json:"manifest"`253 Solution []string `json:"solution"` // G rows; '.' where no emitted tile covers the cell254 Tiles []TilePrivate `json:"tiles"`255 Stats Stats `json:"stats"`256 Layout pack.Report `json:"layout"`257 ChunkStats []Stats `json:"chunk_stats,omitempty"` // fields: per chunk, in chunk order258 DaySeed string `json:"day_seed,omitempty"` // private until the day is archived; seed_commit = sha256("mosaic-day-seed-v1|" + day_seed)259 HashKey string `json:"hash_key,omitempty"` // hex day key; private until the day is archived260}261262func defaults(p Params) (Params, error) {263 if p.X > 0 {264 if p.N == 0 {265 p.N = 14266 }267 p.Kind = "grid"268 p.G = p.X*(p.N-1) + 1269 }270 if p.Kind == "" {271 p.Kind = "scatter"272 }273 if p.G < pack.MinLine {274 return p, fmt.Errorf("G must be at least %d", pack.MinLine)275 }276 if p.MaxAttempts == 0 {277 p.MaxAttempts = 20278 }279 if p.Nonce == "" {280 h := sha256.Sum256([]byte("mosaic-nonce|" + p.Seed))281 p.Nonce = hex.EncodeToString(h[:8])282 }283 return p, nil284}285286func rngFor(parts ...string) *rand.Rand {287 h := sha256.New()288 for _, s := range parts {289 h.Write([]byte(s))290 h.Write([]byte{0})291 }292 sum := h.Sum(nil)293 return rand.New(rand.NewPCG(binary.LittleEndian.Uint64(sum[:8]), binary.LittleEndian.Uint64(sum[8:16])))294}295296// Generate runs the full pipeline. The layout is drawn once from the seed;297// attempts redraw the tile contents with a derived rng when an attempt298// cannot satisfy every assertion.299// Generate runs the full pipeline. A chunk (Params.Region set) is300// generated on a local board that covers just its region and the context301// tiles around it, then translated back to field coordinates: the302// per-cell structures (owners, rules geometry, boards cloned by303// propagation) are region-sized instead of G x G, which at G=1000 was304// hundreds of megabytes per chunk process for a 60x60 region.305func Generate(ctx context.Context, p Params) (*Output, error) {306 if p.Region == [4]int{} || p.G == 0 {307 return generate(ctx, p)308 }309 x0, y0 := p.Region[0], p.Region[1]310 x1, y1 := p.Region[0]+p.Region[2], p.Region[1]+p.Region[3]311 for _, f := range p.Fixed {312 x0, y0 = min(x0, f.Tile.X0), min(y0, f.Tile.Y0)313 x1, y1 = max(x1, f.Tile.X0+f.Tile.W), max(y1, f.Tile.Y0+f.Tile.H)314 }315 S := max(x1-x0, y1-y0)316 lp := p317 lp.G = S318 lp.Region = [4]int{p.Region[0] - x0, p.Region[1] - y0, p.Region[2], p.Region[3]}319 lp.Fixed = make([]FixedTile, len(p.Fixed))320 for i, f := range p.Fixed {321 t := f.Tile322 t.X0, t.Y0 = t.X0-x0, t.Y0-y0323 lp.Fixed[i] = FixedTile{Tile: t, Cells: f.Cells}324 }325 out, err := generate(ctx, lp)326 if err != nil {327 return nil, err328 }329 G := p.G330 toGlobal := func(id int) int { return (id/S+y0)*G + id%S + x0 }331 out.Manifest.G = G332 for i := range out.Manifest.Tiles {333 out.Manifest.Tiles[i].X0 += x0334 out.Manifest.Tiles[i].Y0 += y0335 }336 for i := range out.Tiles {337 for k := range out.Tiles[i].Givens {338 out.Tiles[i].Givens[k][0] = toGlobal(out.Tiles[i].Givens[k][0])339 }340 for k := range out.Tiles[i].Flip {341 out.Tiles[i].Flip[k] = toGlobal(out.Tiles[i].Flip[k])342 }343 }344 sol := make([][]byte, G)345 for y := range sol {346 sol[y] = bytes.Repeat([]byte{'.'}, G)347 }348 for ly, row := range out.Solution {349 gy := ly + y0350 if gy < 0 || gy >= G {351 continue352 }353 for lx := 0; lx < len(row); lx++ {354 gx := lx + x0355 if row[lx] != '.' && gx >= 0 && gx < G {356 sol[gy][gx] = row[lx]357 }358 }359 }360 out.Solution = out.Solution[:0]361 for y := range sol {362 out.Solution = append(out.Solution, string(sol[y]))363 }364 return out, nil365}366367func generate(ctx context.Context, p Params) (*Output, error) {368 p, err := defaults(p)369 if err != nil {370 return nil, err371 }372 var fixed []pack.Tile373 for _, f := range p.Fixed {374 if len(f.Cells) != f.Tile.W*f.Tile.H {375 return nil, fmt.Errorf("fixed tile %d: %d cells for a %dx%d box", f.Tile.ID, len(f.Cells), f.Tile.W, f.Tile.H)376 }377 fixed = append(fixed, f.Tile)378 }379 pp := pack.Params{Seed: p.Seed + "|" + p.Nonce, G: p.G, Kind: p.Kind, N: p.N, Coverage: p.Coverage, Compound: p.Compound,380 Region: p.Region, Fixed: fixed, IDBase: p.IDBase}381 var ctxBoard []rules.Cell382 if len(fixed) > 0 {383 // a candidate touching the context must be completable over the384 // context's cells (a whole line of it can lie inside a fixed tile,385 // where nothing made that segment balanced); the packer asks386 ctxBoard = make([]rules.Cell, p.G*p.G)387 for i := range ctxBoard {388 ctxBoard[i] = rules.Empty389 }390 for _, f := range p.Fixed {391 sh := rules.Shape{X0: f.Tile.X0, Y0: f.Tile.Y0, W: f.Tile.W, H: f.Tile.H, Rects: f.Tile.Rects}392 for li, ok := range sh.Mask() {393 if ok {394 ctxBoard[(sh.Y0+li/sh.W)*p.G+sh.X0+li%sh.W] = f.Cells[li]395 }396 }397 }398 // a candidate must be completable together with the placed new399 // tiles it touches over the fixed context: feasibility against the400 // context alone let through tiles that no completion of their new401 // neighbours could accommodate, and the fill then thrashed on them402 pp.Accept = func(t pack.Tile, touched []pack.Tile) bool {403 sh := rules.Shape{X0: t.X0, Y0: t.Y0, W: t.W, H: t.H, Rects: t.Rects}404 if sh.Valid() != nil {405 return false406 }407 others := make([]rules.Shape, 0, len(touched))408 for _, o := range touched {409 others = append(others, rules.Shape{X0: o.X0, Y0: o.Y0, W: o.W, H: o.H, Rects: o.Rects})410 }411 _, ok := sat.CompleteRegion(ctxBoard, p.G, others, sh, rngFor("accept", fmt.Sprint(t.ID)))412 return ok413 }414 }415 packLayout := func(salt int) (*pack.Layout, error) {416 pp.Salt = ""417 if salt > 0 {418 pp.Salt = fmt.Sprint("gen-salt", salt)419 }420 L, err := pack.Pack(pp)421 if err != nil {422 return nil, err423 }424 // every tile must be able to carry the rules on its own before any425 // search starts (an infeasible shape costs SAT seconds to refute)426 for _, t := range L.All() {427 sh := rules.Shape{X0: t.X0, Y0: t.Y0, W: t.W, H: t.H, Rects: t.Rects}428 if err := sh.Valid(); err != nil {429 return nil, fmt.Errorf("layout tile %d (%dx%d at %d,%d): %w", t.ID, t.W, t.H, t.X0, t.Y0, err)430 }431 }432 // and every new tile must have a neighbour able to pin it: an433 // overlap of at least MinLine cells. Without one, "an alternative434 // differs inside an overlap region" is unsatisfiable and every435 // attempt would fail; better to refuse the layout now436 for i, t := range L.Tiles {437 pinnable := false438 for _, o := range L.Overlaps[i] {439 if o.Cells >= pack.MinLine {440 pinnable = true441 break442 }443 }444 if !pinnable {445 return nil, fmt.Errorf("layout tile %d (%dx%d at %d,%d): no overlap of at least %d cells, no neighbour can pin it", t.ID, t.W, t.H, t.X0, t.Y0, pack.MinLine)446 }447 }448 return L, nil449 }450 packSalt := 0451 L, err := packLayout(packSalt)452 if err != nil {453 return nil, err454 }455 if len(p.Fixed) > 0 && len(L.Tiles) > 0 && len(L.Tiles) <= jointFillMax {456 // a chunk's layout must admit a joint completion against its457 // context; pairwise checks at drop time do not guarantee that, and458 // finding out in the fill costs a whole attempt. One SAT call per459 // salted re-draw, bounded.460 feasible := func(L *pack.Layout) bool {461 shapes := make([]rules.Shape, 0, len(L.Tiles))462 for _, t := range L.Tiles {463 shapes = append(shapes, rules.Shape{X0: t.X0, Y0: t.Y0, W: t.W, H: t.H, Rects: t.Rects})464 }465 _, ok := sat.CompleteAll(ctxBoard, p.G, shapes, rngFor(p.Seed, p.Nonce, "layout-check"))466 return ok467 }468 for !feasible(L) {469 if packSalt >= maxLayoutSalts {470 return nil, fmt.Errorf("no layout with a joint completion against the context after %d packings: %w", packSalt+1, errFixedNoFit)471 }472 packSalt++473 if Verbose {474 fmt.Fprintf(os.Stderr, "gen: layout admits no joint completion against the context; re-packing with salt %d\n", packSalt)475 }476 if L, err = packLayout(packSalt); err != nil {477 return nil, err478 }479 if len(L.Tiles) == 0 {480 break481 }482 }483 }484 if len(L.Tiles) == 0 {485 // a chunk region the context already covers: nothing to generate486 commit := DayCommit(p.Seed)487 out := &Output{Manifest: Manifest{Version: 3, ID: commit, SeedCommit: commit, G: p.G,488 Packer: PackerInfo{Kind: L.Kind, Params: map[string]any{}}, MByN: map[string]int{}, Rules: Rules{Overlaps: true}, SeedTile: -1, Tiles: []TilePublic{}, K: "unmeasured", Generator: generatorHash()},489 Tiles: []TilePrivate{}, Layout: L.Report}490 for y := 0; y < p.G; y++ {491 out.Solution = append(out.Solution, strings.Repeat(".", p.G))492 }493 return out, nil494 }495 start := time.Now()496 satCalls0, satNs0 := sat.Counters()497 var last error498 wasted := 0499 var wastedMs int64500 for attempt := 0; attempt < p.MaxAttempts; attempt++ {501 t0 := time.Now()502 out, err := generateAttempt(ctx, p, L, attempt)503 if err == nil {504 out.Stats.Attempts = attempt + 1505 out.Stats.Ms = time.Since(start).Milliseconds()506 out.Stats.Wasted, out.Stats.WastedMs = wasted, wastedMs507 c, d := sat.Counters()508 out.Stats.SatCalls, out.Stats.SatMs = c-satCalls0, (d - satNs0).Milliseconds()509 out.Layout = L.Report510 if Verbose {511 printTimers(out)512 }513 return out, nil514 }515 if ctx.Err() != nil {516 return nil, ctx.Err()517 }518 wasted++519 wastedMs += time.Since(t0).Milliseconds()520 last = err521 if Verbose {522 fmt.Fprintf(os.Stderr, "gen: attempt %d failed after %s: %v\n", attempt, time.Since(start).Round(time.Millisecond), err)523 }524 if errors.Is(err, errFixedNoFit) {525 // the layout, not the draw, is at fault: attempts cannot help526 return nil, fmt.Errorf("layout against the fixed context: %w", err)527 }528 if errors.Is(err, errLayout) {529 if packSalt >= maxPackSalts {530 return nil, fmt.Errorf("no layout after %d packings: %w", packSalt+1, err)531 }532 packSalt++533 if Verbose {534 fmt.Fprintf(os.Stderr, "gen: layout-class failure; re-packing with salt %d\n", packSalt)535 }536 if L, err = packLayout(packSalt); err != nil {537 return nil, err538 }539 }540 }541 return nil, fmt.Errorf("no mosaic after %d attempts: %w", p.MaxAttempts, last)542}543544// tileGeom is everything fixed about a tile before any content exists.545// Local indexes are ly*W+lx over the bounding box; cells outside the546// shape (mask false) are never read or written.547type tileGeom struct {548 id int549 sh rules.Shape550 W, H int551 cells int552 m int553 mask []bool554 overlaps []pack.Overlap555 shared []bool // local index -> owned by another tile too556 regsAt [][]int // local index -> indexes of pin-eligible overlaps (>= MinLine cells)557 junction []bool // local index -> shared cell that is not on any pin-eligible overlap, or has 3+ owners558 dist int // BFS distance to the seed tile over overlaps559 rank int // position in the fill order (see fillOrder)560 deps []int // tiles earlier in the fill order sharing any cell, by index561 fixed bool // context tile from another chunk: prefilled, never cleared, never given562 pubID int // the id the manifest uses (IDBase + index for emitted tiles)563}564565func (g *tileGeom) gid(m *mosaic, local int) int {566 return m.global.Idx(g.sh.X0+local%g.W, g.sh.Y0+local/g.W)567}568569type mosaic struct {570 hashKey []byte // keys the tiles' HMAC hashes571 gameID string // the day's seed commitment, bound into every tile hash572 p Params573 L *pack.Layout574 G int575 global *rules.Board576 geom []*tileGeom // emitted tiles first (index = position in L.Tiles), then fixed context tiles577 n int // number of emitted tiles578 order []int // fill order: position -> tile index; fixed tiles come first579 firstNew int // position in order of the first emitted tile580 owners [][]int // per cell, tile indexes owning it581 stats Stats582583 bandUniqueHeld bool584585 seamGivens map[int]rules.Cell // shared cells given to hold m; shared by all owners586 seamOwner map[int]int // which tile index added each seam given587 used map[int]bool // cells of planted rectangles: never givens588 mu sync.Mutex589 timers []TileTimer // per tile index590}591592func (m *mosaic) addTimer(i int, f func(t *TileTimer)) {593 m.mu.Lock()594 f(&m.timers[i])595 m.mu.Unlock()596}597598func newMosaic(p Params, L *pack.Layout) *mosaic {599 m := &mosaic{p: p, L: L, G: L.G, n: len(L.Tiles), bandUniqueHeld: p.BandUnique,600 seamGivens: map[int]rules.Cell{}, seamOwner: map[int]int{}, used: map[int]bool{}}601 m.hashKey = DayKey(p.Seed)602 m.gameID = DayCommit(p.Seed)603 m.global = rules.NewBoard(m.G, m.G)604 m.owners = L.Owners()605 all := L.All()606 for _, t := range all {607 m.global.Shapes = append(m.global.Shapes, rules.Shape{X0: t.X0, Y0: t.Y0, W: t.W, H: t.H, Rects: t.Rects})608 }609 // context tiles' cells are the truth from the neighbouring chunk610 for k, f := range p.Fixed {611 sh := m.global.Shapes[m.n+k]612 for li, ok := range sh.Mask() {613 if ok {614 m.global.Cells[m.global.Idx(sh.X0+li%sh.W, sh.Y0+li/sh.W)] = f.Cells[li]615 }616 }617 }618 // BFS distance from the seed tile over overlaps619 dist := make([]int, len(all))620 for i := range dist {621 dist[i] = -1622 }623 dist[L.SeedTile] = 0624 queue := []int{L.SeedTile}625 for len(queue) > 0 {626 t := queue[0]627 queue = queue[1:]628 for _, u := range L.Neighbours(t) {629 if dist[u] < 0 {630 dist[u] = dist[t] + 1631 queue = append(queue, u)632 }633 }634 }635 for i, t := range all {636 g := &tileGeom{id: i, sh: m.global.Shapes[i], W: t.W, H: t.H, cells: t.Cells, m: t.M, overlaps: L.Overlaps[i], dist: dist[i], fixed: i >= m.n, pubID: t.ID}637 g.mask = g.sh.Mask()638 g.shared = make([]bool, t.W*t.H)639 g.regsAt = make([][]int, t.W*t.H)640 g.junction = make([]bool, t.W*t.H)641 for oi, o := range g.overlaps {642 if o.Cells < pack.MinLine {643 continue644 }645 for _, id := range o.Ids {646 gx, gy := id%m.G, id/m.G647 li := (gy-t.Y0)*t.W + gx - t.X0648 g.regsAt[li] = append(g.regsAt[li], oi)649 }650 }651 for li, ok := range g.mask {652 if !ok {653 continue654 }655 own := m.owners[g.gid(m, li)]656 if len(own) >= 2 {657 g.shared[li] = true658 }659 // shared with three or more tiles, or shared only through660 // regions too small to pin: a junction, never planted, never661 // given662 if len(own) >= 3 || (len(own) >= 2 && len(g.regsAt[li]) == 0) {663 g.junction[li] = true664 }665 }666 m.geom = append(m.geom, g)667 }668 m.timers = make([]TileTimer, len(m.geom))669 for i, g := range m.geom {670 m.timers[i] = TileTimer{ID: g.pubID, Cells: g.cells}671 }672 m.order = m.fillOrder()673 for pos, id := range m.order {674 m.geom[id].rank = pos675 }676 for _, g := range m.geom {677 depSet := map[int]bool{}678 for li, ok := range g.mask {679 if !ok {680 continue681 }682 for _, o := range m.owners[g.gid(m, li)] {683 if m.geom[o].rank < g.rank {684 depSet[o] = true685 }686 }687 }688 for d := range depSet {689 g.deps = append(g.deps, d)690 }691 sort.Ints(g.deps)692 }693 return m694}695696// fillOrder decides the order tiles get their solution in: most constrained697// first. Starting from the seed tile, the next tile is always the unplaced698// one with the largest share of its cells already fixed by placed699// neighbours (ties: fewer cells, then lower id). A small tile is therefore700// filled as soon as one neighbour exists, while it still has few fixed701// cells and many completions, and its remaining cells become constraints702// on the large tiles around it, which have room to spare.703func (m *mosaic) fillOrder() []int {704 total := len(m.geom)705 placed := make([]bool, total)706 fixed := make([]int, total)707 order := make([]int, 0, total)708 place := func(id int) {709 placed[id] = true710 order = append(order, id)711 g := m.geom[id]712 for li, ok := range g.mask {713 if !ok {714 continue715 }716 for _, o := range m.owners[g.gid(m, li)] {717 if !placed[o] {718 fixed[o]++719 }720 }721 }722 }723 for _, g := range m.geom {724 if g.fixed {725 place(g.id)726 }727 }728 m.firstNew = len(order)729 place(m.L.SeedTile)730 for len(order) < total {731 best := -1732 var bestShare float64733 for _, g := range m.geom {734 if placed[g.id] {735 continue736 }737 share := float64(fixed[g.id]) / float64(g.cells)738 if best < 0 || share > bestShare ||739 (share == bestShare && (g.cells < m.geom[best].cells || (g.cells == m.geom[best].cells && g.id < best))) {740 best, bestShare = g.id, share741 }742 }743 place(best)744 }745 return order746}747748func generateAttempt(ctx context.Context, p Params, L *pack.Layout, attempt int) (*Output, error) {749 m := newMosaic(p, L)750 tag := fmt.Sprintf("%s|%s|%d", p.Seed, p.Nonce, attempt)751752 // Phase A: the solution, tile by tile in most-constrained-first order753 // (fillOrder) with backjumping (fillSolution).754 total := len(m.geom) // emitted tiles plus fixed context755 tFill := time.Now()756 // a fill that thrashes on backjumps is redrawn with a new salt inside757 // the attempt: the fill is seconds when it works, and nothing of the758 // attempt exists yet to lose759 fillRetries := 0760 for {761 err := m.fillSolution(ctx, tag)762 if err == nil {763 break764 }765 if !errors.Is(err, errBackjumps) || fillRetries >= maxFillRetries || ctx.Err() != nil {766 return nil, err767 }768 fillRetries++769 tag = fmt.Sprintf("%s|f%d", tag, fillRetries)770 if Verbose {771 fmt.Fprintf(os.Stderr, "gen: fill thrashed; redrawing with salt %d\n", fillRetries)772 }773 m = newMosaic(p, L)774 }775 m.stats.FillRetries = fillRetries776 m.stats.FillMs = time.Since(tFill).Milliseconds()777 tGivens := time.Now()778 // Phase B: givens, in waves over the fixed solution. A tile is ready when779 // every earlier tile (fill order) it shares a cell with is done (seam780 // givens flow from earlier tiles); tiles in one wave share no cell, so781 // they run in parallel and the output equals sequential fill order.782 tiles := make([]*tileWork, total)783 done := make([]bool, total)784 remaining := m.n785 for i := m.n; i < total; i++ {786 // a context tile has one solution: its cells787 g := m.geom[i]788 tiles[i] = &tileWork{id: i, sols: rules.TileSolutions{g.sh.Local(m.global.Cells, m.G)}}789 done[i] = true790 }791 for remaining > 0 {792 var idx []int793 for _, g := range m.geom {794 if done[g.id] {795 continue796 }797 ready := true798 for _, d := range g.deps {799 if !done[d] {800 ready = false801 break802 }803 }804 if ready {805 idx = append(idx, g.id)806 }807 }808 if len(idx) == 0 {809 return nil, errors.New("dependency cycle in tile order (bug)")810 }811 m.stats.Waves++812 results := make([]*tileWork, len(idx))813 errs := make([]error, len(idx))814 var wg sync.WaitGroup815 sem := make(chan struct{}, runtime.GOMAXPROCS(0))816 for k, i := range idx {817 wg.Add(1)818 sem <- struct{}{}819 go func(k, i int) {820 defer wg.Done()821 defer func() { <-sem }()822 // a tile whose givens fail is redrawn with a fresh salt823 // before the whole attempt is given up: the other tiles824 // of the attempt are fine, only this draw was not825 for wr := 0; wr < waveRetries; wr++ {826 salt := tag827 if wr > 0 {828 salt = fmt.Sprintf("%s|w%d", tag, wr)829 m.bump(&m.stats.WaveRetries)830 }831 results[k], errs[k] = m.buildGivens(ctx, salt, i)832 if errs[k] == nil || ctx.Err() != nil {833 break834 }835 }836 }(k, i)837 }838 wg.Wait()839 for k, i := range idx {840 if errs[k] != nil {841 g := m.geom[i]842 err := errs[k]843 if isLayoutClass(err) {844 // every refill and retry failed on a property of the845 // tile's geometry (its overlaps admit no pinning flip,846 // or its shared cells leave nothing to bifurcate on):847 // another draw of the same layout cannot help848 err = fmt.Errorf("%w: %v", errLayout, err)849 }850 return nil, fmt.Errorf("tile %d (%dx%d, %d cells at %d,%d): %w", g.pubID, g.W, g.H, g.cells, g.sh.X0, g.sh.Y0, err)851 }852 tiles[i] = results[k]853 m.commitGivens(results[k])854 done[i] = true855 remaining--856 }857 }858 if err := m.global.Validate(rules.All); err != nil {859 return nil, fmt.Errorf("solution invalid: %w", err)860 }861 m.stats.GivensMs = time.Since(tGivens).Milliseconds()862 tSettle := time.Now()863864 // Later tiles may have added seam givens on earlier tiles' shared cells:865 // settle every tile's final givens and solution set, then check the866 // coupled system has exactly one solution. Repair by regenerating the867 // givens of a tile that lacks a witness neighbour, or that its868 // neighbours' clues pinned past its policy.869 shapes := make([]rules.Shape, total)870 for i, g := range m.geom {871 shapes[i] = g.sh872 }873 regiven := func(bad, round int) error {874 for _, id := range tiles[bad].protect {875 delete(m.used, id)876 }877 var tw *tileWork878 var err error879 for wr := 0; wr < waveRetries; wr++ {880 salt := tag881 if wr > 0 {882 salt = fmt.Sprintf("%s|r%d", tag, wr)883 m.stats.WaveRetries++884 }885 tw, err = m.makeGivens(ctx, salt, bad, 100+round)886 if err == nil || ctx.Err() != nil {887 break888 }889 }890 if err != nil && ctx.Err() == nil {891 // no choice of givens over this solution works: redraw the892 // tile's interior (neighbours keep their shared cells) and try893 // the givens again over the new solution894 m.clearInterior(bad)895 if ok, ferr := m.fillTile(ctx, fmt.Sprintf("%s|rr%d", tag, round), bad, 300+round); ferr != nil {896 return ferr897 } else if ok {898 m.stats.Redraws++899 for wr := 0; wr < waveRetries; wr++ {900 tw, err = m.makeGivens(ctx, fmt.Sprintf("%s|rr%d|%d", tag, round, wr), bad, 100+round)901 if err == nil || ctx.Err() != nil {902 break903 }904 }905 }906 }907 if err != nil {908 return fmt.Errorf("repair tile %d: %w", m.geom[bad].pubID, err)909 }910 tiles[bad] = tw911 m.commitGivens(tw)912 m.stats.Regivens++913 return nil914 }915 released := make([]int, total)916 badRounds := make([]int, total)917 pairRounds := map[[2]int]int{}918 // repair rebuilds bad's givens; when that fails because the neighbours'919 // clues left nothing to pin on, it releases those clues, rebuilds bad920 // and then the neighbours that lost a clue, at most twice per tile921 repair := func(bad, round int) error {922 err := regiven(bad, round)923 if err == nil {924 return nil925 }926 if released[bad] >= 2 {927 return err928 }929 dirty := m.releaseClues(tiles, bad)930 if len(dirty) == 0 {931 return err932 }933 released[bad]++934 m.stats.Releases++935 if Verbose {936 fmt.Fprintf(os.Stderr, "gen: repair tile %d: released %d neighbours' clues (%v)\n", m.geom[bad].pubID, len(dirty), err)937 }938 if err := regiven(bad, round); err != nil {939 return err940 }941 for _, nb := range dirty {942 if m.geom[nb].fixed {943 continue944 }945 if serr := m.settle(tiles[nb]); serr != nil {946 if err := regiven(nb, round); err != nil {947 return err948 }949 }950 }951 return nil952 }953 for round := 0; ; round++ {954 sols := make([]rules.TileSolutions, total)955 settled := true956 for i := 0; i < total; i++ {957 t := tiles[i]958 if m.geom[i].fixed {959 sols[i] = t.sols960 continue961 }962 if err := m.settle(t); err != nil {963 if round >= 3*total {964 return nil, err965 }966 if Verbose {967 fmt.Fprintf(os.Stderr, "gen: settle: %v; regiven\n", err)968 }969 if err := repair(i, round); err != nil {970 return nil, err971 }972 settled = false973 break974 }975 sols[i] = t.sols976 }977 if !settled {978 continue979 }980 count, _ := sat.Coupled(shapes, sols, 2)981 if count == 1 {982 break983 }984 if round >= min(3*total, maxRepairRounds) {985 return nil, fmt.Errorf("coupled system has %d solutions after %d repairs", count, round)986 }987 bad, nb := m.witnessGap(tiles)988 if bad < 0 {989 return nil, fmt.Errorf("coupled system has %d solutions but every tile has a witness (bug)", count)990 }991 // the second time the same tile lacks a witness, its ambiguity is992 // correlated with the neighbour's (both alternatives agree on the993 // shared cells): rebuild that neighbour's givens first, so one of994 // the two can pin the other. When the same pair comes back a third995 // time the correlation is in the solutions themselves (a rectangle996 // on the overlap that flips validly in both tiles), and no choice997 // of givens breaks it: redraw the stuck tile's interior solution so998 // its flip geometry changes, then re-given both.999 badRounds[bad]++1000 pair := [2]int{bad, nb}1001 pairRounds[pair]++1002 if pairRounds[pair] >= 3 {1003 if Verbose {1004 fmt.Fprintf(os.Stderr, "gen: tiles %d/%d stay mutually unwitnessed; redrawing tile %d's interior\n", m.geom[bad].pubID, m.geom[nb].pubID, m.geom[bad].pubID)1005 }1006 for _, id := range tiles[bad].protect {1007 delete(m.used, id)1008 }1009 m.clearInterior(bad)1010 if ok, err := m.fillTile(ctx, fmt.Sprintf("%s|redraw%d", tag, round), bad, 200+round); err != nil {1011 return nil, err1012 } else if !ok {1013 return nil, fmt.Errorf("redraw tile %d: no completion", m.geom[bad].pubID)1014 }1015 pairRounds[pair] = 01016 badRounds[bad] = 01017 m.stats.Redraws++1018 }1019 if badRounds[bad] >= 2 && nb >= 0 && !m.geom[nb].fixed {1020 if Verbose {1021 fmt.Fprintf(os.Stderr, "gen: tile %d lacks a witness again; regiven its neighbour %d first\n", m.geom[bad].pubID, m.geom[nb].pubID)1022 }1023 if err := repair(nb, round); err != nil {1024 return nil, err1025 }1026 badRounds[bad] = 01027 }1028 if err := repair(bad, round); err != nil {1029 return nil, err1030 }1031 }10321033 m.stats.SettleMs = time.Since(tSettle).Milliseconds()1034 for _, t := range m.timers[:m.n] {1035 m.stats.LadderMs += t.LadderMs1036 m.stats.RemoveMs += t.RemoveMs1037 }1038 m.stats.TileTimers = append([]TileTimer(nil), m.timers[:m.n]...)1039 if attemptHook != nil {1040 attemptHook(m, tiles)1041 }1042 commit := DayCommit(p.Seed)1043 mByN := map[string]int{}1044 for n := pack.MinN; n <= pack.MaxN; n += 2 {1045 mByN[fmt.Sprint(n)] = pack.MByN(n)1046 }1047 out := &Output{1048 Manifest: Manifest{1049 HashScheme: "mosaic-tile-v1",1050 HashKeyCommit: HashKeyCommit(m.hashKey),1051 Version: 3,1052 ID: commit,1053 SeedCommit: commit,1054 G: m.G,1055 Packer: PackerInfo{Kind: L.Kind, Params: map[string]any{"n": p.N, "coverage": p.Coverage, "compound": p.Compound}},1056 MByN: mByN,1057 Rules: Rules{Overlaps: true, CrossTile: false, SeamClues: len(m.seamGivens) > 0, BandUnique: m.bandUniqueHeld},1058 SeedTile: m.geom[L.SeedTile].pubID,1059 K: "unmeasured",1060 Generator: generatorHash(),1061 },1062 Stats: m.stats,1063 DaySeed: p.Seed,1064 HashKey: hex.EncodeToString(m.hashKey),1065 }1066 for y := 0; y < m.G; y++ {1067 row := make([]byte, m.G)1068 for x := 0; x < m.G; x++ {1069 row[x] = '.'1070 for _, o := range m.owners[m.global.Idx(x, y)] {1071 if o < m.n {1072 row[x] = byte('0' + m.global.At(x, y))1073 break1074 }1075 }1076 }1077 out.Solution = append(out.Solution, string(row))1078 }1079 for _, t := range tiles[:m.n] {1080 pub := t.public1081 pub.ID = m.geom[t.id].pubID1082 pub.Overlaps = append([]OverlapPublic(nil), pub.Overlaps...)1083 for k := range pub.Overlaps {1084 pub.Overlaps[k].With = m.geom[pub.Overlaps[k].With].pubID1085 }1086 priv := t.private1087 priv.ID = pub.ID1088 out.Manifest.Tiles = append(out.Manifest.Tiles, pub)1089 out.Tiles = append(out.Tiles, priv)1090 }1091 if len(p.Fixed) > 0 || p.Region != [4]int{} {1092 out.Manifest.Packer.Params["region"] = p.Region1093 out.Manifest.Packer.Params["chunk"] = p.Chunk1094 out.Manifest.Packer.Params["id_base"] = p.IDBase1095 }1096 return out, nil1097}10981099// printTimers writes the timing table to stderr (MOSAIC_DEBUG=1).1100func printTimers(o *Output) {1101 st := o.Stats1102 fmt.Fprintf(os.Stderr, "gen: %d tiles in %d ms: fill %d ms, givens %d ms (waves %d, remove sum %d ms, ladder sum %d ms), settle+csp %d ms, sat %d calls / %d ms, attempts %d (wasted %d, %d ms), regivens %d, releases %d, backjumps %d\n",1103 len(o.Manifest.Tiles), st.Ms, st.FillMs, st.GivensMs, st.Waves, st.RemoveMs, st.LadderMs, st.SettleMs, st.SatCalls, st.SatMs, st.Attempts, st.Wasted, st.WastedMs, st.Regivens, st.Releases, st.Backjumps)1104 rows := append([]TileTimer(nil), st.TileTimers...)1105 sort.Slice(rows, func(a, b int) bool { return rows[a].GivensMs > rows[b].GivensMs })1106 if len(rows) > 12 {1107 rows = rows[:12]1108 }1109 fmt.Fprintf(os.Stderr, "gen: %6s %5s %7s %8s %6s %6s %6s %8s %8s\n", "tile", "cells", "fill", "givens", "rounds", "trials", "sat", "remove", "ladder")1110 for _, r := range rows {1111 fmt.Fprintf(os.Stderr, "gen: %6d %5d %7d %8d %6d %6d %6d %8d %8d\n", r.ID, r.Cells, r.FillMs, r.GivensMs, r.Rounds, r.Trials, r.SatCalls, r.RemoveMs, r.LadderMs)1112 }1113}11141115func generatorHash() string {1116 h := sha256.Sum256([]byte("mosaic-engine/" + Version))1117 return hex.EncodeToString(h[:8])1118}11191120// fillSolution walks the fill order with backjumping. A tile whose prefilled1121// cells admit no completion sends the search back to the latest earlier1122// tile that shares a cell with it; everything from there on is cleared and1123// redrawn with the next try. Repeated failures of the same tile escalate:1124// every second failure targets the next earlier dependency, so a conflict1125// caused by a neighbour other than the latest one is reached rather than1126// looping on a refill that cannot help.1127func (m *mosaic) fillSolution(ctx context.Context, tag string) error {1128 total := len(m.geom)1129 if m.n <= jointFillMax {1130 // a chunk: one joint completion of every new tile over the context,1131 // no backjumping. A NOFIT is definitive: the layout admits no1132 // solution against its context, and the caller re-packs.1133 shapes := make([]rules.Shape, 0, m.n)1134 for i := 0; i < m.n; i++ {1135 shapes = append(shapes, m.geom[i].sh)1136 }1137 assign, ok := sat.CompleteAll(m.global.Cells, m.G, shapes, rngFor(tag, "fill-all"))1138 if !ok {1139 return fmt.Errorf("layout admits no joint completion: %w", errFixedNoFit)1140 }1141 for id, v := range assign {1142 m.global.Cells[id] = v1143 }1144 return nil1145 }1146 tries := make([]int, total) // by tile id1147 fails := make([]int, total) // consecutive NOFITs by tile id1148 backjumps := 01149 for pos := m.firstNew; pos < total; {1150 if ctx.Err() != nil {1151 return ctx.Err()1152 }1153 i := m.order[pos]1154 t0 := time.Now()1155 ok, err := m.fillTile(ctx, tag, i, tries[i])1156 m.addTimer(i, func(t *TileTimer) { t.FillMs += time.Since(t0).Milliseconds() })1157 if err != nil {1158 return err1159 }1160 tries[i]++1161 if ok {1162 fails[i] = 01163 pos++1164 continue1165 }1166 backjumps++1167 m.bump(&m.stats.Backjumps)1168 if backjumps > 3*total {1169 return errBackjumps1170 }1171 g := m.geom[i]1172 // the conflict set: every redrawable earlier tile that fixes a cell1173 // of this tile or of a later neighbour it was completed jointly1174 // with (the joint check is what refused), latest first; fixed1175 // context tiles cannot be redrawn1176 inConf := map[int]bool{}1177 var byRank []int1178 addDeps := func(t *tileGeom) {1179 for _, d := range t.deps {1180 if m.geom[d].rank < g.rank && !m.geom[d].fixed && !inConf[d] {1181 inConf[d] = true1182 byRank = append(byRank, d)1183 }1184 }1185 }1186 addDeps(g)1187 for _, o := range m.geom {1188 if o.rank > g.rank {1189 for _, d := range o.deps {1190 if d == i {1191 addDeps(o)1192 break1193 }1194 }1195 }1196 }1197 if len(byRank) == 0 {1198 if len(g.deps) > 0 {1199 return fmt.Errorf("tile %d: %w", g.pubID, errFixedNoFit)1200 }1201 return fmt.Errorf("tile %d admits no completion with nothing prefilled (bug)", i)1202 }1203 sort.Slice(byRank, func(a, b int) bool { return m.geom[byRank[a]].rank > m.geom[byRank[b]].rank })1204 k := fails[i] / 21205 fails[i]++1206 if k >= len(byRank) {1207 k = len(byRank) - 11208 }1209 j := byRank[k]1210 if Verbose {1211 fmt.Fprintf(os.Stderr, "gen: tile %d (%d cells) has no completion; backjump to tile %d (dep %d of %d, try %d)\n", i, g.cells, j, k+1, len(byRank), tries[j])1212 if fails[i] == 20 {1213 // a tile refused twenty times: say what fixes the region1214 fmt.Fprintf(os.Stderr, "gen: diagnose tile %d (%dx%d at %d,%d rank %d): deps %v\n", i, g.W, g.H, g.sh.X0, g.sh.Y0, g.rank, g.deps)1215 report := func(t *tileGeom) {1216 owners := map[int]int{}1217 filled := 01218 for li, ok := range t.mask {1219 if !ok {1220 continue1221 }1222 id := t.gid(m, li)1223 if m.global.Cells[id] != rules.Empty {1224 filled++1225 for _, o := range m.owners[id] {1226 if o != t.id {1227 owners[o]++1228 }1229 }1230 }1231 }1232 fmt.Fprintf(os.Stderr, "gen: tile %d (%dx%d at %d,%d rank %d fixed %v): %d/%d cells fixed, by owner %v, deps %v\n", t.id, t.W, t.H, t.sh.X0, t.sh.Y0, t.rank, t.fixed, filled, t.cells, owners, t.deps)1233 }1234 report(g)1235 for _, o := range m.geom {1236 if o.rank > g.rank {1237 for _, d := range o.deps {1238 if d == i {1239 report(o)1240 break1241 }1242 }1243 }1244 }1245 }1246 }1247 for p := pos; p >= m.geom[j].rank; p-- {1248 m.clearTile(m.order[p])1249 }1250 pos = m.geom[j].rank1251 }1252 return nil1253}12541255// buildGivens makes a tile's givens over its solution. A few rounds try1256// different removal orders; if none work, the tile's own interior is1257// redrawn (shared cells stay, since the neighbours are filled already) and1258// the rounds repeat. Only after several refills does the attempt fail.1259// `fillTry` continues the per-tile fill counter across refills so each1260// draw is distinct and deterministic.1261func (m *mosaic) buildGivens(ctx context.Context, tag string, i int) (*tileWork, error) {1262 t0 := time.Now()1263 defer func() { m.addTimer(i, func(t *TileTimer) { t.GivensMs += time.Since(t0).Milliseconds() }) }()1264 var gerr error1265 fillTry := 1 // 0 was used by phase A1266 for refill := 0; refill < 6; refill++ {1267 for round := 0; round < 4; round++ {1268 tw, err := m.makeGivens(ctx, tag, i, refill*4+round)1269 if err == nil {1270 return tw, nil1271 }1272 if ctx.Err() != nil {1273 return nil, ctx.Err()1274 }1275 gerr = err1276 if Verbose {1277 fmt.Fprintf(os.Stderr, "gen: tile %d refill %d round %d: %v\n", i, refill, round, err)1278 }1279 }1280 m.clearInterior(i)1281 ok, err := m.fillTile(ctx, tag, i, fillTry)1282 fillTry++1283 if err != nil {1284 return nil, err1285 }1286 if !ok {1287 return nil, fmt.Errorf("refill %d admits no completion: %w", refill, gerr)1288 }1289 }1290 return nil, gerr1291}12921293// commitGivens registers a tile's planted cells and seam givens.1294func (m *mosaic) commitGivens(t *tileWork) {1295 for _, id := range t.protect {1296 m.used[id] = true1297 }1298 for _, id := range t.ownSeam {1299 m.seamGivens[id] = t.ownSeamValue[id]1300 m.seamOwner[id] = t.id1301 }1302}13031304func (m *mosaic) bump(counter *int) {1305 m.mu.Lock()1306 *counter++1307 m.mu.Unlock()1308}13091310// clearTile blanks every cell of the tile that no tile earlier in the fill1311// order owns.1312func (m *mosaic) clearTile(i int) {1313 g := m.geom[i]1314 for li, ok := range g.mask {1315 if !ok {1316 continue1317 }1318 id := g.gid(m, li)1319 earlier := false1320 for _, o := range m.owners[id] {1321 if m.geom[o].rank < g.rank {1322 earlier = true1323 }1324 }1325 if !earlier {1326 m.global.Cells[id] = rules.Empty1327 }1328 }1329}13301331// free counts the tile's cells no other tile shares.1332func (g *tileGeom) free() int {1333 n := 01334 for li, ok := range g.mask {1335 if ok && !g.shared[li] {1336 n++1337 }1338 }1339 return n1340}13411342// clearInterior blanks only the cells no other tile owns. Used once every1343// tile has a solution (phase B): a redraw must not touch a shared cell,1344// because the tiles across it are already filled and may be building their1345// givens in the same wave.1346func (m *mosaic) clearInterior(i int) {1347 g := m.geom[i]1348 for li, ok := range g.mask {1349 if !ok {1350 continue1351 }1352 id := g.gid(m, li)1353 if len(m.owners[id]) == 1 {1354 m.global.Cells[id] = rules.Empty1355 }1356 }1357}13581359// fillTile completes tile i over its prefilled cells, jointly with every1360// later neighbour (tiles after it in the fill order that share a cell):1361// one SAT instance over the union of those shapes, of which only tile i's1362// cells are written. That is forward checking with the interactions1363// between the neighbours included, which per-neighbour checks miss (the1364// last small neighbour of a boxed-in tile cannot balance its own edge and1365// finish the big tile's forced edge at once). Returns ok=false when no1366// joint completion exists: a definitive NOFIT, and the caller backjumps.1367func (m *mosaic) fillTile(ctx context.Context, tag string, i, refill int) (bool, error) {1368 g := m.geom[i]1369 // the joint region: every unfilled neighbour, and every unfilled tile1370 // that shares a cell with one of them (two hops). One hop keeps the1371 // neighbours completable; the second keeps the neighbours completable1372 // together, which is what a later NOFIT usually turns out to be about1373 inRegion := map[int]bool{}1374 var later []rules.Shape1375 add := func(j int) {1376 if j != i && !inRegion[j] && m.geom[j].rank > g.rank {1377 inRegion[j] = true1378 later = append(later, m.geom[j].sh)1379 }1380 }1381 var hop1 []int1382 for _, o := range m.geom {1383 if o.rank > g.rank {1384 for _, d := range o.deps {1385 if d == i {1386 hop1 = append(hop1, o.id)1387 add(o.id)1388 break1389 }1390 }1391 }1392 }1393 for _, j := range hop1 {1394 gj := m.geom[j]1395 for li, ok := range gj.mask {1396 if !ok {1397 continue1398 }1399 for _, o := range m.owners[gj.gid(m, li)] {1400 add(o)1401 }1402 }1403 }1404 // the one-hop region, for the fallback below1405 hop1Shapes := make([]rules.Shape, 0, len(hop1))1406 for _, j := range hop1 {1407 hop1Shapes = append(hop1Shapes, m.geom[j].sh)1408 }1409 const tries = 16 // only band collisions need a second draw1410 var collided []rules.Cell1411 for t := 0; t < tries; t++ {1412 if ctx.Err() != nil {1413 return false, ctx.Err()1414 }1415 rng := rngFor(tag, "fill", fmt.Sprint(i), fmt.Sprint(refill), fmt.Sprint(t))1416 full, ok := sat.CompleteRegion(m.global.Cells, m.G, later, g.sh, rng)1417 if !ok && len(hop1Shapes) < len(later) {1418 // the two-hop region refused; the direct neighbours may still1419 // admit a completion together with this tile (the second hop's1420 // infeasibility is theirs to backjump on). A one-hop UNSAT is1421 // a real NOFIT: no completion of this tile leaves its1422 // neighbours completable, so backjump rather than write it.1423 full, ok = sat.CompleteRegion(m.global.Cells, m.G, hop1Shapes, g.sh, rng)1424 }1425 if !ok {1426 return false, nil1427 }1428 if m.p.BandUnique && m.bandCollision(i, full) {1429 m.bump(&m.stats.Refills)1430 collided = full1431 continue1432 }1433 m.writeTile(g, full)1434 return true, nil1435 }1436 m.mu.Lock()1437 m.bandUniqueHeld = false1438 m.mu.Unlock()1439 m.writeTile(g, collided)1440 return true, nil1441}14421443// writeTile fills only the cells that are still empty: prefilled cells came1444// from earlier tiles and carry the same value.1445func (m *mosaic) writeTile(g *tileGeom, full []rules.Cell) {1446 for li, ok := range g.mask {1447 if !ok {1448 continue1449 }1450 id := g.gid(m, li)1451 if m.global.Cells[id] != rules.Empty {1452 continue1453 }1454 m.global.Cells[id] = full[li]1455 }1456}14571458// bandCollision reports whether any row of the candidate tile equals a row1459// of an already generated tile of the same size in the same band (same1460// y0). Only square tiles take part (the grid packers).1461func (m *mosaic) bandCollision(i int, full []rules.Cell) bool {1462 g := m.geom[i]1463 if g.W != g.H || len(g.sh.Rects) != 1 {1464 return false1465 }1466 seen := map[string]bool{}1467 for _, o := range m.geom {1468 if o.rank >= g.rank || o.sh.Y0 != g.sh.Y0 || o.W != g.W || o.H != g.H || len(o.sh.Rects) != 1 {1469 continue1470 }1471 for ly := 0; ly < o.H; ly++ {1472 row := make([]byte, o.W)1473 for lx := 0; lx < o.W; lx++ {1474 row[lx] = byte('0' + m.global.At(o.sh.X0+lx, o.sh.Y0+ly))1475 }1476 seen[string(row)] = true1477 }1478 }1479 for ly := 0; ly < g.H; ly++ {1480 row := make([]byte, g.W)1481 for lx := 0; lx < g.W; lx++ {1482 row[lx] = byte('0' + full[ly*g.W+lx])1483 }1484 if seen[string(row)] {1485 return true1486 }1487 }1488 return false1489}14901491// tileWork is a tile's givens under construction: its solution set, the1492// public and private records, the interior givens (local, Empty where1493// blank or outside the shape), the planted cells to protect from removal,1494// and the seam givens it added on its own shared cells (global ids and1495// values).1496type tileWork struct {1497 id int1498 sols rules.TileSolutions1499 public TilePublic1500 private TilePrivate1501 interior []rules.Cell1502 protect []int1503 ownSeam []int1504 ownSeamValue map[int]rules.Cell1505}15061507// puzzleOf assembles a tile's current puzzle: interior givens plus every1508// seam given on its cells, whichever tile added it.1509func (m *mosaic) puzzleOf(t *tileWork) []rules.Cell {1510 g := m.geom[t.id]1511 p := append([]rules.Cell(nil), t.interior...)1512 for li, ok := range g.mask {1513 if !ok {1514 continue1515 }1516 if v, ok := m.seamGivens[g.gid(m, li)]; ok {1517 p[li] = v1518 }1519 }1520 return p1521}15221523// settle recomputes a tile's givens, blank ratio, hash and solution set1524// from the final puzzle, and re-checks the assertions seam givens can move.1525func (m *mosaic) settle(t *tileWork) error {1526 g := m.geom[t.id]1527 p := m.puzzleOf(t)1528 var exhausted bool1529 t.sols, exhausted = solutionsPT(p, g.sh, g.m+1)1530 if !exhausted {1531 return fmt.Errorf("tile %d: solution count over budget after settling", t.id)1532 }1533 if len(t.sols) < 2 || len(t.sols) > g.m {1534 return fmt.Errorf("tile %d: %d solutions after settling", t.id, len(t.sols))1535 }1536 t.public.M = len(t.sols)1537 // pins follow the settled solution set: neighbours' seam clues may have1538 // removed alternatives, so the overlaps some alternative still differs1539 // on are recomputed here, not carried from makeGivens1540 truth := g.sh.Local(m.global.Cells, m.G)1541 pinned := map[int]bool{}1542 for _, s := range t.sols {1543 for _, li := range rules.Diff(truth, s) {1544 for _, oi := range g.regsAt[li] {1545 pinned[oi] = true1546 }1547 }1548 }1549 t.public.Pins = []int{}1550 for oi := range g.overlaps {1551 if pinned[oi] {1552 t.public.Pins = append(t.public.Pins, oi)1553 }1554 }1555 if len(t.public.Pins) == 0 {1556 return fmt.Errorf("tile %d: no alternative differs inside an overlap after settling", t.id)1557 }1558 t.private.Givens = nil1559 blanks := 01560 for li, ok := range g.mask {1561 if !ok {1562 continue1563 }1564 if p[li] == rules.Empty {1565 blanks++1566 } else {1567 t.private.Givens = append(t.private.Givens, [2]int{g.gid(m, li), int(p[li])})1568 }1569 }1570 t.private.Blank = float64(blanks) / float64(g.cells)1571 if t.private.Blank < PolicyFor(g.cells).BlankMin {1572 return fmt.Errorf("tile %d: %.0f%% blank after neighbours' seam clues", t.id, t.private.Blank*100)1573 }1574 // content hash: shape, solution bits, givens mask, shared mask, keyed1575 sol := make([]byte, len(p))1576 giv := make([]byte, len(p))1577 shared := make([]byte, len(p))1578 for li := range p {1579 sol[li], giv[li], shared[li] = '.', '.', '.'1580 if !g.mask[li] {1581 continue1582 }1583 sol[li] = byte('0' + m.global.Cells[g.gid(m, li)])1584 if p[li] != rules.Empty {1585 giv[li] = '1'1586 } else {1587 giv[li] = '0'1588 }1589 if g.shared[li] {1590 shared[li] = '1'1591 } else {1592 shared[li] = '0'1593 }1594 }1595 _ = shared1596 t.public.Hash = TileHash(m.hashKey, m.gameID, t.public.ID, g.sh.X0, g.sh.Y0, g.W, g.H, g.sh.Rects, sol, giv)1597 return nil1598}15991600// DayCommit is the public commitment to a day's seed: the manifest's id and1601// seed_commit. The seed itself (random, never derived from the date) is1602// private until the day is archived.1603func DayCommit(seed string) string {1604 h := sha256.Sum256([]byte("mosaic-day-seed-v1|" + seed))1605 return hex.EncodeToString(h[:])1606}16071608// DayKey derives the day key that keys every tile commitment:1609// HMAC-SHA256 with the label as key over the seed (a labelled one-step1610// KDF; the label domain-separates it from every other stream). Private1611// until the day is archived; sha256(DayKey) is published at start.1612func DayKey(seed string) []byte {1613 h := hmac.New(sha256.New, []byte("mosaic-day-key-v1"))1614 h.Write([]byte(seed))1615 return h.Sum(nil)1616}16171618// HashKeyCommit is what the manifest publishes about the day key.1619func HashKeyCommit(key []byte) string {1620 h := sha256.Sum256(key)1621 return hex.EncodeToString(h[:])1622}16231624// TileHash is a tile's commitment, scheme "mosaic-tile-v1": HMAC-SHA2561625// under the day key over a versioned, length-prefixed encoding of the1626// game id, the tile id, its geometry, its solution bits and its givens1627// mask (both packed over the shape's cells in raster order). Without the1628// key a tile's m candidate solutions cannot be told apart by hashing1629// them; with it (released with the archive) the record is verifiable.1630// The shared mask is not part of it: in a field, neighbours from later1631// chunks and rings change which cells are shared after the tile was1632// hashed. sol and giv are row-major W*H byte strings, '.' outside the1633// shape; sol holds '0'/'1', giv holds '1' for a given.1634func TileHash(key []byte, gameID string, id, x0, y0, W, H int, rects [][4]int, sol, giv []byte) string {1635 var buf []byte1636 u32 := func(v int) { buf = append(buf, byte(v>>24), byte(v>>16), byte(v>>8), byte(v)) }1637 str := func(v string) { u32(len(v)); buf = append(buf, v...) }1638 bits := func(src []byte, one byte) {1639 var cells []bool1640 for i := range src {1641 if src[i] != '.' {1642 cells = append(cells, src[i] == one)1643 }1644 }1645 u32(len(cells))1646 packed := make([]byte, (len(cells)+7)/8)1647 for i, b := range cells {1648 if b {1649 packed[i/8] |= 1 << (7 - uint(i%8))1650 }1651 }1652 u32(len(packed))1653 buf = append(buf, packed...)1654 }1655 str("mosaic-tile-v1")1656 str(gameID)1657 u32(id)1658 u32(x0)1659 u32(y0)1660 u32(W)1661 u32(H)1662 u32(len(rects))1663 for _, r := range rects {1664 for _, v := range r {1665 u32(v)1666 }1667 }1668 bits(sol, '1')1669 bits(giv, '1')1670 h := hmac.New(sha256.New, key)1671 h.Write(buf)1672 return hex.EncodeToString(h.Sum(nil))1673}16741675// tileGrid reads a tile's solution as H rows of W local cells (Empty1676// outside the shape).1677func (m *mosaic) tileGrid(i int) [][]rules.Cell {1678 g := m.geom[i]1679 s := make([][]rules.Cell, g.H)1680 for ly := range s {1681 s[ly] = make([]rules.Cell, g.W)1682 for lx := range s[ly] {1683 s[ly][lx] = rules.Empty1684 if g.mask[ly*g.W+lx] {1685 s[ly][lx] = m.global.At(g.sh.X0+lx, g.sh.Y0+ly)1686 }1687 }1688 }1689 return s1690}16911692// makeGivens plants a flip rectangle touching a pin-eligible overlap, then1693// removes clues while the tile keeps at most m solutions, and checks every1694// per-tile assertion.1695func (m *mosaic) makeGivens(ctx context.Context, tag string, i int, round int) (*tileWork, error) {1696 g := m.geom[i]1697 S := m.tileGrid(i)1698 gid := func(lx, ly int) int { return g.gid(m, ly*g.W+lx) }16991700 // preferred overlaps: with a neighbour closer to the seed tile1701 preferred := make([]bool, len(g.overlaps))1702 for oi, o := range g.overlaps {1703 preferred[oi] = m.geom[o.With].dist >= 0 && g.dist >= 0 && m.geom[o.With].dist < g.dist1704 }17051706 type cand struct {1707 r rules.Rect1708 pref bool1709 }1710 var cands []cand1711 for _, r := range rules.FindFlips(g.sh, S, rules.All) {1712 onRegion, pref, clash := false, false, false1713 for _, c := range r.Cells() {1714 li := c[1]*g.W + c[0]1715 if _, given := m.seamGivens[gid(c[0], c[1])]; given || m.used[gid(c[0], c[1])] || g.junction[li] {1716 clash = true1717 }1718 if len(g.regsAt[li]) > 0 {1719 onRegion = true1720 }1721 for _, oi := range g.regsAt[li] {1722 if preferred[oi] {1723 pref = true1724 }1725 }1726 }1727 if onRegion && !clash {1728 cands = append(cands, cand{r, pref})1729 }1730 }1731 if len(cands) == 0 {1732 // small tiles hemmed in by junctions may have no plantable1733 // rectangle: rely on the ambiguity blank shared cells leave naturally1734 cands = append(cands, cand{r: rules.Rect{R1: -1}})1735 }1736 rng := rngFor(tag, "givens", fmt.Sprint(i), fmt.Sprint(round))1737 rng.Shuffle(len(cands), func(a, b int) { cands[a], cands[b] = cands[b], cands[a] })1738 sort.SliceStable(cands, func(a, b int) bool { return cands[a].pref && !cands[b].pref })17391740 limit := len(cands)1741 if limit > 10 {1742 limit = 101743 }1744 // Candidates are independent and read-only over the mosaic, so they run1745 // in parallel; the winner is the first success by index, which keeps the1746 // output deterministic whatever the scheduling.1747 type result struct {1748 tw *tileWork1749 err error1750 ms int641751 }1752 results := make([]result, limit)1753 var wg sync.WaitGroup1754 for ci := 0; ci < limit; ci++ {1755 wg.Add(1)1756 go func(ci int) {1757 defer wg.Done()1758 t0 := time.Now()1759 crng := rngFor(tag, "givens", fmt.Sprint(i), fmt.Sprint(round), fmt.Sprint(ci))1760 tw, err := m.removeClues(ctx, crng, i, S, cands[ci].r)1761 results[ci] = result{tw, err, time.Since(t0).Milliseconds()}1762 }(ci)1763 }1764 wg.Wait()1765 m.addTimer(i, func(t *TileTimer) {1766 t.Rounds++1767 t.Trials += limit1768 for _, r := range results {1769 t.RemoveMs += r.ms1770 }1771 })1772 var lastErr error1773 for ci, res := range results {1774 if Verbose {1775 fmt.Fprintf(os.Stderr, "gen: tile %d (%d cells) flip %d/%d %v in %dms: %v\n", i, g.cells, ci+1, limit, cands[ci].r, res.ms, res.err)1776 }1777 if res.err == nil {1778 return res.tw, nil1779 }1780 lastErr = res.err1781 }1782 if ctx.Err() != nil {1783 return nil, ctx.Err()1784 }1785 return nil, fmt.Errorf("no acceptable givens: %w", lastErr)1786}17871788// solutionsPT enumerates up to limit solutions (all rules) with the SAT1789// backend. ok is always true (kept for the callers' shape).1790func solutionsPT(puzzle []rules.Cell, sh rules.Shape, limit int) (rules.TileSolutions, bool) {1791 sols, _ := sat.Enumerate(puzzle, sh, rules.All, limit)1792 return rules.TileSolutions(sols), true1793}17941795// countPT counts solutions up to limit (all rules) with the SAT backend.1796func countPT(puzzle []rules.Cell, sh rules.Shape, limit int) int {1797 c, _ := sat.Count(puzzle, sh, rules.All, limit)1798 return c1799}18001801// uniquenessRects lists rectangles whose flip keeps run and balance but1802// duplicates a line, shuffled.1803func uniquenessRects(sh rules.Shape, S [][]rules.Cell, rng *rand.Rand) []rules.Rect {1804 valid := map[rules.Rect]bool{}1805 for _, r := range rules.FindFlips(sh, S, rules.All) {1806 valid[r] = true1807 }1808 var out []rules.Rect1809 for _, r := range rules.FindFlips(sh, S, rules.Run|rules.Balance) {1810 if !valid[r] {1811 out = append(out, r)1812 }1813 }1814 rng.Shuffle(len(out), func(i, j int) { out[i], out[j] = out[j], out[i] })1815 return out1816}18171818func (m *mosaic) removeClues(ctx context.Context, rng *rand.Rand, ti int, S [][]rules.Cell, r rules.Rect) (*tileWork, error) {1819 g := m.geom[ti]1820 W := g.W1821 M := g.m1822 gid := func(lx, ly int) int { return g.gid(m, ly*W+lx) }1823 satCalls := 01824 defer func() { m.addTimer(ti, func(t *TileTimer) { t.SatCalls += satCalls }) }()1825 // one hot solver for this tile, and the solutions of the current1826 // puzzle found so far: adding a clue keeps a subset of them, removing1827 // one keeps all of them, so a count only ever has to look for1828 // solutions beyond the known set (usually one solve, often none)1829 inc := sat.NewIncremental(g.sh, rules.All)1830 var known [][]rules.Cell1831 countPT := func(puzzle []rules.Cell, _ rules.Shape, limit int) int {1832 satCalls++1833 known = sat.Consistent(puzzle, known)1834 known, _ = inc.Extend(puzzle, known, limit)1835 return len(known)1836 }1837 solutionsPT := func(puzzle []rules.Cell, _ rules.Shape, limit int) (rules.TileSolutions, bool) {1838 satCalls++1839 known = sat.Consistent(puzzle, known)1840 var ex bool1841 known, ex = inc.Extend(puzzle, known, limit)1842 return rules.TileSolutions(known), ex || len(known) >= limit1843 }1844 protect := map[int]bool{} // local indices never given: planted rectangles1845 planted := r.R1 >= 01846 if planted {1847 for _, c := range r.Cells() {1848 protect[c[1]*W+c[0]] = true1849 }1850 }1851 ownSeam := map[int]rules.Cell{} // seam givens this tile adds (local index)1852 build := func() []rules.Cell {1853 p := make([]rules.Cell, len(g.mask))1854 for i := range p {1855 switch {1856 case !g.mask[i]:1857 p[i] = rules.Empty1858 case protect[i]:1859 p[i] = rules.Empty1860 case g.shared[i]:1861 if v, ok := m.seamGivens[gid(i%W, i/W)]; ok {1862 p[i] = v1863 } else if v, ok := ownSeam[i]; ok {1864 p[i] = v1865 } else {1866 p[i] = rules.Empty1867 }1868 default:1869 p[i] = S[i/W][i%W]1870 }1871 }1872 return p1873 }1874 // Seam clues: blank shared cells alone can leave more than m1875 // solutions. Give the fewest shared cells that bring the count within1876 // m, never planted cells, never junctions.1877 addSeamClues := func() bool {1878 if countPT(build(), g.sh, M+1) <= M {1879 return true1880 }1881 // two tiers: first the shared cells nobody has a stake in; then,1882 // only if those do not suffice, cells a neighbour planted its flip1883 // on (m.used). Giving one of those kills that neighbour's1884 // alternative, which settle detects and regiven repairs; leaving1885 // this tile ambiguous would fail the attempt outright. Junctions1886 // (three or more owners) are never given.1887 var cands, planted []int1888 for i := range g.mask {1889 if !g.mask[i] {1890 continue1891 }1892 _, inherited := m.seamGivens[gid(i%W, i/W)]1893 _, own := ownSeam[i]1894 if !g.shared[i] || g.junction[i] || protect[i] || inherited || own {1895 continue1896 }1897 if m.used[gid(i%W, i/W)] {1898 planted = append(planted, i)1899 } else {1900 cands = append(cands, i)1901 }1902 }1903 rng.Shuffle(len(cands), func(a, b int) { cands[a], cands[b] = cands[b], cands[a] })1904 rng.Shuffle(len(planted), func(a, b int) { planted[a], planted[b] = planted[b], planted[a] })1905 cands = append(cands, planted...)1906 ok := false1907 added := []int{}1908 for _, i := range cands {1909 ownSeam[i] = S[i/W][i%W]1910 added = append(added, i)1911 if countPT(build(), g.sh, M+1) <= M {1912 ok = true1913 break1914 }1915 }1916 if !ok {1917 for _, i := range added {1918 delete(ownSeam, i)1919 }1920 return false1921 }1922 for _, i := range added {1923 v := ownSeam[i]1924 delete(ownSeam, i)1925 if countPT(build(), g.sh, M+1) > M {1926 ownSeam[i] = v1927 }1928 }1929 return true1930 }1931 if !addSeamClues() {1932 return nil, fmt.Errorf("shared cells stay ambiguous with every one given")1933 }1934 // Plant a uniqueness situation: a rectangle whose flip is legal under1935 // run+balance but duplicates a line. Kept blank, only the uniqueness1936 // constraint separates the solution from its flip there.1937 uniq := uniquenessRects(g.sh, S, rng)1938 if len(uniq) > 4 {1939 uniq = uniq[:4]1940 }1941 for _, u := range uniq {1942 clash := false1943 for _, c := range u.Cells() {1944 li := c[1]*W + c[0]1945 id := gid(c[0], c[1])1946 _, given := m.seamGivens[id]1947 _, own := ownSeam[li]1948 if protect[li] || m.used[id] || given || own || g.junction[li] {1949 clash = true1950 }1951 }1952 if clash {1953 continue1954 }1955 for _, c := range u.Cells() {1956 protect[c[1]*W+c[0]] = true1957 }1958 if addSeamClues() {1959 break1960 }1961 for _, c := range u.Cells() {1962 delete(protect, c[1]*W+c[0])1963 }1964 }1965 puzzle := build()1966 blanks := 01967 var removable []int1968 for i, v := range puzzle {1969 if !g.mask[i] {1970 continue1971 }1972 if v == rules.Empty {1973 blanks++1974 } else if !g.shared[i] {1975 removable = append(removable, i)1976 }1977 }1978 count := func(lim int) int { return countPT(puzzle, g.sh, lim) }1979 rng.Shuffle(len(removable), func(a, b int) { removable[a], removable[b] = removable[b], removable[a] })1980 pol := PolicyFor(g.cells)1981 // the technique checks (needs a bifurcation, needs uniqueness) are1982 // about the work left inside the tile once its neighbours have fixed1983 // the shared cells, so they key on the free cells, not the total: a1984 // 160-cell tile with 60 shared cells is a 100-cell puzzle1985 tech := PolicyFor(g.free())1986 pol.NeedsUnique, pol.NeedsBifurcation = tech.NeedsUnique, tech.NeedsBifurcation1987 target := int(pol.BlankMax * float64(g.cells))1988 for _, i := range removable {1989 if blanks >= target {1990 break1991 }1992 if ctx.Err() != nil {1993 return nil, ctx.Err()1994 }1995 saved := puzzle[i]1996 puzzle[i] = rules.Empty1997 t := rules.Single(g.sh, append([]rules.Cell(nil), puzzle...))1998 t.Propagate(rules.All, 0)1999 if t.Cells[i] == saved {2000 blanks++2001 continue2002 }2003 if count(M+1) > M {2004 puzzle[i] = saved2005 continue2006 }2007 blanks++2008 }2009 blank := float64(blanks) / float64(g.cells)2010 if blank < pol.BlankMin {2011 return nil, fmt.Errorf("only %.0f%% blank", blank*100)2012 }2013 sols, exhausted := solutionsPT(puzzle, g.sh, M+1)2014 if !exhausted {2015 return nil, errors.New("solution count over budget")2016 }2017 if len(sols) < 2 || len(sols) > M {2018 return nil, fmt.Errorf("%d solutions alone", len(sols))2019 }2020 // every alternative must differ inside some pin-eligible overlap2021 flat := make([]rules.Cell, len(g.mask))2022 for ly := 0; ly < g.H; ly++ {2023 copy(flat[ly*W:(ly+1)*W], S[ly])2024 }2025 pins := map[int]bool{}2026 for _, s := range sols {2027 d := rules.Diff(flat, s)2028 if len(d) == 0 {2029 continue2030 }2031 touched := false2032 for _, i := range d {2033 for _, oi := range g.regsAt[i] {2034 pins[oi] = true2035 touched = true2036 }2037 }2038 if !touched {2039 return nil, errors.New("an alternative solution differs inside no overlap region")2040 }2041 }2042 // technique checks on the pinned puzzle (every shared cell fixed)2043 pinned := append([]rules.Cell(nil), puzzle...)2044 for i := range pinned {2045 if g.mask[i] && g.shared[i] {2046 pinned[i] = S[i/W][i%W]2047 }2048 }2049 tLadder := time.Now()2050 rating := rules.Single(g.sh, append([]rules.Cell(nil), pinned...)).Ladder(12)2051 m.addTimer(ti, func(t *TileTimer) { t.LadderMs += time.Since(tLadder).Milliseconds() })2052 needsBif := rating.UsedBifurcation2053 satCalls++2054 noUnique, _ := sat.Count(pinned, g.sh, rules.Run|rules.Balance, 2)2055 needsUnique := noUnique >= 22056 if pol.NeedsBifurcation && !needsBif {2057 return nil, errors.New("pinned tile falls to propagation alone")2058 }2059 if pol.NeedsUnique && !needsUnique {2060 return nil, errors.New("pinned tile is unique without the uniqueness constraint")2061 }2062 if one, ok := solutionsPT(pinned, g.sh, 2); !ok || len(one) != 1 {2063 return nil, errors.New("pinned tile is not unique (bug)")2064 }20652066 tw := &tileWork{id: ti, sols: sols}2067 tw.public = TilePublic{ID: ti, X0: g.sh.X0, Y0: g.sh.Y0, W: g.W, H: g.H, Rects: g.sh.Rects, Cells: g.cells, M: len(sols), Overlaps: []OverlapPublic{}, Pins: []int{}}2068 for oi, o := range g.overlaps {2069 tw.public.Overlaps = append(tw.public.Overlaps, OverlapPublic{With: o.With, Cells: o.Cells})2070 if pins[oi] {2071 tw.public.Pins = append(tw.public.Pins, oi)2072 }2073 }2074 tw.private = TilePrivate{ID: ti, Blank: blank, NeedsUnique: needsUnique, NeedsBifurcation: needsBif, Flip: []int{},2075 Ladder: Ladder{UsedUnique: rating.UsedUnique, UsedBifurcation: rating.UsedBifurcation, Bifurcations: rating.Bifurcations, Complete: rating.Complete}}2076 if planted {2077 for _, c := range r.Cells() {2078 tw.private.Flip = append(tw.private.Flip, gid(c[0], c[1]))2079 }2080 }2081 tw.interior = make([]rules.Cell, len(g.mask))2082 for i, v := range puzzle {2083 if !g.mask[i] || g.shared[i] {2084 tw.interior[i] = rules.Empty2085 } else {2086 tw.interior[i] = v2087 }2088 }2089 for i := range protect {2090 tw.protect = append(tw.protect, gid(i%W, i/W))2091 }2092 tw.ownSeamValue = map[int]rules.Cell{}2093 for i, v := range ownSeam {2094 id := gid(i%W, i/W)2095 tw.ownSeam = append(tw.ownSeam, id)2096 tw.ownSeamValue[id] = v2097 }2098 sort.Ints(tw.protect)2099 sort.Ints(tw.ownSeam)2100 for i, v := range puzzle {2101 if g.mask[i] && v != rules.Empty {2102 tw.private.Givens = append(tw.private.Givens, [2]int{gid(i%W, i/W), int(v)})2103 }2104 }2105 return tw, nil2106}21072108// errFixedNoFit: a tile has no completion given only fixed context tiles,2109// which no redraw can change.2110var errFixedNoFit = errors.New("admits no completion against the fixed context")21112112// waveRetries is how many fresh draws a tile's givens get (in a wave, or2113// in a repair) before the attempt is given up; an attempt restart redraws2114// every tile, which is the expensive way to fix one.2115const waveRetries = 321162117// attemptHook, when set (tests), sees the mosaic after every assertion2118// held and before the output is assembled.2119var attemptHook func(m *mosaic, tiles []*tileWork)21202121// releaseClues takes back the seam clues other tiles put on bad's shared2122// cells (they can fix its only pin-eligible overlap outright, leaving2123// nothing for an alternative to differ on) and returns the tiles that2124// lost a clue, sorted, so their givens can be rebuilt afterwards.2125func (m *mosaic) releaseClues(tiles []*tileWork, bad int) []int {2126 g := m.geom[bad]2127 var dirty []int2128 seen := map[int]bool{}2129 for li, ok := range g.mask {2130 if !ok || !g.shared[li] {2131 continue2132 }2133 id := g.gid(m, li)2134 nb, has := m.seamOwner[id]2135 if !has || nb == bad {2136 continue2137 }2138 delete(m.seamGivens, id)2139 delete(m.seamOwner, id)2140 t := tiles[nb]2141 delete(t.ownSeamValue, id)2142 for k, v := range t.ownSeam {2143 if v == id {2144 t.ownSeam = append(t.ownSeam[:k], t.ownSeam[k+1:]...)2145 break2146 }2147 }2148 if !seen[nb] {2149 seen[nb] = true2150 dirty = append(dirty, nb)2151 }2152 }2153 sort.Ints(dirty)2154 return dirty2155}21562157// tileWithoutWitness finds a tile some alternative of which is not refuted2158// by any neighbour that is unanimous on a shared cell where the alternative2159// differs from the solution. Returns -1 if every tile has a witness.2160func (m *mosaic) tileWithoutWitness(tiles []*tileWork) int {2161 bad, _ := m.witnessGap(tiles)2162 return bad2163}21642165// witnessGap is tileWithoutWitness that also names the neighbour sharing2166// the most cells where the unwitnessed alternative differs (the one whose2167// own ambiguity lets it through), or -1.2168func (m *mosaic) witnessGap(tiles []*tileWork) (bad, neighbour int) {2169 unanimous := func(t *tileWork, gx, gy int) bool {2170 g := m.geom[t.id]2171 i := (gy-g.sh.Y0)*g.W + (gx - g.sh.X0)2172 v := t.sols[0][i]2173 for _, s := range t.sols[1:] {2174 if s[i] != v {2175 return false2176 }2177 }2178 return v == m.global.At(gx, gy)2179 }2180 for ti, t := range tiles[:m.n] {2181 g := m.geom[ti]2182 f := g.sh.Local(m.global.Cells, m.G)2183 for _, s := range t.sols {2184 d := rules.Diff(f, s)2185 if len(d) == 0 {2186 continue2187 }2188 witness := false2189 for _, i := range d {2190 gx, gy := g.sh.X0+i%g.W, g.sh.Y0+i/g.W2191 for _, ui := range m.owners[m.global.Idx(gx, gy)] {2192 if ui != ti && unanimous(tiles[ui], gx, gy) {2193 witness = true2194 break2195 }2196 }2197 if witness {2198 break2199 }2200 }2201 if !witness {2202 shares := map[int]int{}2203 for _, i := range d {2204 gx, gy := g.sh.X0+i%g.W, g.sh.Y0+i/g.W2205 for _, ui := range m.owners[m.global.Idx(gx, gy)] {2206 if ui != ti {2207 shares[ui]++2208 }2209 }2210 }2211 nb, best := -1, 02212 for ui, c := range shares {2213 if c > best || (c == best && ui < nb) {2214 nb, best = ui, c2215 }2216 }2217 return ti, nb2218 }2219 }2220 }2221 return -1, -12222}