Count anything on an edge-matching board twice, once from each side, and the totals must agree, giving impossibility proofs for the price of one pass. The 479 story shows both the power and the trap: a clean parity claim, true for every interior move, defeated through the sixty border edges nobody scores.
A parity argument is double-entry bookkeeping applied to a game board. Every
edge inside the puzzle has two sides, so anything counted over the whole
board (colour occurrences, matched edges, orientation sums) gets counted
twice, once from each side, and the two ledgers must agree. A state where
they disagree is not merely unpromising; it is impossible, and no search is
needed to prove it. On a puzzle where no move is ever
forced and lookahead is expensive, an
invariant that costs one pass over the board and never lies is worth taking
seriously, as long as you remember which direction it points.
The community's best parity tale starts two weeks after launch. In August
2007, kubzpa argued that a placement with exactly 479 matched edges, one
single mismatch, cannot exist
(msg 1640). The intuition is a
parity flip: disturb any piece and the edges it touches change state
together, so mismatches should come in pairs. psykowally immediately
supplied the constructive companion for 478: take a solved board and rotate
an interior piece whose opposite edges carry equal colours by 180°: exactly
two edges break
(msg 1642).
The argument is correct for every interior move. It fails at the frame. In
January 2009 Louis Verhaard pointed out the leak: the 60 outward-facing grey
edges are unscored, so a border piece whose two ring-facing sides share a
colour can be flipped end-for-end, breaking exactly one scored edge (the
seam edge behind it) while the change on the grey side costs nothing
(msg 6317). One mismatch,
score 479, parity defeated through the edges the scoring convention ignores.
This project checked the claim against the official piece set: 14 border
pieces qualify (computed), so any full solution implies a 479. That is the
version of the story that known facts now
carries.
Verhaard added a bureaucratic punchline: the prize entry form recorded piece
numbers but not rotations, so Tomy's scorer would have read such a board as
a 480.
The lesson generalises. A parity argument is only as strong as the boundary
conditions it accounts for, and Eternity II's scoring rules puncture the
boundary in sixty places.
The three acts fit on one small board. Below is a genuinely solved,
engine-generated framed 8×8: every scored edge matched, and an outward grey
rim the score ignores, exactly like the real puzzle's 60 grey edges (32 of
them at this size). Every claim in the story above is a single click here.
Start solved. All 112 scored edges match, this board's stand-in for
480/480. The grey band is the rim the scoring convention never reads.
Act one: click any unmarked interior piece. A 180° turn swaps the
up/down edges together and the left/right edges together, so scored edges
break in pairs per axis: 0, 2 or 4 at a time, never an odd count. Try as
many as you like; no interior click will ever produce exactly one
mismatch. That is kubzpa's argument, and for interior moves it is
airtight.
Act two: click a sky-ringed interior piece. One opposite pair equal,
the other not: exactly two scored edges break, and the badge reads a
478-class board, psykowally's constructive companion.
Act three: click an emerald-ringed border piece. Its two ring-facing
sides share a colour, so the 180° flip leaves both lateral edges matched.
Only the seam edge behind it breaks (one scored edge) while the
outward change parks on the grey rim (flashed amber), where no scorer
ever looks. One mismatch. 479. Verhaard's refutation, in one click.
Audit the boundary. The counter panel tells you how many pieces of
this draw qualify for each move; on the official set, 14 border pieces
qualify (computed), so any full solution implies a 479. The proof was
correct everywhere the scoring looked; the leak is precisely the edges
it exempted.
A parity or balance check is a single pass over the scored edges:
O(edges)=O(480)on the full board,O(56)for NS-1’s seam,
with a constant so small it is effectively free: 480 edge reads are
microseconds, against search steps counted in billions. That asymmetry of
price is why such checks compose with everything: NS-1 after the border
closes rejects 10–28% of deep dead-ends for 56 reads, the cheapest pruning
this project knows. But the asymmetry of information runs the other way,
and it never softens: a violated invariant is a proof of impossibility, a
satisfied one proves nothing at all. One pass over the edges buys a
certificate that only ever says no. It is worth exactly its price, provided
nobody mistakes it for guidance.
The second family of counting arguments tallies colours rather than
mismatches. Already in August 2007, angwin_uk observed that the border is
built balanced: five border edge types, twelve of each on either side of
every border piece's grey edge
(msg 2073). mjqxxxx
sharpened the point: border pieces sit in a fixed orientation, so each type
must split equally into left-facing and right-facing edges, a strictly
stronger condition than even counts
(msg 2098).
Follow that thought inward and you reach the seam. In any complete solution,
the multiset of colours the border ring presents to the interior must equal
the multiset the interior presents back: every colour handed in is handed
out. That is Hopfer's NS-1 condition, formalised in 2022 and treated at
length on the border balance page: a genuine
necessary condition, cheap to check, and blind to everything that happens
interior-to-interior. Same mathematics, two uses. In 2007 the balance served
to estimate how many border solutions
exist; in 2022 it was turned
around into a pruning certificate.
The 2011 expedition: balance is abundant and buys nothing#
After the contest ended, the list spent the summer of 2011 pushing parity as
far as it would go. Juraj Pivovarov posed the oriented set problem: split
the 256 pieces into checkerboard piles A and B so that every colour's
directional edge counts balance, because knowing either the orientations or
the pile assignment of a solution would make the rest easy
(msg 8898). Peter McGavin
reduced the condition to per-colour sums, left equals right and top equals
bottom (msg 8906). Juraj then
counted the qualifying checkerboard rotation-balanced sets: his first
estimate of roughly 4.5×10485
(msg 8929) drew a "something
must be wrong" from Michael Field
(msg 8930), and the corrected
count settled around 3×10147
(msg 8931). All the while, he
framed the search for even one as a hard instance of PARTITION.
Two results ended the expedition, both worth keeping. John Gilbert ran the
experiment: balanced checkerboard sets can be found one at a time, but
feeding the balance to a backtracker as a constraint makes it stall
faster: each placement now draws on half the candidate pieces, and the
restriction costs more than it prunes
(msg 8913). And Nick, working
with pen and paper while bored on a train
(msg 8960), drove a full
256-piece checkerboard-plus-rotation assignment to within a single edge-flip
of balance (msg 8977); Jason
Jamison verified the global sums under Nick's coding (all tops equal all
bottoms at 2,809, all lefts equal all rights at 2,881) and reported that
the near-balanced set still stalled his backtracker about 19 pieces out of a
corner (msg 8978). Balance is
real, abundant, and buys the search nothing.
Cheap necessary conditions. A parity or balance check costs one pass and
composes with anything: a backtracker, a
local search, a sanity check
on someone else's claimed board. The NS-1 figures above show the going rate.
Certificate asymmetry. Every argument on this page points one way: a
violated invariant says definitely broken, a satisfied one never says
definitely fine. Swap two border pieces and NS-1 stays at zero; balance a
piece set perfectly and the backtracker stalls anyway. Parity prunes; it
does not guide.
A boundary-conditions reflex. The 479 proof was correct everywhere the
prover looked, and wrong because the scoring rules created sixty edges he
did not have to look at. Before trusting any counting argument on this
puzzle, including this project's own, audit what the frame, the scoring
convention, and the unscored grey are quietly exempting. On Eternity II, the
exceptions live at the border, and the border is where the arguments go to
die.