24
$\begingroup$

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.

61-Square Solution

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.

$\endgroup$
1
  • 2
    $\begingroup$ @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.) $\endgroup$ – tehtmi Mar 29 at 13:10
12
$\begingroup$

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:
enter image description here

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:

enter image description here enter image description here

So we are at least halfway there:

From all these points we know a solution does exist.
enter image description here

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

enter image description here enter image description here

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.
enter image description here

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Jaap Scherphuis Mar 27 at 9:22
  • $\begingroup$ @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?) $\endgroup$ – Bass Mar 27 at 9:30
  • $\begingroup$ I don't see any that use the 2x2 corner squares, but D2/F3 is possible as is C4/E5. $\endgroup$ – Jaap Scherphuis Mar 27 at 10:08
24
$\begingroup$

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:

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.