The Knight's Tour With Fewest Turns: Solved by Agents

In my knight's tour post, I described our tours with 9.25n + O(1) turns on an n x n board, and a lower bound of about 6n. Here's the paper.

Recently, I asked a team of AI agents to try to make progress in either direction, and they managed to close the gap:

• Lower bound: For n >= 8, every closed tour has at least 8n - 28 turns.
• Upper bound: There are closed tours with 8n - 14 turns, for every even n >= 48.

So, the gap is now just a constant: between 14 and 28 turns below 8n.

The bounds have likely moved since I wrote this post. As new results come in, they will appear in Results since the post.

This post explains the new tour and lower bound argument found by the agents, as well as how I orchestrated the agents. They also improved the bounds for the fewest crossings, but these results are in a separate post.

Recap

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

A square or "cell" is a turn if the knight changes direction there.

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, so the only turns are along the edges:

Finally, in the corners, the 4 paths are connected into a single cycle.

With this approach, all the turns are near the sides of the board:

• 2 turns per row on the left and right sides.
• 2.75 turns per column on average on each of the top and bottom sides.

Parker Williams later reduced the turns per column to 2.625 (see below). Across the four edges, this gave a total of 2n + 2n + 2.625n + 2.625n = 9.25n turns, plus some constant.

The paper also gave a lower bound of about 6n, meaning that our tour was proven to be within a factor of about 9.25n / 6n ≈ 1.54 of optimal, leaving the actual minimum as an open problem.

The new bounds

AI Agents closed the gap between the lower and upper bounds, up to a constant (personally, in the spirit of asymptotic analysis, I don't care about the exact constant as much):

And this is what the new tours look like:

The interactive demo shows the tour of each step in this research progression chart above.

The lower bound

The 6n lower bound in our paper uses a fairly convoluted argument. In comparison, the agents came up with a shorter, simpler, and more elegant 8n - 64 lower bound using the pigeonhole principle. We'll see that proof first, before we see how they refined it to 8n - 28.

The argument looks at the four columns next to one side of the board, and it shows that they contain at least 2n turns.

Call a move from column 2 or 3 outward if it goes to column 1 or to column 4:

Now we analyze each column:

• In Column 1, every cell is a turn, accounting for n turns.

• In Columns 2 and 3, if the two moves adjacent to a cell are outward, that cell has a turn.

Now, we count how many outward moves go from columns 1 and 4 to columns 2 and 3. Column 1 sends 2n. Column 4 sends some unknown number, B, so the total is 2n + B.

That's 2n + B outward moves going into 2n cells, and each cell can hold at most 2 of those. By the pigeonhole principle, at least B cells hold two. Thus, there are at least B turns in columns 2 and 3.

• A cell in Column 4 with no move back into columns 2-3 has both moves going right, so it is a turn. At most B cells of column 4 have a move back, so at least n - B of them turn.

Adding up: n + B + (n - B) = 2n.

The same holds at all four sides, which gives 8n. The only problem is that the strips overlap at the corners:

Each corner square has 16 cells, so at most 64 turns are counted twice. That gives 8n - 64.

The corners don't really lose 16 turns each. A finer look at a 4 x 4 corner shows that it loses at most 7. That improves the bound to 8n - 28. The details are in the full proofs.

Both bounds, 8n - 64 and 8n - 28, are checked in Lean 4 with Mathlib, a proof assistant. The formal statements use the same definition of a turn as the paper.

The upper bound

The lower bound argument says that each side needs at least 2 turns per row or column, on average.

The left and right sides of the paper's tours already did exactly that:

So, we focused on the top and bottom edges. 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. Parker's optimized heels, with 2.625 turns per column, let the four knights break formation temporarily, but only inside the heel's own 8x4 box. They still enter and leave the heel in the same permutation as the original heel, preserving the integrity of the whole tour.

2. The first AI improvement removed the walls between heels: paths can step into neighboring heels, as long as the four incoming diagonals still go out on the next four diagonals, in any order. The corners then join everything back into a single cycle. This improved the turns to 2.25 per column.

3. The second and final improvement dropped the 2x2 knight formation entirely: the four incoming diagonals don't need to exit as the next four adjacent diagonals. At this point, it's just a repeating pattern every 8 columns:

The sides also change (still 2 turns per row):

The four 6 x 6 corners are solved by a computer search, once for each even value of n mod 8. So there are 4 sets of corners, and each set works for every even board size n >= 48 in its residue class modulo 8.

See the interactive demo for the full tour.

Counting the turns

Outside the corner columns, the bottom counts repeat as 2, 2, 3, 1, 2, 2, 1, 3 (red dots above). This averages to 2. The top uses the same template, just flipped.

Outside of the corner rows, each row has 2 turns on the left side and 2 on the right side.

The four corners have 82 turns in total (it just happens to be the case regardless of n mod 8).

Outside the corners, there are n - 12 columns and n - 12 rows. So the total is 82 + 4(n - 12) + 4(n - 12) = 8n - 14.

Ensuring it's a single tour

For every even n >= 48, 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.

A computer check confirms this directly for every even n from 48 to 102.

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

Going from n to n + 8 inserts one more bottom-left block, left-right block, and right-top block:

A block consists of 8 consecutive diagonal lines 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 block (far away enough from the corners), glued end to end, connect their outer ports exactly like one copy, without closing a loop in the middle.

Open questions

The exact minimum remains open between 8n - 28 and 8n - 14, and it could depend on n mod 8.

The agents claim that the exact minimum is 8n - 20 for n = 14 and 16, and 8n - 21 for n = 18.

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

Results since the post

The agents have kept working on this problem and keep reporting results. I won't cover them in this post, but I'll list them here as they come in. The proofs are in the MinCrossingsKnightsTour repository.

• Upper bound: tours with 8n - 17 turns when n ≡ 2 (mod 8) and 8n - 16 when n ≡ 6 (mod 8) (proof, interactive demo).
• Lower bound: every closed tour has at least 8n - 24 turns, for n >= 20 (proof).

Agent Team Orchestration Via Isomux

I used Isomux for orchestration, because it allows Claude and Codex agents to exist side-by-side and message each other.

I created a room with a single Opus 5.5 agent, Chief Researcher, and set the following room instructions (written by hand). Room instructions are inherited by every agent spawned in this room.

Room for one-off tasks, not related to any of Nil's main projects (Isomux, Wall Game, etc.) but which may require deep computation, exploration, and agent-to-agent communication.

The main workflow is that Nil gives a a prompt to the Chief Researcher, and the Chief Researcher decides by herself how many additional helper agents to spawn, which models to give them, and how to assign tasks to them, as necessary to achieve the mission.

The agents can coordinate by putting findings in files, decided organically by the C.R., by using the taskboard (scoped to this room), or by direct agent-to-agent communication. It's the C.R.'s responsibility to ensure the workers work efficienctly, having the context they need, without interrupting each other too much.

Rules:

- Avoid "Max" thinking effort without Nil's direct approval. Rest are fine.
- C.R. and the workers can use subagents liberally.

Then, this was the prompt to Chief Researcher that kicked it off:

I described a research idea in the email below.
Your task is to pursue it and report back the maximum improvements you can find on either bound.
Feel free to branch out from my specific idea if you see other promising ways of improving the bounds.

[forwarded email thread]

Context:
https://nilmamano.com/blog/knights-tour
https://arxiv.org/pdf/1904.02824

I'm here to answer any questions and assist.

The mentioned "research idea" was a type of heel relaxation that roughly maps to the first improvement found by the agents.

From there, it wrote a shared brief, split the work, and spawned the other agents itself, a mix of Opus and Astra:

I checked in with Chief Researcher from time to time. I'd say I barely steered at all.

I kept it to one room intentionally so it wouldn't burn unbounded tokens. That may have bottlenecked progress.

Each agent had a main job and its own folder for its findings. These are the ones that mattered for turns (others worked on crossings):

• Turns Builder searched for heels with the fewest turns, using a constraint solver (CP-SAT, from Google's OR-Tools).
• Integrator turned heels into full tours. It solved the corners with the same solver. It also checked that the tours repeat when n grows by 8.
• Turns Theory did the lower bound: first the four-column argument, and then the corner certificate.
• Verifier rebuilt every result with its own code, written from the definitions in the paper.
• Lean wrote the Lean proofs of 8n - 64 and, later, 8n - 28.

The agents worked through the night and seemingly had no plans to stop (until I told them I was happy with the final constant gap). They sent each other messages and wrote their results to files. Whenever an agent context got about half full, the agent handed off the work to a new session for itself (something they know they can do via an Isomux server endpoint).

One emergent rule was that a claim counts only after an independent check. The Verifier audited each claim and logged a verdict. Two days in, it had logged 52 numbered claims. Some failed, and the agents then fixed the statement or dropped it.¹

Timeline

• October 1, 4:06 pm: I handed over the email.
• October 1, 5:26 pm: Lower bound raised to 8n - 64.
• October 1, 5:42 pm: Upper bound lowered to 8.5n.
• October 1, 5:43 pm: Lower bound raised to 8n - 28.
• October 1, 6:23 pm: Upper bound lowered to 8n - 14.
• October 1, 7:17 pm: 8n - 64 lower bound checked in Lean, 37 minutes after I asked whether that was possible (I had never proved anything in Lean before).

October 2 and 3 went to crossings, audits, write-ups (where I'm the bottleneck), the interactive demo, and trying to close the constant gap.

Conclusions

I want to remark that, for the lower bound, (1) the agents did not build upon our methods, this was a novel approach, and (2) they did not just throw computation at the problem. They came up with an elegant mathematical argument that's better than any of us could come up with. The upper bound improvements above are similarly original.

The complete proofs, with every definition and every finite check, are in the MinCrossingsKnightsTour repository.

The improvements on the lower and upper bounds for the sibling problem of minimizing crossings, which are in the next post, were even more impressive.

The Opus agents took less than 20% of weekly credits on the $200 plan, with most of it going into the harder problem of minimizing crossings (not counting a subsequent effort to try to close the constant gap). So, I'd say the research in this post took under $5 at subscription prices for the Opus agents.

Put bluntly, agents destroyed humans (or specifically me) at research, at least when it comes to this problem. Cost wise, it's over three orders of magnitude cheaper compared to months of grad student salary.

Want to leave a comment? You can post under the linkedin post or the X post.

Footnotes

1. Here's one example from turns. The Integrator's check that the tours repeat every 8 sizes looked at finitely many sizes. The Verifier did not accept that as a proof for every n. Turns Theory then wrote the block argument that is now in the full proofs, and the Verifier passed it. ↩