# 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.

2 Likes

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.

2 Likes

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?

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

1 Like