Closed knight's tour — Besa et al.'s algorithm with an interface-preserving heel patch
Your browser does not support HTML5 canvas.
Turns: · Crossings:

Crossing counts for $n = 80, 120, 160, \ldots, 1000$ (step 40)

$n$ $\chi(\text{Gen}(n,n))$
BJMOW $12n$		 $\chi(T_n)$
patched		 saving $\chi(T_n)/n$
809769562011.9500
120145614164011.8000
160193618766011.7250
200241623368011.6800
2402896279610011.6500
2803376325612011.6286
3203856371614011.6125
3604336417616011.6000
4004816463618011.5900
4405296509620011.5818
4805776555622011.5750
5206256601624011.5692
5606736647626011.5643
6007216693628011.5600
6407696739630011.5563
6808176785632011.5529
7208656831634011.5500
7609136877636011.5474
8009616923638011.5450
84010096969640011.5429
880105761015642011.5409
920110561061644011.5391
960115361107646011.5375
1000120161153648011.5360

This page visualises the closed knight's tour produced by BJMOW Algorithm 1 (Besa et al., 2022) in its $12n$ optimised configuration (Section 4.2.2 of the paper, with each $4\times8$ heel using 28 crossings instead of the $32$ of the default Sequence1), optionally patched: groups of five adjacent heels are replaced by a single $4\times40$ SequenceP_40 template found by CP-SAT search.

Toggle the checkbox to switch between the two tours. Coloured rectangles overlaid on the board mark the heel templates used in the current view: green for each $4\times8$ BJMOW optimised heel, and red for each $4\times40$ SequenceP_40 in the patched tour. Each red rectangle replaces exactly five adjacent green rectangles (Fig. below). The edges outside the marked rectangles — the bulk, side bands, and corner templates — are bit-for-bit identical between the two tours.

BJMOW optimised: five adjacent 4×8 heels (12n version) 5 × 28 = 140 crossings replace (CP-SAT found) Patched: one SequenceP_40 template (same 4×40 region) 130 crossings (saving 10 per substitution)

The $4\times40$ SequenceP_40 template was found by constraint-programming search subject to one rule: the cross-boundary edges, boundary endpoints, and internal-path pairing of the $4\times40$ region must exactly match those of five horizontally adjacent BJMOW heels. Because of that, the substitution is interface-preserving, and BJMOW's Hamilton-property proof (their Theorem 2) applies verbatim to the patched tour. The same SequenceP_40 template works for either the default ($32$-crossing) Sequence1 or the optimised ($28$-crossing) heel — their cross-template interface and path-pairing are identical, so $\chi(T_n)/n$ converges to $11.5$ in both cases.

About

The knight's tour problem asks for a cycle through every cell of a rectangular board using only knight moves. BJMOW (Theoretical Computer Science 902, 2022; arXiv:1904.02824) gave the first $O(1)$-constant upper bound on the number of crossings: $\chi(T_n) \le 12n + O(1)$ asymptotically.

This fork uses the optimised BJMOW heel ($28$ crossings per $4\times8$ heel, matching their claimed $12n$ bound) as the baseline, and adds a single-element SequenceP_40 patch in board.js: a $4 \times 40$ pairing-preserving template found by CP-SAT search. It replaces five adjacent $4 \times 8$ heels and preserves the cross-boundary edge interface; BJMOW's Hamilton-property proof (their Theorem 2) therefore applies verbatim to the patched tour. The crossing constant drops asymptotically from $12$ to $11.5$ (or from $13$ to $11.5$ relative to the default Sequence1 heel).

Original demo by Juan Jose Besa Vidal, Timothy Johnson, Nil Mamano, and Martha Osegueda (upstream repo). Source for this fork: github.com/daizisheng/MinCrossingsKnightsTour.