Whirling Knight’s Tours: Solving the Beluhov Conjecture via Farkas Certificates

TL;DR

In a masterclass of combinatorial geometry and optimization, Shisheng Li has proven the nonexistence of specific Whirling Knight's Tours. By utilizing Linear Programming (LP) relaxations and Farkas' Lemma, the paper demonstrates that for board sizes $n\equiv 4,6(\mathrm{mod}8)$, a tournament with exactly $n/2$ "coils" is mathematically impossible. This settles a conjecture proposed by Nikolay Beluhov.

Context: What is a Whirling Knight?

A standard Knight's Tour is a sequence of moves where a knight visits every square on an $nimesn$ board exactly once and returns to the start. A Whirling Tour adds a directional constraint: every move must be counter-clockwise (CCW) relative to the board's center.

The coil count ($c$) is essentially the "winding number" of this path—the number of times the tour revolves around the center. Previous research found that for most boards, $n/2\le c\le n$. However, a mysterious gap appeared: no one could find a tour with $c=n/2$ when $n$ was 4 or 6 plus a multiple of 8.

The Core Insight: From Arcs to Linear Equations

The author approaches the problem not by trying to draw tours, but by proving they cannot exist. The strategy involves:

1. LP Relaxation: Treating the tour as a flow problem where each cell must have one incoming and one outgoing arc.
2. Farkas' Lemma: A fundamental tool in optimization. To prove a set of linear constraints is infeasible, one must find a "certificate"—a set of weights that, when applied to the equations, leads to a contradiction (e.g., $0>1$).

Methodology: Two Distinct Proofs

The paper provides two different certificates because the geometry of the "failure" changes based on the board size residue.

1. The $n\equiv 6(\mathrm{mod}8)$ Case: Block Inconsistency

For boards like $6imes6$ or $14imes14$, the author identifies blocks of cells flanking the center.

• The Certificate: Assigns $+1$ weights to specific cells near the "north plumb-line" (the ray stretching upwards from the center).
• The Intuition: The author proves that any arc entering or leaving these specific blocks must cross the plumb-line. Mathematically, the total number of required crossings for these blocks exceeds the allowed coil count $c=n/2$.

Figure: The certificate support for n=14. Blue and orange cells represent the weighting strategy that forces a contradiction in the coil count.

2. The $n\equiv 4(\mathrm{mod}8)$ Case: Parity Triangles

For boards like $4imes4$ or $12imes12$, a simple block argument fails. Instead, the author uses a Triangular Support.

• The Certificate: Uses a triangle in the North-East quadrant of the board with alternating $\pm 1$ weights.
• The Intuition: Through a "parity-counting identity," the author shows that the number of cells with odd coordinates in this triangle exceeds the even ones by exactly $2m+1$. This slight imbalance, when plugged into the LP dual, proves that the coil count $c$ cannot be $n/2$.

Figure: α-support of the certificate for n=12. The alternating weights in the triangle are key to the parity proof.

Why This Matters

This paper is a significant contribution to Graph Theory and Discrete Geometry. It moves beyond mere computer searches and provides the "theoretical why" behind observed patterns.

• SOTA Achievement: It completely classifies the existence of $n/2$-coil tours for all even $n$.
• Methodological Rigor: The use of Farkas certificates provides a "closed-form" proof that is checkable by hand, which is much more satisfying than a "proof by computer exhaustion."

Critical Analysis & Conclusion

Takeaway

The nonexistence of these tours isn't a fluke of knight movement but a deep property of how Hamiltonian cycles interact with winding numbers on a discrete grid.

Limitations

The proof is specifically tuned to the $c=n/2$ case. For higher coil counts (approaching $c=n$), different mechanisms likely prevent or allow tours, which remains a fertile ground for future exploration.

Future Work

The author suggests that similar Farkas-based approaches could be used for other "leaper" tours (like those of Camels or Giraffes in fairy chess) or to explore the upper bounds of the coil count.