Joshua Blackwood's record backtracker, decoded through Jef Bucas's notes (a colour quota schedule and a late-game mismatch allowance, tuned near-optimally), then built and run on my M1: left as published it flies to 248 of 256 pieces ignoring the clues; pin the five official clues and the same engine stalls near 45.
The algorithm and the C# are Joshua Blackwood's
(EternityII_Solver,
public on GitHub under the GPL-3.0). The decoding of the internals, along with
the parameter study reported below, is Jef Bucas's, in his
wrapper_blackwood project; the
decoded sections rephrase and extend
his notes
with his explicit permission
(groups.io message 11905), and
the figures are his, reproduced from the same notes. The final section is
Raphaël Anjou building and running
Blackwood's code on one machine and writing up what it did; the three small
edits to his source are listed there, each one his own README invites.
Joshua Blackwood holds the standing 470 record, found with code he made public.
His solver is, at heart, a classic depth-first backtracker running the same loop
as any other: place, check, back up. What makes it the engine behind the
community's best boards is a set of manually crafted heuristics layered on top: a
scoring rule that decides which pieces to try first, a depth-by-depth quota
schedule that prunes branches falling behind, a
fill order tuned to be "not too tight
and not too loose", and a late-game allowance for accumulating mismatches. Every
one of those choices has numbers in it, and Jef Bucas's study asked the obvious
question: are Blackwood's numbers any good? They are, uncomfortably so. Because
the code is a real, buildable C# program, it can then be run exactly as its
author wrote it, which is what the last section here does.
The solver scores every piece by the colours on its sides, and it privileges
exactly three of them, one border colour and two interior colours:
heuristic_sides = new List<int>() { 13, 16, 10 };
Pieces carrying those colours are sorted to the front of every candidate list, so
the search commits them early. Why these three? That is one of the two knobs
Jef's study turned (see below). His sampling suggests the best known scores come
from two distinct pattern sets:
The two pattern sets behind the best-scoring 470-class runs, mapped onto the board: the three privileged motifs cluster in the region the scan fills first. Figures by Jef Bucas (wrapper_blackwood), reproduced with permission.
Prioritizing three colours only helps if the search is forced to actually place
them. So the solver carries a 256-entry array, one entry per depth, where each
value is the minimum number of those three colours that must already be on the
board to keep descending. Fall below the quota and the branch is cut on the spot:
backtrack, no discussion.
Blackwood filled that array by hand, as a piecewise-linear ramp:
heuristic_array = new int[256];for (int i = 0; i < 256; i++) { if (i <= 16) heuristic_array[i] = 0; else if (i <= 26) heuristic_array[i] = (int)(((float)i - 16) * (float)2.8); else if (i <= 56) heuristic_array[i] = (int)((((float)i - 26) * (float)1.43333) + 28); else if (i <= 76) heuristic_array[i] = (int)(((((float)i - 56) * (float)0.9)) + 71); else if (i <= 102) heuristic_array[i] = (int)(((((float)i - 76) * (float)0.6538)) + 89); else if (i <= 160) heuristic_array[i] = (int)(((((float)i - 102) / 4.4615)) + 106);}
Free until depth 16, steep through the 20s, then flattening out to depth 160.
This is the "schedule" in schedule-and-break-index: a pre-committed timetable for
burning down the high-frequency colours, enforced as a hard prune.
The schedule drawn: quota curves ramp to about 115 privileged placements by depth ~155, then release. Figure by Jef Bucas (wrapper_blackwood), reproduced with permission.
The search starts at the bottom-left of the board (the corner nearest the
mandatory centre piece) and runs a standard row scan all the way to depth 180.
After that, it intersperses the remaining border pieces (including the third
corner) every few steps among the interior placements.
That is a deliberate middle course. Spiralling in (border ring first) commits the
most constrained pieces too early; a pure row scan leaves them all to the end,
where they ambush you. Blackwood's order releases the border pressure
progressively. Why the order matters this much, and how to score one before
running it, is exactly what complex theory
formalizes.
Blackwood's fill order: a bottom-left row scan to depth 180, border pieces interspersed afterwards. Figure by Jef Bucas (wrapper_blackwood), reproduced with permission.
Approaching the end of the search, the solver stops demanding perfection. A
budget of edge mismatches unlocks with depth, cumulatively: one break is allowed
from depth 201 onward (it can be spent at 201 or any later depth), a second from
206, and so on:
Ten breaks in total, the last unlocking at depth 239. This is what makes the
record boards reachable at all: a perfect 256 has never been
found, but a board that tolerates a handful of late mismatches is something a
backtracker can actually finish.
Two details sharpen the picture. First, the budget comes with a discipline: no
two breaks are ever allowed to touch: each mismatch must sit isolated among
matched edges. Blackwood spells out the consequence himself: any run that reaches
255 placements automatically completes to 256, and a 469 board is equivalently a
249-piece partial with seven holes
(groups.io message 10051). Second,
the ten-entry list above is itself a retune: planning the push from 469 to 470,
Blackwood cut the break budget from eleven depths to ten, a change he documented,
lever by lever, in his own tuning plan
(groups.io message 10076). The
shifted unlock points he sketched in that plan were never adopted (the published
470 code keeps the 469-era points and simply drops the eleventh), and that
tightened schedule is what found the 470.
A row-scan backtracker rarely climbs back up to its first rows, so a bad opening
can strand an entire run in an impossible region. Blackwood's answer is cheap and
effective: randomize the opening (the first corner and the bottom-row pieces are
shuffled on every attempt, so no two runs retrace the same prefix) and cap each
attempt at 50 billion nodes explored. Hit the cap, abandon,
restart with a fresh opening, and go
looking for a more fertile one.
The last ingredient is mechanical sympathy. Candidate pieces live in per-position
lookup tables, and each entry is a compact struct (piece number, rotation, the
two exposed sides, a break count and a heuristic count) sized so the working set
fits in CPU cache:
public struct RotatedPiece{ public ushort PieceNumber { get; set; } public byte Rotations { get; set; } public byte TopSide { get; set; } public byte RightSide { get; set; } public byte Break_Count { get; set; } public byte Heuristic_Side_Count { get; set; }}
This is the throughput half of the story: the same design that
Peter McGavin later pushed
to hundreds of millions of placements per second.
The solver's history is as instructive as its internals. Blackwood arrived a
complete outsider: his 468, the first advance past
Louis Verhaard's 467 in twelve
years, reached the mailing list second-hand, relayed from a Reddit post
(groups.io message 10032). Three
days later he open-sourced the solver, with heuristics he reckoned made it "twice
as good" as the 468 run
(message 10037); Jef Bucas had it
running under Mono on Ubuntu almost immediately
(message 10038). Within a week,
Peter McGavin, running it "on about a couple of hundred cores," hit 469
(message 10045). Bucas then
rewrote the algorithm in C for roughly double the speed
(message 10065), a wave of fresh
469 boards followed within weeks, and the code generator behind the rewrite was
published as libblackwood
(message 10078). When Blackwood
posted his 470 in March 2021, it came from that same public code. His own words,
on re-publishing the repo after it had quietly gone private: "It is the exact code
used to find a 470"
(message 10161). One record,
open-sourced, became a community record machine.
All of the above is how the solver works. Jef Bucas built
wrapper_blackwood to ask whether
its numbers are right. The setup is a small
distributed experiment: a Python
server hands out jobs over HTTP, where each job is a variation of the solver's
parameters. Clients (one worker per core) fetch a job, generate the C# source
from templates with that variation baked in, compile it with Mono, run it, and
report the result back to the server for analysis.
Two parameters got the treatment:
The three prioritized colours. Sampling many different sets of three
patterns, and recording how deep the algorithm got with each, his
results page
maps every combination of one border colour and two interior colours to the
depth it reached, together with a heatmap of where in the board the search
spent its time. The best known scores concentrate on two distinct pattern sets.
The quota schedule. Running many random variations of the 256-entry
heuristic array and plotting how far each one got (greener is better),
Blackwood's manually crafted curve lands right in the middle of the green
region.
Hundreds of random variations of the quota schedule, coloured by how deep the search got (green = deeper, red/black = shallower). The blue line is Blackwood's hand-tuned schedule, squarely inside the best-performing band. Figure by Jef Bucas (wrapper_blackwood), reproduced with permission.
That last result deserves emphasis. Blackwood filled his schedule by hand: five
linear segments, eyeballed coefficients. When a randomized sweep explored the
neighbourhood around it, the hand-tuned line sat squarely in the best-performing
zone. Jef's conclusion, and ours: the original parameters were near-optimal. The
decades-old advice holds. Before you redesign a record solver's heuristics, check
whether its author already found the local optimum by hand.
Blackwood's own negative results
Blackwood ran the same audit on himself. After the 469 he catalogued his dead
ends on the mailing list
(groups.io message 10056):
eliminating four colours early instead of three (no gain), saving colours for
the endgame (worse), SAT solvers such as kissat, cryptominisat and Google
OR-tools (poor), GPU acceleration, and caching all pre-solved 2×2 blocks
(measured, then dropped). The only thing that ever paid was refining the
heuristics themselves, worth another ~2x. It is the same conclusion as Jef's
sweep, reached from the other direction: the schedule is the magic, not the raw
technology.
One caveat on the parameter study, and it is Jef's own: the sample counts behind
these results are low, and he is not 100% sure of the conclusions. His notes say
it plainly: it would be good to attempt to reproduce these results, to validate
or invalidate them. He offers his samples, and the
wrapper_blackwood harness is
public: point a few machines at the server, re-run the sweeps, and post what you
find on the mailing list. An independent
replication would confirm or refute the findings, and either outcome would be a
real contribution.
The study above audits Blackwood's parameters; this last section audits something
different: what his published program does when you build it yourself and hold it
to the real puzzle, single core, on my machine.
The source is his public repository,
github.com/jblackwood345/EternityII_Solver,
under the GPL-3.0. It builds unmodified on .NET 8. It is not copied here: the
licence and good manners both say to link it, not vendor it, so it was cloned to
a scratch directory, run, and only the numbers kept.
His program is written to run on one machine's full core count and to save only
near-complete boards. To measure it single core, and to see anything short of a
full solve, three edits were made, each of which his own README invites ("change
the number of cores", "change the save function"):
One search thread. His number_virtual_cores constant defaults to 64. His
Parallel.For(1, N) runs N-1 workers, so setting it to 2 gives exactly one
search thread.
A progress line. Unmodified, in a bounded run it prints only "Solving...".
A single added line reports the deepest placement reached, so a run that does
not finish still yields a number.
A lower save threshold, and clue pinning for the constrained run below.
Left as published: fast, and aimed at the one clue that binds#
Run as his code stands, single core for 60 seconds, it is fast and it gets far:
248 / 256 pieces placed, a board that re-scores to 454 / 480 matched
edges.
~18.9 million nodes per second (one node is one placement attempt).
His published program has no notion of clues at all: it treats every piece,
including the special ones, as ordinary and maximises raw matched edges. This is
less of a compromise than it first looks, because a legal Eternity II board has
exactly one binding constraint, the mandatory centre clue (piece 139 in its
centre cell, in its given orientation); the puzzle's other four "clues" were bonus
hints the maker released, not requirements. His celebrated 470 board is the
proof: in the viewer it verifies as clues respected 1 / 5, the one
respected being the centre, and one is all a legal board needs. Maximising edges
without clue logic is not a shortcut around the puzzle; it is a legitimate way to
attack the one that binds.
The last eight cells of that 454 board are a genuine dead end: no arrangement of
the eight leftover pieces completes them edge-perfectly. (For fun, handing that
board to our ALNS for 30
seconds filled all eight and pushed it to 462 by rearranging the region.)
Pinning the clue pieces into their cells forces the engine to respect them
instead of placing them wherever they fit. The same code, all five official
clues pinned, 120 seconds, single core:
Deepest placement: about 45 / 256.
His scan-order heuristic has nothing to grip once the special pieces are fixed
mid-board: it thrashes near the bottom rows and never climbs. Pinning all five is
stricter than the puzzle strictly requires (only the centre clue is mandatory),
but it is the same constraint the other engines are held to here, and Blackwood
lands far below the
Verhaard reimplementation's 438
or McGavin's 204 under the
same constraint.
A fair caveat
This clue pin is crude: it forbids every other piece at the five clue cells and
reserves those pieces. A clue-aware redesign would search outward from the clues
instead, and would do better. So 45 is a floor for "his published code with
clues bolted on", not a verdict on the approach. His record 470 was found with
this code plus a great deal of compute and luck, not in two minutes.
