The Knight's Tour With Fewest Crossings: Agents Narrow the Gap

In my knight's tour post, the crossings result was the weak one. Our tours had 12n + O(1) crossings on an n x n board, and the best lower bound was about 4n. Here's the paper.

In the turns post, I described how a team of AI agents closed the gap for turns. The same team also worked on crossings, and moved both bounds:

• Lower bound (tentative - not human-reviewed): For every even n >= 32, every closed tour has at least 5n - 597 crossings.
• Upper bound: There are closed tours with at most 19n/3 + 142 crossings, about 6.33n, for every even n >= 96.

The ratio between the bounds went from about 3 to 19/15, about 1.27.

This post explains the new tours and the new lower bound argument found by the agents.

Recap

A closed knight's tour visits every cell of the board once and returns to the start:

A crossing is a pair of moves of the tour whose segments cross.

The idea from the paper is to imagine a 2x2 "formation" of four knights moving together, because such a formation can move leaving no gaps in between:

The formation covers the board along long diagonals:

Parallel lines never cross, so the inside of the board has no crossings at all. All of them are near the sides, where the formation turns around:

• 2.5 crossings per row on the left and right sides.
• 4 crossings per column on average on each of the top and bottom sides.

Parker Williams later reduced the crossings per column to 3.5 (see below). Across the four edges, this gave a total of 2.5n + 2.5n + 3.5n + 3.5n = 12n crossings, plus some constant. Later, Shisheng Li brought it down to 11.5n.

The paper's lower bound of 4n - O(1) comes from a case analysis of the moves next to each side: each side has about one crossing per row or column.

The new bounds

This is what the new tours look like:

The main original idea by the agents is the addition of turns along the two main diagonals and two middle lines. This is to ensure that the paths always approach the edges at a steep angle, which turns out to be better than when paths approach at a shallow angle. Our knight-formation-based approach, which is completely disregraded in the agent's solution, approached two sides at steep angles and two at shallow angles.

The interactive demo shows the tour of each step in the progress chart above.

The upper bound

Better heels: from 12n to 7.15n

The top and bottom sides had the most crossings, so the first improvements focused on them. We call the transition of the 2x2 knight formation from one group of four diagonals to the next along the bottom side a "heel" because of the shoe-like shape. Here's one expanded out:

Progress came from iteratively relaxing the strict 2x2 knight formation.

1. 12n: Parker's heels, optimized for crossings, have 28 crossings per 8 columns, or 3.5 per column. The four knights stay inside their heel's 8x4 box:

2. 11.5n: Shisheng Li replaced every five adjacent heels with a single 40-column template that keeps the formation but has 10 fewer crossings: 130 per 40 columns, or 3.25 per column:

3. 9n: The first AI improvement removed the walls between heels: each heel can overlap with the next, indefinitely, whereas Li's approach only allowed overlap in groups of five. The four incoming diagonals still go out on the next four diagonals, but in a different order, and the corners join everything back into a single cycle. This heel has 16 crossings per 8 columns, or 2 per column:

4. 7.15n: The second AI improvement dropped the 2x2 formation entirely. It used a different repeating pattern on each of the four sides, and then verified that the corners can be wired correctly. Click here to see what it looks like.

But the bigger step came from a different layout: folds.

Folds

The new layout splits the board into 8 triangles. Each triangle is covered by straight parallel lines, in one of the four directions of knight moves. Here's a starting point, which is not yet a full tour:

Where two triangles meet, the lines bounce off the boundary, like a fold in a sheet of paper, so they don't cross:

So, the inside of the board has no crossings. All the crossings come from completing this layout into one tour.

The sides: 1 crossing per row or column

At each side, when knights come in at a steep angle, the cheapest way to turn knights around costs 1 crossing per row:

That is n per side, so 4n in total, which matches the paper's lower bound of about one crossing per row at each side. If nothing else went wrong, we'd have tours with 4n + O(1) crossings.

But two things go wrong.

Trapped loops (+n)

Near the middle of each side, the lines come in, bounce off a fold, and come back out to the same side. With the cheap U-turns, they close into many small loops instead of one big tour (left).

The fix is to flip the U-turn pattern on a quarter of each side (right, shaded). Then the former loops join into one path, drawn in blue for the part that fits in the picture:

The flipped pattern costs 2 crossings per row instead of 1. That is n/4 extra crossings per side, so +n in total.¹

The corner imbalance (+4n/3)

The second thing that goes wrong is subtler.

Take a square region of any size at a corner of the board, and freeze everything outside it: the cheap U-turns at the sides and the straight lines. Each cell inside the region still needs some moves: 2, minus the moves already coming in from outside. Every move inside the region joins a black cell and a white cell. So the region can only be completed if its black cells, together, need exactly as many moves as its white cells.

For example, here is the 6 x 6 region at the bottom-left corner, with the number of moves each cell still needs. The black cells need 28 moves in total, and the white cells need 29. They don't match, so the region can't be completed.

The cheap tweaks don't fix this. For example, shifting the diagonal fold by one line changes three cells, and the totals become 29 for black and 27 for white. The difference jumped by 3, from -1 to +2. Tweaks like this change it by 3 at a time, so it never reaches 0:

Making the square region bigger doesn't help either. For example, on a 96 x 96 board, every square at the corner, from 5 x 5 up to 40 x 40, comes out off by one.

So every corner square needs a change: some move crossing its boundary has to be different. The squares are nested, so each one needs its own change, all the way out until the mismatch can cancel with the other corners' at the center. The cheapest place we found to make these changes is along the diagonal fold, with a jog of the lines that costs about 2 crossings every 3 columns:

That is 2/3 of a crossing per column. Four corridors, each about n/2 columns long, add 4n/3 crossings.

The total: 19n/3

That is 4n + n + 4n/3 = 19n/3, plus a constant from the corners and the center. The corners, the center, the side midpoints, and the ends of the flipped quarters are filled in by a computer search, which optimizes for minimum crossings. This is done once for each even board size from 96 to 118, and larger boards reuse the same pieces.

For example, here is the 96 x 96 tour, with 720 crossings in red:

The formula gives 19 * 96 / 3 = 608, and the constant adds 112 more.

Ensuring it's a single tour

For every even n >= 96, the construction gives each cell two distinct legal neighbors, and the choices are reciprocal. This gives cycles covering the board. We must also show that there is only one cycle.

For each even n from 96 to 118, a computer search finds pieces that close the layout into a single tour. Copying those pieces gives the tours for larger boards, and a computer check confirms that they are single cycles for every even n up to 166.

For larger boards, the argument is that growing the board by 24 does not change how things connect:

Going from n to n + 24 inserts two more copies of each of eight blocks: one block near each corner and one on each side.

A block consists of 6 consecutive lines, each bent at a fold, and the pieces at both ends of those lines. Its paths meet the rest of the tour through a few "ports". Some paths cross the block, and some come back out on the same side.

A computer check validated that two copies of a corner block, glued end to end, connect their outer ports exactly like one copy, without closing a loop in the middle.

The side blocks behave differently: each copy shifts its four paths by one position. So, every +24 switches the connection pattern between two states, and +48 brings back the first one. A computer check confirmed that both states give a single cycle (details in the full proofs).²

The 4n lower bound

The agents first found a new, short proof of the paper's 4n bound, using area. Then they refined the same argument to 5n.

Put the cells at the points of a grid. Each knight move is then the long diagonal of a small parallelogram, whose short diagonal is the unit grid edge with the same midpoint. Call this parallelogram the move's tile. Every tile has area exactly 1.

If we cut each unit square of the grid along both of its diagonals, we get four quarter triangles. Every tile is made of exactly four of them:

Two tiles overlap exactly when their moves cross, and they share either one or two quarters:

A tour on an n x n board has n^2 moves, so the tiles have a total area of n^2. But they all fit in the square spanned by the cells, which only has area (n - 1)^2. That leaves 2n - 1 of tile area that must go into overlaps. Each crossing accounts for at most 1/2 of overlap, so there are at least 4n - 2 crossings.

This bound was checked in Lean.

The 5n lower bound (tentative)

The 4n proof only uses the total area of the tiles. The 5n proof also looks at how well they cover the board, and shows that near every corner they can't cover it perfectly. It has four steps:

1. Imperfect covering costs extra crossings.
2. A charge, measured along a path, detects imperfect covering.
3. About 2n separate paths around the corners must have a charge.
4. The tour can't avoid this cheaply at the sides.

Step 1: bad quarters cost extra crossings

Call a quarter bad if it isn't covered exactly once: either no tile covers it, or several do. Here are the quarters near the corner of a real tour, colored blue if covered exactly once, red if covered more than once, and white if not covered:

The long straight lines inside the board tile it perfectly. All the trouble is at the sides.

The 4n bound is exact only if the overlap is perfectly efficient: no holes, no quarter covered three or more times, and every crossing overlapping in two quarters. The sides already need about one crossing per row, about 4n in total, and their overlap is enough on its own. So any other bad quarter is waste: a hole, a quarter covered too many times, or overlap from a crossing that the sides didn't need. A careful count turns this into:

crossings >= 4n - 1 + (bad quarters) / 4 + (side crossings beyond one per row) / 2

So each bad quarter costs at least 1/4 of an extra crossing, and each extra crossing at the sides counts at least 1/2. The one exception is a quarter covered twice by a single side crossing whose tiles share two quarters. That overlap is the side crossings' own, so it doesn't count as bad.

Bad quarters also come in pairs. Within each unit square, a tile always covers two neighboring quarters: one of the top and bottom quarters, and one of the left and right quarters. So the top and bottom quarters together are covered exactly as many times as the left and right quarters together, and a square with a bad quarter has at least two:

So a square with bad quarters costs at least half an extra crossing.

Step 2: a charge that detects bad quarters

To force bad quarters, the agents used the same black and white balance as in the corner imbalance of the upper bound. There, we froze everything outside a corner region and found that the black cells and the white cells inside couldn't be matched. Here, the tour is arbitrary, so nothing is frozen. Instead, the balance is measured along a path.

Color the cells like a chessboard, and orient every move from its black end to its white end. Do the same for the unit grid edges between neighboring cells, which also join a black and a white cell. Now take a path through the centers of the grid squares. Its charge is the number of moves and grid edges that cross it from left to right, minus the number that cross it from right to left, modulo 3.

Two facts make the charge useful:

• Around a closed loop, the charge is 0. Every cell has 2 moves and 4 grid edges. For the cells inside the loop, all 6 point out of each black cell and into each white cell, and the ones between two inside cells cancel. So the charge around the loop is 6 x (black cells - white cells), which is 0 modulo 3. This is the same black and white balance as in the corner region.
• A step between two well-covered quarters adds 0. Each step of the path, from one square to the next, crosses one grid edge, and passes through the two quarters on either side of it. A computer-checked identity says that the step adds m1 + m2 + 1, up to sign, modulo 3, where m1 and m2 are the numbers of tiles that cover those two quarters. If both are covered exactly once, that is 3, which is 0 modulo 3. The grid edges and the modulo 3 are there to make this true.

So, if a path has a nonzero charge, at least one of its steps passes through a bad quarter.

Step 3: about 2n charged paths around the corners

Take a box at a corner of the board, and a path that goes up the right side of the box and then left along its top:

Close the path into a loop around the box. The rest of the loop runs just outside the two sides of the board, where only grid edges cross it, so its charge is easy to compute. The exceptions are the two short pieces at its ends, which depend on a few moves in the two end rows next to the sides. If both end rows are normal, the rest of the loop has charge 1. The whole loop has charge 0, so the path has charge -1, which is 2 modulo 3. So the path must pass through a bad quarter.

The cheap side pattern, with one crossing per row, is normal. (The exact test is in the full proofs.)

Here is how this looks in the 96 x 96 fold tour. Every corner path, from size 12 to 44, finds its bad quarters where it crosses the corridor along the diagonal fold:

This is the corner imbalance of the upper bound, seen from the other side. All the paths at a corner cross its diagonal, so one corridor serves all of them.

The agents used boxes of every size from 12 up to about n/2, at all four corners:

The paths don't touch, and there are 2n - 60 of them. If all of them are charged, each one has its own square with at least two bad quarters. By Step 1, that's half an extra crossing per path, so n extra crossings on top of 4n.

Step 4: abnormal rows don't help

A tour can avoid paying for a path by making one of its end rows abnormal. A row is abnormal if its moves fail the test from Step 3, or if a side crossing there overlaps in two quarters where the path ends. Those quarters don't count as bad (Step 1), so the path couldn't use them. Either way, the path is dropped.

But abnormal rows cost crossings too. A computer check goes through every possible pattern of moves in the four columns next to a side, row by row, as a finite-state machine with 3,136 states. It shows that each side has at least one crossing per row, plus one more for each abnormal row, minus a constant:

By Step 1, each of these extra side crossings counts at least half a crossing, which is what the dropped path would have cost. Each row is an end row of at most one path. So every corner path pays half a crossing either way: through its bad quarters, or through its abnormal end row.

Keeping track of the constants gives 5n - 597. The details are in the full proofs, which call abnormal rows strong.

The fold tours pay about 2/3 of a crossing per corner path in their corridors, where the proof asks for 1/2. And the trapped loops (+n) have no counterpart in the proof. Together, that is the gap between 5n and 19n/3.

Open questions

The factor on n in the minimum number of crossings remains open, somewhere between 5 and 19/3.

A significant effort went into attempting to close the gap, but neither direction budged. At this point, it seems prudent to wait for better models before trying again.

Agent Team Orchestration Via Isomux

The setup is described in the turns post: one room in Isomux, a Chief Researcher agent that spawned its own team, and one kickoff prompt.

These are the ones that mattered for crossings:

• Edge Searcher searched for heels and side pieces with the fewest crossings, using a constraint solver (CP-SAT, from Google's OR-Tools).
• Structures designed the fold layout and worked out how the corner imbalance flows to the center.
• Lower Bounds worked on the lower bound: the charge, the side strips, and their computer checks.
• Turns Theory wrote the proofs, and later the shorter proof of 5n.
• Integrator turned all of this into full tours, and built the interactive demo.
• Verifier rebuilt every result with its own code and audited every claim. As with turns, a claim counted only after the Verifier audited it.
• Lean wrote the Lean proof of 4n - 2.

At subscription prices, the whole thing costed less than $20.

Timeline

The agents were not working continuously through the entire period.

• October 1, 4:06 pm: Work started.
• October 1, 4:59 pm: Upper bound lowered to 9n.
• October 1, 6:55 pm: Upper bound lowered to 7.15n.
• October 1, 8:31 pm: Upper bound lowered to 19n/3 ≈ 6.33n, with the fold layout.
• October 1, 9:26 pm: First lower bound above 4n: 4.0001n.
• October 2, 12:21 am: Lower bound raised to 14n/3 ≈ 4.67n, after six intermediate steps.
• October 2, 8:36 pm to 10:11 pm: Lower bound raised to 4.73n, 4.74n and 4.8n.
• October 3, 2:50 am: Lower bound raised to 5n.
• October 3, 11:40 am: A shorter proof of the lower bound, with a better constant: 5n - 597.

Conclusions

I want to remark that the agents did not follow our preexisting methods, but rather invented new ones entirely. In fact, for the 4n lower bound, they were not content with the fact that we already proved it - they came up with a nicer proof themselves. The tiling, the area-based bounds, the folds, the black and white parity analysis - it's all new, clever, and creative.

The complete proofs are in the MinCrossingsKnightsTour repository.

Footnotes

1. In every variant of the fold layout that the agents built and checked, fixing the trapped loops cost about n or more. That is an observation, not a theorem. A different layout could do better. ↩

2. Growing the board by 12 instead of 24 does not work: it gives the other rotations, and for example at n = 112 it gives three cycles. ↩