Puzzling Asked on July 15, 2021
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.
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
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:
With Jaap's generous help, these were also found workable:
So we've managed to narrow the problem down quite a bit:
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.
Correct answer by Bass on July 15, 2021
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).
Answered by Jaap Scherphuis on July 15, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP