Tile the board into small blocks, solve each one to proven optimality, and glue them together, paying for the seams instead of forbidding them. From scratch, with no record to copy, it reaches 448.
Reproducedeterministic — reproduces byte-for-byte·reruns the search (See below)·Budget: ~30 s per block × 16 blocks (exploratory run, not the standardized single-core bench)
Pipeline
1
MaxSAT
Solve each 4×4 block to a provable optimum with core-guided weighted MaxSAT; shared edges are soft clauses
carries: Scarcity reservation: hold back the ~8% globally scarcest pieces to fight piece theft
2
exact tail
Coarse backtracking over the per-block MaxSAT solution enumerators composes the blocks into a full board
Complexity
Time
per 4×4 block ~30 s to MaxSAT optimum (3×3 ~11 s); 16 block levels with backtracking
Space
one MaxSAT solution enumerator per block level held on the backtrack stack
Each block is exact (MaxSAT-optimal), but composing 16 of them is a coarse 16-level backtracking search, exponential in the worst case, tractable because each node is a whole provably-optimal block.
Hardware & run
Native runCPU only
0.067core-hours
Cores
8
RAM
16 GiB
GPUs
0
CPU
Apple M1
Machine
MacBook (Apple M1, 8 cores)
Budget
~30 s per block × 16 blocks (exploratory run, not the standardized single-core bench)
Eternity II has no local structure you can exploit globally, but a small
window of it, a 4×4 block, solves to perfect optimality in seconds. MOSAIC is
an experiment built on that single fact: if you can solve a block exactly, can
you compose sixteen exact blocks into a whole board?
The 16×16 board is cut into sixteen 4×4 blocks, filled one at a time. Each
block is handed to an exact MaxSAT solver, which finds the best possible
placement of pieces in it. The trick is in how a block meets its
already-placed neighbours: those shared edges are not hard requirements but
soft targets the block is rewarded for matching. So a block can never become
impossible; it simply pays for any seam it can't match, and always completes.
The second idea fights piece theft directly. Before filling a block, MOSAIC
holds back the globally scarcest pieces, so the last blocks aren't starved of
the rare pieces their seams will demand. Tuning how much to reserve is the one
real knob; too little and the corner starves, too much and the early blocks
suffer.
The window primitive does what it promises: a 4×4 block solves to its 24-edge
optimum in about thirty seconds, a 3×3 in eleven, confirming the puzzle
really is tractable in the small. Composed across the whole board, from
scratch and with no warm start, MOSAIC reaches 448 of 480. The reservation
sweet spot is around eight percent of the pool.
The shortfall is informative: almost all of it is in the last three blocks of
the bottom-right corner, where the pool finally runs thin: piece theft again,
now visible as a single bright spot on the board. Exact-in-the-small does
compose, but the composition order spends its freedom early and pays for it at
the end, the same shape every method here runs into.
The exactness is genuine, and so is the backtracking that stitches it
together.
Exact blocks. Each 4×4 block is encoded as a weighted MaxSAT problem
and solved by RC2, a core-guided solver, to a provably-optimal fill. Shared
edges with already-placed neighbours are soft clauses (rewarded, not
required), so a block can never be infeasible, it pays for any seam it can't
match and always completes.
Backtracking over solutions. MOSAIC is not a one-shot glue. Each block
level keeps an enumerator of MaxSAT solutions, best-first, via RC2 plus
blocking clauses that rule out already-seen fills. When a later block is
starved or a level exhausts, it backtracks and pulls the next solution of
the previous block (freeing a different set of pieces). It is a coarse
16-level backtracking search where each node is a whole optimal block.
Scarcity reservation. Before filling, MOSAIC holds back the globally
scarcest pieces so the final blocks aren't starved of the rare pieces their
seams demand. That reservation fraction is the one real knob; the measured
sweet spot is ~8% of the pool.
The window primitive is real: a 4×4 block reaches its 24-edge optimum in ~30 s,
a 3×3 in ~11 s, the puzzle is tractable in the small. Composed from scratch
it reaches 448, with the residual shortfall concentrated in the last three
bottom-right blocks: piece theft made visible as a
single bright spot.
Deterministic: the MaxSAT block solves and the backtracking composition are
exact, so kind: exact, the 448 board reproduces and is checkable edge by
edge in the viewer. The block engine runs from the puzzle alone, with no corpus
or seed board, its only external dependency being a MaxSAT solver, so a runnable
backing directory for it is planned alongside the other exact experiments.
Would a non-row-major block order, spiralling in or solving the constrained
corner first, move the depletion off the hardest block? Could blocks overlap,
so seams are solved twice and reconciled? And does a faster (Rust) primitive
make a larger block size, with its stronger exact guarantee, affordable?