Whose work this is
The solver, called eii, and its documentation are Louis Verhaard's,
hosted on his own site
(shortestpath.se/eii). The winning entry was
submitted under the name of his wife, Anna Karlsson; Verhaard's own words
settle the credit: "My wife submitted my best solution last year and won 10 000
dollars" (groups.io message 7451).
This page, written up by Raphaël Anjou,
reconstructs the machine from Verhaard's mailing-list posts of 2008–2010 and
from JSA's public benchmark of the released binary, and records why the original
binary cannot be run here at all. The runnable engine is a separate
reimplementation,
filed here in this section beside the method, bylined to Raphaël because that
code is his, not Verhaard's.
Louis Verhaard's eii is the solver behind the 467/480 that won the $10,000
runner-up prize at the first scrutiny date, the only money the Eternity II
contest ever paid out. The same score then stood as the record for twelve years,
until Joshua Blackwood's 468 in 2020. Like
Blackwood's engine, it is at
heart a depth-first backtracker with hand-tuned heuristics layered on top. Unlike
Blackwood's, its internals were never open-sourced as code; what we have instead
is unusually good testimony: Verhaard documented the heuristics and search order
himself, discussed the design on the mailing list in first person, and shipped a
public binary that an independent user benchmarked all the way back to the prize
score. That missing source is why, of the three community engines studied in this
lab, his is the one that cannot be run at all; the last section here says exactly
why.
Verhaard's own origin story is disarming. His first high-score program only
placed perfectly matching pieces, and stalled around a 450: hundreds of
248-piece clean partials, no way forward. Only when he tried Bob Cousins'
(originally Dave Clark's) solver, which found a 458 within a minute, did he grasp
that the contest scored matching edges, so half-fitting placements count
(groups.io message 5767). He had, in
his own telling, never bothered to read the rules; Jef Bucas was still pointing
readers at that admission in Verhaard's documentation in 2021
(groups.io message 10582).
Through the summer of 2008 the community's publicly visible ceiling was 463
(groups.io message 5688), and in a
remarkable exchange Verhaard and Max compared notes as the only two known to be
past what they called the "don't-talk-about-limit"
(messages 5767–5787). Then, on 22
September 2008, with the first scrutiny date three months away, Verhaard
published the solver for anyone to run at fingerboys.se: "This because I am stuck
and my only hope to improve my best score is by using brute force"
(message 5940). The terms mirrored
eternity2.net's: you needed to own the real puzzle, and any prize would be split
50-50 between the best-scoring user and Verhaard. The community became his compute
farm.
It worked. On 6 January 2009 he released a decoder for the solver's .eii output
files, documented the internals (heuristics and search order), and disclosed the
number the farm had reached: 467, found more than 40 times by different users
(message 6275). Nine days later,
Tomy's announcement surfaced: no complete solution, and a $10,000 runner-up prize
to Anna Karlsson of Lund for 467 of 480
(message 6337). The list took about
an hour to decode "Lund + 467". The rest of the contest story belongs to
the history page: the silence from Tomy, the press
coverage, the aftermath. What follows here is the machine.
The base loop is a depth-first backtracker over a fixed
fill order, but one that prunes
forward: branches whose heuristic score falls below a threshold are cut before
they are explored. Verhaard described his thresholds as static and hand-tuned:
"mostly based on pure guesswork and only on limited amount on theory or
measurements," slow to tune but predictable over long runs
(groups.io message 5771, quoted back
at him in message 5772).
What are the thresholds for? The design he and Max converged on in that exchange
is the interesting part: you can only influence piece selection early in the
search, but what you want to maximize is the tileability of the remaining
pieces deep in the fill, around pieces 160–200, where the branching factor
collapses toward forced moves. So the early thresholds are tuned, semi-manually,
to answer: which heuristic score must early partials reach so that the survivors
carry a leftover piece set that still tiles well? Verhaard's verdict on Max's
description: "I think we work in a very similar way after all"
(message 5780).
How do you know a heuristic is strong? The measure the two settled on (proposed
by Max, adopted by Verhaard) is where the peak of the node-depth distribution
sits. An unheuristic full search on E2 spends most of its time around depth 161,
Brendan Owen's baseline figure
(message 6112); both of their
heuristic searches had pushed the peak to just under 170
(message 5780). Max supplied the
interpretation: a peak at 170 is roughly equivalent to eliminating one interior
colour from the puzzle entirely; a "killer heuristic" that eliminates two seemed
out of reach (message 5787).
A full-solution search wants a row-by-row scan; a high-score search lives deeper
in the board, and wants a different frontier. When Brendan Owen posed exactly
that question, Verhaard revealed the shape of his answer: the best orders he had
found resemble a comb search (most rows searched horizontally, then the
remaining rows searched vertically), with the tooth length tied to the target:
"The lower the score you aim for, the longer the teeth of the comb become"
(groups.io message 6112). Max had
independently converged on nearly the same geometry (twelve rows of scanline,
then column scan) and reported his scores ran about one edge below "the results
that Louis solver accomplishes"
(message 6126).
The lever that actually bought the 467 is deliberate imperfection. Asked about it
directly a year later, Verhaard was precise: the 467 program searches "normally,"
but at certain depths it allows edge slipping: placing a piece with one
mismatching edge against an already-placed neighbour. It does not first build a
clean partial and then patch holes; the mismatches are budgeted into the
descent, unlocked at chosen depths. And the anatomy of the result is telling:
most of the 467 boards he examined had a clean score of only 247, with thirteen
slipped edges spent where the schedule allowed them
(groups.io message 7321). The 467
was no fluke, either: he found it more than 50 times
(same message).
The technique itself has its own page: why
scheduled mismatches reach boards a clean search never could, and the counting
theory behind the cost of each extra matched edge. What belongs here is the
solver-side machinery: the per-depth mismatch budget is a slip array, one
entry per depth, and it is a tuned object, not a guess.
In January 2009, in the thread where Owen was extending
complex theory to cover slips, Verhaard posted
the outline (with Java snippets) of the algorithm he used to optimize eii's
search order and slip array
(groups.io message 6423). The input
is a candidate search order plus a slip array. For every depth he estimates two
numbers from experimental runs (theory would do to start, he noted): the
probability that a random remaining piece fits perfectly, and the probability
that it fits with one slipped edge. From these he builds a Markov chain whose
state is (depth, slipped edges so far), with transitions for a clean placement
and, where the slip array permits, for a slipped one. Running the chain end to
end yields the probability of reaching the bottom and the expected node count: a
cheap, closed-loop evaluator for any (order, slip-schedule) pair, memoized for
efficiency. He flagged its limit himself: the simple model ignores slip parity,
so it gets unreliable at very high target scores.
The family resemblance to what came a decade later is hard to miss: Blackwood's
break indexes are also a depth-gated mismatch budget, and his quota schedule is
also a pre-committed, per-depth curve, hand-tuned rather than chain-optimized.
The lineage runs through this solver.
The same heuristics powered a second program with a different late-game move:
instead of slipping an edge, it may skip a square, that is, leave a cell empty
and keep going. The name is his own
(message 7321). That is the
clean-score (no mismatches) hunter. With it, Verhaard filled 14 complete rows plus
two pieces, a 226-piece flawless partial and the record he knew of at the time
(groups.io message 6303). In a
one-day return in December 2009, after estimating ~2,000 248s per 249, he landed
three 249s in a row and stopped, putting a 250 at roughly 4,000 times harder
(message 7306). Asked about it a
decade later, he confirmed the 249 on his site is real: about a week of compute on
one machine (message 9890).
Because the binary was public, the 467 is the rare contest-era record with an
independent, quantified reproduction. JSA ran eii continuously on one PC and
logged the score distribution as it accumulated:
- 43 days: 2,008,484 463s · 109,195 464s · 6,048 465s · 250 466s · nothing
higher (groups.io message 6571)
- 62 days: 427 466s, arriving at roughly 5–6 per day, and still no 467
(message 6653)
- 82 days: two 467s, alongside 4,017,182 463s · 227,245 464s · 13,637 465s ·
625 466s (message 6687)
That last log is the cleanest public measurement of the exponential rarity ladder
near the top: four million 463s for every couple of 467s, and a 466→467 step that
took a single machine nearly three months. JSA's sign-off, "Congratulations to
Louis on a well-thought-out algorithm", doubles as the verification verdict.
Beyond the score, eii set a precedent: when you are stuck, release the solver and
let the community's machines hunt, with the prize split as the contract. The 467
was found by users of a published binary, 40+ times, before it won anything.
Twelve years later
Joshua Blackwood repeated the pattern,
posting a 468 and open-sourcing the engine days later, and got the same reward: a
wave of community records on his own algorithm. The other lesson is methodological
and runs through this whole page: Verhaard tuned his solver against models
rather than raw vibes (the node-peak dashboard, the Markov-chain evaluator), at a
time when that discipline was rare.
The original home, fingerboys.se, was his band's website; when the band gave up
maintaining the site, the solver went offline with it for months. In January 2010
Verhaard republished it, unchanged, at
shortestpath.se/eii
(groups.io message 7439); that
address is still its home, and the first-party source behind the 467 row in
the records table. One operational footnote from the Q&A that
followed: the solver keeps no memory of past positions, so its thousands of
463–465 boards are not deduplicated
(message 7451).
What "the code lives there" hides is that no source lives anywhere. What
Verhaard shipped is eii-1.0-win32.zip: a Windows eii.exe, a readme, and some
.bat files. There are zero source files, and it is Win32 only. It does not
run on Apple silicon, and there is no Windows or emulation layer on this machine to
run it under. His artifact is, here, unrunnable, and there is nothing of his to
fetch and build. The comb-search fill orders and depth-gated slip schedule
described above became community canon precisely because they were recovered from
his posts and, where numeric, byte-exact from the strings inside eii.exe, since
that binary is the only surviving record of them.
So "running Verhaard" at all means rebuilding his method from that documentation.
That is what the
Verhaard reimplementation
does, and on the real five-clue puzzle it reaches 438 of 480, single core. That
engine is filed here beside this page, bylined to Raphaël, because it is a reading
of Verhaard's method rewritten as Raphaël's code. Naming that distinction is part of the
finding: of the three community engines studied here, his is the one that cannot
be run at all.