Country Road: contract the countries and it is a Hamiltonian cycle — and that is the easy half

Country Road in the browser with five rule sets inside. The grid is
cut into countries; one closed loop visits every country exactly once; a
number says how many of that country's cells the loop uses; and two cells
facing each other across a border may not both be empty. Puzzle #49 in the
solver series.

Demo: https://sen.ltd/portfolio/country-road/
Repo: https://github.com/sen-ltd/country-road

The rules

The grid is cut into countries. Draw one closed loop through cell
centres, orthogonally, never crossing itself. Then:

1. The loop visits every country exactly once.
2. A number in a country says how many of its cells the loop uses. Unnumbered countries are unconstrained.
3. Two orthogonally adjacent cells in different countries may not both be off the loop. (Two empty cells inside one country are fine.)

Contract the countries and this is a Hamiltonian cycle problem

Shrink each country to a single node; join two nodes when their countries share
a border. Rule 1 then says the loop's country order is a cyclic sequence hitting
every node exactly once:

The loop induces a Hamiltonian cycle on the region adjacency graph.

Two consequences, and the whole solver is built around them.

A cut vertex is a proof of impossibility

Every Hamiltonian graph is 2-connected. So a partition whose region graph has
a cut vertex or a bridge admits no solution at all — for any numbers
whatsoever.

The cleanest counterexample is the strip partition. Make every row a country and
the region graph is a path, so everything but the two ends is a cut vertex:

  n×n cut into rows: cut vertex true, Hamiltonian false, solutions 0   (n = 4, 5, 6)

hasCutVertex is Hopcroft–Tarjan, O(V+E), and it rejects the board without
looking at a single number. The brute-force counter, which knows nothing about
graphs, independently returns 0.

"Two border crossings per country" is a 2-factor, not a Hamiltonian cycle

The loop enters a country once and leaves once, so exactly two of its border
edges are used. As a relaxation that is degree-two on every node of the region
graph — a 2-factor — and the gap between a 2-factor and a Hamiltonian cycle
is exactly the subtour that TSP practitioners spend their lives eliminating.

The ladder is that structure, one rung at a time:

rung	what it knows
region	cell-level bookkeeping: an empty cell carries no road, a used edge puts both ends on the road, two empty cells may not face each other across a border, and a number bounds how many cells are used
once	every country exactly once: exactly two border edges used, at least one cell on the road, the same border never crossed twice, and a country's road cells connected inside the country
loop	the loop's own structure: degree two, dead ends, cycles that close too early or skip a country, road cells stranded out of reach
macro	Hamiltonicity of the region graph. Every Hamiltonian cycle is enumerated once per puzzle into a bitmask catalogue; propagating is then set arithmetic — keep the cycles containing every crossed border and avoiding every closed one, then read the union (a border on no cycle dies) and the intersection (a border on every cycle is forced)
probe	singleton consistency, on cells and on edges — a board can have every cell decided and still two ways to thread the road through them

macro is the subtour elimination. Every propagator is sound, so a rung
that finishes a board without guessing is also a proof that the board has
exactly one solution.

What each rung reaches

Share of the board's bits — every cell and every grid edge — decided at the
rung's fixpoint, starting from a board with every country numbered:

size	boards	region	once	loop	macro	probe
6×6	80	14.9%	15.1%	18.3%	30.5%	63.4%
8×8	80	18.1%	18.2%	20.5%	33.4%	77.8%
10×10	40	18.3%	18.4%	19.8%	30.1%	72.8%

Nothing below probe finishes boards to speak of — macro completes 1.3% at
6×6 and 0.0% above it. The shipped bank agrees: the weakest grade it could find
is loop at 6×6, macro at 8×8, probe at 10×10. No board at any size falls
to region or once alone.

Ablation: drop one rung from the full ladder

size	drop	bits lost at the fixpoint	boards moved	probe assumptions
6×6	−region	889	40/40	+31.6%
6×6	−once	71	9/40	+9.4%
6×6	−loop	482	36/40	+28.5%
6×6	−macro	607	32/40	+39.2%
8×8	−region	1240	30/30	+110.9%
8×8	−once	59	10/30	+46.5%
8×8	−loop	458	30/30	+116.8%
8×8	−macro	591	25/30	+57.8%

once is the row worth staring at. It is nearly free at the fixpoint — 59 bits
across 30 boards at 8×8, and it moves only a third of them — and yet removing it
makes the search buy the same facts back at 46.5% more assumptions.
Incremental reach and ablation point in opposite directions about it, so both
get reported.

And then the Hamiltonian cycle turns out to be the easy half

The framing above makes the macro problem sound like the hard part. It is not,
and finding out is one measurement: take the ambiguous boards and ask what the
second solution changes.

size	ambiguous boards	second solution walks the same country order	a different one
6×6	51	92.2%	7.8%
8×8	34	85.3%	14.7%

Nearly all ambiguity is micro: same countries, same order, different cells used
inside them. Which is precisely the job of the numbers — and the numbers mostly
do not do it. With every country numbered, only 18.0% of 6×6 boards and
10.0% of 8×8 boards are unique.

The correlation even runs backwards:

Hamiltonian cycles in the region graph	6×6 boards	unique
exactly 1	28	7.1%
2–4	45	17.8%
5–16	26	30.8%

A board with no macro freedom at all is the least likely to be unique. The
confound is country size: small countries make the region graph dense (many
macro cycles) and leave no room to route inside a country. Turn that dial
directly and the whole effect is size's:

size	avg country	unique	median macro cycles	ladder reach
6×6	2.5	40.0%	7	41.6%
6×6	3.5	20.0%	4	33.3%
6×6	4.5	6.7%	2	27.7%
6×6	6.0	3.3%	1	21.3%
8×8	2.5	18.3%	54	34.6%
8×8	6.0	1.7%	4	22.7%

The partition can be a wall, so don't start from one

Partition-first generation is a trap, and the trap is measurable. Random
partitions, before a single number exists:

size	countries	cut vertex	region graph Hamiltonian	board solvable
6×6	4	13.3%	86.7%	83.3%
6×6	6	11.7%	88.3%	74.2%
6×6	8	4.2%	95.8%	84.2%
6×6	12	0.0%	100.0%	90.0%

Hamiltonicity of the region graph is necessary but not sufficient: the gap
between the last two columns is the micro problem refusing to route.

So the generator runs the other way, and cannot dead-end:

1. Inflate one closed loop. Start from a 2×2 square, repeatedly push an edge out into the neighbouring 2×2 and replace it with a three-edge detour. The result is a single closed circuit by construction — no rejection, no connectivity check.
2. Cut the loop into consecutive arcs. Each arc seeds one country, so the loop already visits every country once and the arc order is a Hamiltonian cycle on the region graph. The macro problem is solved before the board exists.
3. Hand every connected blob of off-loop cells to one country whole — which is exactly rule 3.

Legality is structural. Only uniqueness has to be bought, by erasing numbers for
as long as the ladder still finishes:

size	countries	numbers kept (adversarial)	numbers kept (random erasure)
6×6	6.7	2.9	5.4
8×8	11.3	4.7	10.1

Three engines, and a number from outside the repository

Every board is counted three ways that share only the geometry helpers: a
propagating search, a cells-first brute force (fix the cells, count the
routings), and a loops-first brute force (enumerate every simple cycle of the
grid, read the empty cells off as the complement). They agree on 60/60
boards.

And the whole thing is pinned to a count that exists outside this repo. Give
every cell its own country and rule 1 becomes "visit every cell exactly
once", so a clue-free board has as many solutions as the grid graph has
Hamiltonian cycles — OEIS A003763:

  2×2 singletons: 1      4×4: 6      6×6: 1072
  2×m strips:     1, for every m from 3 to 8

"Finished without search ⇔ unique" is checked against brute force in both
directions on 120 boards: 0 finished-but-ambiguous, 0 unique-but-stalled. 37
tests in all.

One debugging lesson

The bug that cost the most time was in loop's premature-closure test. It
compared the size of a closed component against the number of cells known to
be on the road — and within a single pass an edge can be forced after its
endpoint was last looked at. One cell that is on the road by its edges but still
blank in the cell array makes a finished loop look one cell too long, and a
sound-looking propagator kills the correct solution.

The way it surfaced is the standard harness for this series: every rung's
fixpoint must agree, bit for bit, with every solution brute force returns. If
one propagator is unsound, "finished without search" stops being a uniqueness
proof, and everything built on top of it — the grades, the bank, the ablation
tables — is quietly wrong.

src/country-road.ts   rules, geometry, five rungs, referee, region-graph theorems
src/brute.ts          two brute-force counters sharing nothing but geometry
src/generate.ts       loop-first generation, partitions, clue erosion
tools/stats.mts       every table in this article

---

Demo: https://sen.ltd/portfolio/country-road/
Repo: https://github.com/sen-ltd/country-road