# The Knight's Romp

Recently I was messing around with a singular knight on a chess board, and I came up with an interesting dilemma.

Can you move a knight, from starting on any square, such that its path covers every square exactly once?

Below is the best pathing I could get, but it misses out three of the squares.

I can't figure out any reason why it would be impossible, but at the same time I can't find a viable solution. The question is: can you either find a path where the knight completes its quest, or prove why this puzzle is impossible?

Happy puzzling!

EDIT: The knight is able to move either: a) one square in any direction, then two squares in a perpendicular direction, or b) two squares in any direction, then one square in a perpendicular direction.

Basically as long as it makes the traditional L-shape that knights are known to move in.

• @RossMillikan For those (like myself) who didn't immediately see why this isn't a Knight's Tour, in this puzzle, the knight does not "jump" -- it is considered to have visited the intermediate squares. (Look at the illustration again. It is nothing like a Knight's Tour.) Mar 29, 2021 at 13:10

First things first: let's check the divisibility.

There are 64 squares, and the knight is standing in one of them. That leaves 63 squares to cover, and each move covers 3 squares, so that seems to work out. That means, however, that we won't be able to create a closed loop, so every solution we find only solves the puzzle for the starting point and, by reversing, the end point. (And the symmetrical counterparts of each all around the board.)

Then, let's see if we can find a path starting from some square. Choosing a starting point so that we can put one knight's move nicely in a corner (it feels like corners and nooks are going to be the most difficult to cover), it turns out that it's

not all that difficult to find at least one solution:

This should convince us that there are no general proofs to the contrary, so now we just need to find an opposite case, or a handful of cases with the same result. (We are not going to need much more than that, because of the board's symmetry.)

That is, however, a lot trickier than it seems, every heuristic seems to have its exceptions, so I'm posting this as a partial answer, and will get back to it after lunch. (If anyone wants to continue from here, please do.)

EDIT:

Here are two more of the similar kind:

So we are at least halfway there:

From all these points we know a solution does exist.

With Jaap's generous help, these were also found workable:

So we've managed to narrow the problem down quite a bit:

If there is a square from which it is impossible to start the "romp", it is either a corner square, or a square a king's move away from the corner.

Usually, after this much fiddling, some pretty solid heuristics have emerged, but that's not the case here. If there's some clever logic that applies, it'll be on the order of "parities of parities don't match" or "every move is to another 2x2 square", but I'm not seeing any use for either of those, either. So my next approach would be a brute force search, which I'll have to leave for someone else to implement.

• Glancing through the solutions my program spat out, it looks like the start and end squares are almost always adjacent, and in the few other cases they are 3 squares apart (knights move or 3 vertically/horizontally), never further than that. Mar 27, 2021 at 9:22
• @JaapScherphuis That's almost something I was hoping to find. I was trying to prove that the path cannot start at b2, this helps a lot but doesn't quite clinch it. (By the way, do you happen to have any solutions with an endpoint at the square diagonally adjacent to a corner?)
– Bass
Mar 27, 2021 at 9:30
• I don't see any that use the 2x2 corner squares, but D2/F3 is possible as is C4/E5. Mar 27, 2021 at 10:08

I have a computer program for solving packing problems, and found a way to use it to solve this problem. One of the solutions it found is below:

Note that this is very close to the attempted solution in the question, as it differs only in the top left quadrant.

Modelling the problem in this way will not find all solutions (I'd need to allow other tile shapes as well), and will also find non-solutions (containing one or more closed loops of moves).

• What a brilliant approach!
– Bass
Mar 27, 2021 at 9:08
• Are you able to name the computer program, or a link to it's repository? It must be very interesting! Mar 28, 2021 at 5:28
• @stevec You can find the Polyform Puzzle Solver on my puzzle website here. Mar 28, 2021 at 21:18