Statusready
Subboards0 / 64
Unique squares0
Legal moves0
Incrementally constructed tour
locked tilecurrent optimizationinter-tile connector
Optimize one 8×8 subboard at a time, fold the macro path down and back, then constrain the final endpoint to make one legal knight move to the first square.
The macro order crosses the top row, folds through the interior, and returns along the left edge. Every local path must reach a legal connector to the next subboard; the last path must end where it can jump back to the fixed first square.
local uniqueness + legal connectors + fold-back macro cycle + closing move ⇒ global closed tour
This laboratory decomposes an N×N board into 8×8 subboards. It solves one constrained Hamiltonian path per tile, locks that path, and passes only a legal exit–entry knight move to the next tile. The final tile is constrained to reconnect to the fixed start.
Each tile is a subproblem, but its entry and allowed exits are its contract with neighboring tiles. Independent local tours alone do not guarantee a global tour.
COIN learns directed edge weights from rewarded and punished candidates. Warnsdorff supplies a local prior favoring destinations with fewer onward moves. It guides rather than replaces COIN learning.
64 unique cells/tile63 legal local moves+ legal connector+ final closing move
P(next=j | current=i) ∝ W[i,j] / (1 + OnwardDegree(j))⁴
Terminology: the learning option is COIN–Warnsdorff Hybrid. The Warnsdorff baseline uses randomized minimum-onward-degree selection without learning an edge matrix.
Let q=N/8 be the number of subboards per side. A row-by-row snake is an intuitive open path, but its last tile need not be adjacent to its first. A closed construction must reserve a return corridor or search directly for a macro Hamiltonian cycle.
Cross the top, fold through the interior, and reserve a boundary column for returning beside the first tile.
A plain snake cannot simply fold onto its start. This lab searches an 8-neighbor macro graph and may use a diagonal neighboring tile; the exact cells must still differ by a legal (1,2) knight move.
Find a macro Hamiltonian cycle first, then solve each 8×8 tile under its interface. If a seam is unrealizable, backtrack or choose another cycle.
Odd q does not imply that the large board has no closed tour: N=8q remains even. Only the simplest serpentine fold fails. Macro adjacency is also not enough—the cell-to-cell connector must be verified.
Parberry’s divide-and-conquer algorithm recursively builds closed tours in quadrants and splices selected edges, using O(n²) work for an n×n board—linear in the number of cells. Later work shows structured and obfuscated tours up to 2,000×2,000. This lab instead exposes each constrained 8×8 solve and lets a learning COIN model work locally, so students can inspect the boundary contract.