UncleEbenezer wrote:Does anyone else find it mildly unsatisfying that it's not a closed loop, with a knight's move from 100 back to 1?
Yes that would be elegant. I suppose a challenging problem would be to find how many distinct closed-loop paths exist in the 10x10 grid?
Yes, decidedly challenging, and the answer is probably unknown - that's based on OEIS entry A001230
, which indicates that the answer is 0 for all odd-sized boards (easily proved), 0 for the 2x2 board (trivially proved - no knight's moves are possible!), 0 for the 4x4 board (easily proved), 9862 for the 6x6 board (I'd guess that might
be doable by hand, with a lot
of error-prone work, but computer assistance recommended!) and 13267364410532 for the 8x8 board (computer assistance almost certainly required - a PDF link from the OEIS entry
contains a reasonably readable sketch of how the computer enumeration can be done). I would expect the number for the 10x10 board to be hugely greater still - and the fact that the OEIS entry only goes as far as the 8x8 board very likely means that no-one has actually managed to compute it (the alternative is that they've kept quiet enough about having computed it for it not to have come to the attention of the many OEIS contributors, and it seems highly unlikely that anyone would want to keep that quiet about it).
By the way, some things that need clarification about the question are:
* Any particular closed loop has 200 variants created by starting with 1 on any of the 100 squares and following the loop in either of the two possible directions - are they to be counted as different loops or essentially the same loop? The answer if they're counted as different loops will be 200 times the answer if they're counted as essentially the same loop. The OEIS entry counts them as essentially the same loop - it fails to say this explicitly, but I know it because if it counted them as different loops, similar reasoning would say that 9862 would be divisible by 72 and 13267364410532 would be divisible by 128, neither of which is the case.
* Any particular closed loop has up to eight variants (including itself) created by the eight rotations and reflections of the board (including the null rotation by 0 degrees) - again, are they to be counted as different or essentially the same? This doesn't have an easy answer based on neither 9862 nor 13267364410532 being divisible by 8, because it's possible for some of those variants to be the same loop as each other, just with the numbering started at a different place. For instance, for a 6x6 board, the following closed knight's tour:
| 1| 8| 31| 16| 3| 10|
| 30| 15| 2| 9| 24| 17|
| 7| 36| 23| 32| 11| 4|
| 22| 29| 14| 5| 18| 25|
| 35| 6| 27| 20| 33| 12|
| 28| 21| 34| 13| 26| 19|
can be rotated by 90, 180 and 270 degrees to produce essentially the same tour, just numbering the squares starting with 1 in the top right, bottom right and bottom left corners respectively. So it and its three rotated variants become just one after factoring out the 72 possible starting positions and directions according to the first bullet point above, and its 4 reflected variants similarly become just one.
(but am not yet entirely certain), based on reading the PDF link, that rotated and reflected variants are counted as different in the 9862 and 13267364410532 counts, unless they happen to be essentially the same under the different choices of where to put the 1 in the loop and which direction to go around it. I.e. the 8 rotations and reflections of the above closed knight's tour contribute 2 to the 9862 count, not 8 nor just 1.
Incidentally, the PDF link says "It was pointed out by Knuth that the only symmetry of an 8 x 8 board which may preserve a knight's tour is a rotation by 180 degrees. This is an easy but interesting exercise that we will leave for the reader.
" I think it makes quite a good mathematical puzzle, which people may be interested in trying. As a very mild hint, note that the above example shows that the same is not true of the 6x6 board, since it is also preserved under rotations by 90 and 270 degrees.
UncleEbenezer wrote:Bonus question: what is the smallest number of squares that must be identified by a puzzle setter to enable the solver to identify correctly and completely one of those closed loops? 41 squares were pre-numbered in the OP's puzzle, but the solution was fairly easy so I guess a few of them could have been removed... I'm guessing the answer to this question will be closely related to information theory or some sort of hash algorithm but might also be talking out my backside!
I suspect the answer to that question is even more difficult to compute than the number of closed loops! It probably isn't too difficult to establish whether such a puzzle can have any numbers removed - just produce a standard 'back-tracking' program to solve such puzzles, which takes input saying which squares are filled with which numbers and which are empty, and operates by looking for all possible positions for each of the missing numbers, based on the position being reachable in the right number of moves from the nearest specified numbers both up and down from it. If any missing number has no possible position, return "no solution"; if all missing numbers have possible positions, choose the missing number with the smallest number of possible positions (make an arbitrary choice for ties). If that number of possible positions is N, call the program recursively N times to try to solve the problem with that missing number in each of its possible positions, and report all the solutions that any of those recursive calls produces.
The main problem with such a program (beyond getting it bug-free!) is that it may branch out into huge numbers of recursive calls, so that it never finishes in practice. But well-posed puzzles only have one solution, and I suspect that when presented with a well-posed puzzle, such a program will have so many of the branches pruned off by running into the "no solution" case that the time it takes remains very reasonable. Furthermore, I suspect that removing just one number that is essential for there to be only one solution won't increase the number of solutions or the amount of branching needed to discover there's more than one very greatly. So it should be possible to run the program on the puzzle to check that it's only got one solution, and on the puzzle with each of its numbers removed in turn to check that it's 'tight', i.e. removing any number from it leaves a puzzle with more than one solution. So checking that a puzzle is 'locally minimal' in that none of the pre-numbered squares can be removed without producing multiple solutions should be easy enough - but that doesn't tell you that it's 'globally minimal', i.e. that no puzzle of the type exists with fewer pre-numbered squares. For that, you'd need to consider not just removing each pre-numbered square, but also removing each pair of pre-numbered squares plus adding a different pre-numbered square, removing each triple of pre-numbered squares plus adding a pair of different pre-numbered squares, etc. The number of possibilities that need to be considered rapidly becomes astronomical...
One other thing that seems worth mentioning is that given the number of puzzles for which a similar computer-based approach should work (sudokus should be similarly minimisable by computer, for instance), a similar computerised technique is used to automate the production of minimised puzzles. Basically, start with a desired solution to the puzzle - i.e. a complete knight's tour in this case, with all of 1-100 pre-numbered and no missing numbers. Choose a random order in which to consider removing the numbers. Then for each of the numbers in that order in turn, see whether removing it from the puzzle leaves the puzzle still having just one solution. If it does, remove the number from the puzzle; if it leaves the puzzle with multiple solutions, don't remove the number from the puzzle; either way, then move on to the next number. When you get to the end of considering all 100 numbers, you've got a (locally) minimised puzzle.