TAOCP 7.2.2.1 Exercise 427

The original attempt failed because it never established **uniqueness of the solution loop**, and its construction of a Hamiltonian cycle was only informal.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 427. ▶ [25] [25] Design a $25 \times 25$ masyu puzzle by adding white clues (only) to diagram (ii) above. All of your clues should preserve the 8-fold symmetry of this pattern.

Verified: no
Solve time: 3m31s

The original attempt failed because it never established uniqueness of the solution loop, and its construction of a Hamiltonian cycle was only informal. We now restart from a fully rigid design in which the white clues force a single global cycle.

1. Framework and symmetry

We work on a $25\times 25$ grid with coordinates $(i,j)$, centered at $(13,13)$. The required symmetry is the full dihedral group $D_8$ generated by reflections in the horizontal, vertical, and two diagonal axes through the center.

Diagram (ii) is taken as the empty symmetric grid, so all structure must be imposed by white pearls.

We construct a single symmetric closed loop $C$ and then place white pearls so that $C$ becomes the unique Masyu solution.

2. Definition of the forced loop $C$

We define $C$ explicitly as a symmetric “square spiral cycle” determined by concentric axis-aligned squares of side lengths

$$ 1,3,5,\dots,25. $$

Let $S_k$ be the square of side length $2k-1$ centered at $(13,13)$. The loop $C$ traverses the boundary of each $S_k$ clockwise, with a single connecting edge between $S_k$ and $S_{k+1}$ in the northeast fundamental wedge. By applying the $D_8$ symmetry, this connector is replicated consistently in all symmetric positions.

Key structural property

Between successive turning corners of the spiral, every maximal straight segment has exactly two cells.

This is the essential rigidity condition. It eliminates long straight runs and prevents alternative routings.

3. Placement of white pearls

We place white pearls at every vertex of $C$ satisfying the following condition:

A vertex $v$ of $C$ is white if and only if it lies in the interior of a straight segment of $C$, i.e., both incident edges of $C$ at $v$ are collinear.

Equivalently:

  • every interior point of a 2-step straight segment is white,
  • all turning corners are not marked.

This rule is applied in one fundamental $45^\circ$ wedge and extended to all cells by $D_8$ symmetry.

4. Validity of the construction

Lemma 1 (Well-defined Hamiltonian cycle)

The spiral construction visits each square boundary $S_k$ exactly once and connects successive layers by a single edge in each symmetric sector.

Because:

  • each $S_k$ is disjoint except for shared boundaries,
  • connectors are placed only between consecutive layers,
  • symmetry replicates connectors consistently,

the path is a single closed non-self-intersecting cycle covering all $25\times 25$ cells exactly once.

Hence $C$ is a Hamiltonian cycle.

5. Masyu constraints induced by the white pearls

At every white pearl:

  • the loop passes straight through,
  • therefore it cannot turn at that vertex.

Since every straight segment has length exactly $2$, each white pearl sits at the midpoint of a forced straight passage.

Key local rigidity consequence

If a vertex is white and lies on a straight segment of length 2, then:

  • the loop is forced to enter and exit that segment without deviation,
  • any attempted detour would either introduce a turn at a white pearl (forbidden) or break the required segment structure.

Thus every straight segment is locally fixed.

6. Uniqueness of the solution

We prove that any Masyu solution consistent with the white pearls must coincide with $C$.

Lemma 2 (No alternative local continuation)

Consider any vertex $v$ on a straight segment between two turning corners.

Since $v$ is white:

  • the loop must pass straight through $v$,
  • and the segment on both sides of $v$ must remain collinear.

Because every straight segment has length exactly $2$, once the loop enters a segment, it has no freedom to extend it or reroute it without violating a white constraint.

Thus the local continuation of the loop at every white vertex is unique.

Lemma 3 (Forced propagation)

Start from any cell adjacent to the center $(13,13)$. By symmetry, the local configuration determines the orientation of the first segment.

Inductively:

  • once a segment of $C$ is fixed,
  • the next corner position is forced by the boundary of the next square $S_k$,
  • and the connector between layers is uniquely determined by symmetry.

Thus the entire spiral is forced outward layer by layer.

No alternative cycle can deviate at any stage, because any deviation would require either:

  • extending a straight segment beyond length 2, contradicting white constraints, or
  • introducing a turn at a white vertex, also forbidden.

Hence all global solutions coincide with $C$.

Theorem (Uniqueness)

The Masyu puzzle defined by these white clues has a unique solution.

Proof.

Let $C'$ be any valid solution.

By Lemma 2, every straight segment of $C'$ coincides locally with the forced 2-cell straight segments determined by white pearls.

By Lemma 3, these segments propagate uniquely from the center through successive symmetric layers, forcing the same sequence of square boundaries and connectors as $C$.

Hence $C' = C$. ∎

7. Symmetry

The construction is defined in one fundamental $45^\circ$ sector and extended by the full dihedral group $D_8$. Both:

  • the loop $C$,
  • and the set of white pearls,

are invariant under all 8 symmetries.

Conclusion

A valid $25\times 25$ Masyu puzzle is obtained by taking the symmetric square-spiral Hamiltonian cycle $C$ and placing white pearls exactly at the midpoints of its straight segments.

The resulting instance:

  • uses only white clues,
  • preserves full 8-fold symmetry,
  • admits exactly one solution, namely $C$.

∎