Knight Transposition Puzzle

A friend sent me this puzzle, and it was a neat little solution! I shared it with the community discord, and then @dreev encouraged me to post it here. Enjoy!

1 Like

Nice puzzle! The shortest solution I have come up with so far is 40 moves.


I’ve just revisted my (42-move) solution to match your 40 moves, @byorgey—I had two moves that achieved absolutely nothing! Also, here’s a lichess board with the starting position, with the unavailable spots taken up by rooks, for people who want to wiggle the knights around but don’t have a physical board. No capturing!

I was curious if I could actually get a solution in PGN from that starting position, correctly alternating sides, and I think it’s not possible, although I certainly don’t have a proof. For bonus points: either find a solution that alternates sides every move, or prove that it’s not possible.

My intuition that it’s not possible is b3 is the only square from which a knight can get to three other squares, so it’s the only “crossover” point where black and white knights can change relative positions. But—and here’s the fuzzy bit—I can’t find any solution approach that doesn’t have, in its middle, a black knight on b4, white knights on a1 and c2, and a black knight that wants to cross through b3 from d2 to get to c1, but by doing so, white has no moves. “I can’t think of something” isn’t much in the way of proof, though.

1 Like

I agree that it’s not possible to do it with alternating moves, and I think I have a proof.

If we think of the board in graph theory terms, where each cell is a vertex and there is an edge between every pair of cells separated by a knight move, we can see that the board consists of a linear chain of length 9, except that there is also one extra edge sprouting off in the middle, connected to the fourth cell in the chain.

So the knights are in a particular permutation along the chain, and as @rperce pointed out, the only way to change the permutation is to put one of the knights into that cell off to the side and then move the others past it. So we start with the permutation W-W-B-B but we need it to be B-B-W-W. So at some point we need to change which color knight is at the rightmost end of the permutation. But the only way to do that is to put one knight in the side cell with the other three in the leftmost cells—to either put the rightmost knight into the side cell, or take the side cell knight out so it is the new rightmost knight, but either way we must at some point have the configuration where the four knights are lined up in the four leftmost cells of the chain. The only way to reach that configuration is for the rightmost knight to move into that fourth spot, but then it is the only knight that can move, so it would have to move twice in a row.


Danger danger—your code block isn’t spoilered—but I think the proof is spot on!

Yeah, I couldn’t figure out a way to hide a code block behind a spoiler…

Maybe just don’t make it a code block — it’ll look unpleasant, but at least it won’t spoil? :confused:

Removed! Can’t even make it a non code block since spoilers can’t have line breaks.

1 Like