Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to csearle,brightncheerful,Dormouse,Silverstar64,dave559, for Donating to support the site

Knight

cinelli
Lemon Slice
Posts: 367
Joined: November 9th, 2016, 11:33 am
Has thanked: 123 times
Been thanked: 70 times

Knight

#366383

Postby cinelli » December 15th, 2020, 10:39 am

-----------------------------------------
| 1| | | | | | 39| | 25| 22|
-----------------------------------------
| 4| | | 31| | | 26| 23| | 19|
-----------------------------------------
| 29| | 37| | 33| 78| | 42| | |
-----------------------------------------
| 36| | | 83| 48| 45| | 79| | |
-----------------------------------------
| 51| | | 54| | 84| 93| | | 70|
-----------------------------------------
| | | 82| | | | | | | |
-----------------------------------------
| | | | | | 96| 87| 98| | 66|
-----------------------------------------
| 10| | | | | | 74| 89| 16| 91|
-----------------------------------------
| 61| 58| | | | | | 14| | 72|
-----------------------------------------
| 8| | | |100| | 64| | | |
-----------------------------------------

This is a "knight's tour" puzzle which appears in the i newspaper. The objective is to make 99 knight's moves from 1 to 100, covering all the squares in the process. You may think this is straightforward but I have found that, if you make a single mistake, it is very difficult to recover.

Cinelli

UncleEbenezer
Lemon Half
Posts: 6084
Joined: November 4th, 2016, 8:17 pm
Has thanked: 828 times
Been thanked: 1363 times

Re: Knight

#366396

Postby UncleEbenezer » December 15th, 2020, 10:59 am

cinelli wrote:This is a "knight's tour" puzzle which appears in the i newspaper. The objective is to make 99 knight's moves from 1 to 100, covering all the squares in the process. You may think this is straightforward but I have found that, if you make a single mistake, it is very difficult to recover.

Cinelli

Is that premised on visiting every square exactly once? So for example there's obviously just the one way to get from 4 to 8 in four moves, and that in turn eliminates one of the two paths from 1 to 4, leaving us immediately the solution from 1 to 8?

GoSeigen
Lemon Quarter
Posts: 2825
Joined: November 8th, 2016, 11:14 pm
Has thanked: 799 times
Been thanked: 786 times

Re: Knight

#366499

Postby GoSeigen » December 15th, 2020, 6:05 pm

UncleEbenezer wrote:
cinelli wrote:This is a "knight's tour" puzzle which appears in the i newspaper. The objective is to make 99 knight's moves from 1 to 100, covering all the squares in the process. You may think this is straightforward but I have found that, if you make a single mistake, it is very difficult to recover.

Cinelli

Is that premised on visiting every square exactly once? So for example there's obviously just the one way to get from 4 to 8 in four moves, and that in turn eliminates one of the two paths from 1 to 4, leaving us immediately the solution from 1 to 8?



Fun little puzzle, thank you!

Spoiler:

-----------------------------------------
| 1| 30| 3| 34| 27| 32| 39| 20| 25| 22|
-----------------------------------------
| 4| 35| 28| 31| 38| 43| 26| 23| 40| 19|
-----------------------------------------
| 29| 2| 37| 44| 33| 78| 47| 42| 21| 24|
-----------------------------------------
| 36| 5| 52| 83| 48| 45| 68| 79| 18| 41|
-----------------------------------------
| 51| 56| 49| 54| 77| 84| 93| 46| 67| 70|
-----------------------------------------
| 6| 53| 82| 85| 94| 75| 80| 69| 92| 17|
-----------------------------------------
| 57| 50| 55| 76| 81| 96| 87| 98| 71| 66|
-----------------------------------------
| 10| 7| 60| 95| 86| 99| 74| 89| 16| 91|
-----------------------------------------
| 61| 58| 9| 12| 63| 88| 97| 14| 65| 72|
-----------------------------------------
| 8| 11| 62| 59|100| 13| 64| 73| 90| 15|
-----------------------------------------

GS

cinelli
Lemon Slice
Posts: 367
Joined: November 9th, 2016, 11:33 am
Has thanked: 123 times
Been thanked: 70 times

Re: Knight

#366521

Postby cinelli » December 15th, 2020, 8:01 pm

UncleEbenezer wrote:Is that premised on visiting every square exactly once? So for example there's obviously just the one way to get from 4 to 8 in four moves, and that in turn eliminates one of the two paths from 1 to 4, leaving us immediately the solution from 1 to 8?

Yes. The knight visits each square of the grid exactly once. You have given an excellent example of the logic you need to solve this puzzle.

Cinelli

cinelli
Lemon Slice
Posts: 367
Joined: November 9th, 2016, 11:33 am
Has thanked: 123 times
Been thanked: 70 times

Re: Knight

#366523

Postby cinelli » December 15th, 2020, 8:09 pm

Well solved, GS.

Cinelli

staffordian
Lemon Quarter
Posts: 1447
Joined: November 4th, 2016, 4:20 pm
Has thanked: 869 times
Been thanked: 413 times

Re: Knight

#366556

Postby staffordian » December 15th, 2020, 10:17 pm

I try these from time to time in the i newspaper and find them frustrating.

My strategy (if what I do is worthy of that term :) ) is to write out the numbers 1 to 100 in a grid.

Then I cross off the ones already in the puzzle.

Next, I look at my grid for any "single jump" numbers, i.e. those with an already entered number either side of them.

I enter any which have just one possibility.

Repeat the above for any double jump numbers, then treble jumps.

Then back to the singles, and so on.

I suspect this is a sledge hammer rather than refined approach, but even so, it's incredibly easy to overlook a move and put in what looks a certainty, only to realise later it wasn't...

UncleEbenezer
Lemon Half
Posts: 6084
Joined: November 4th, 2016, 8:17 pm
Has thanked: 828 times
Been thanked: 1363 times

Re: Knight

#366589

Postby UncleEbenezer » December 16th, 2020, 12:45 am

In the absence of a program to manipulate numbers like this, I found a pen and paper.

Using chessboard notation extended to j and 10, the walk from a0 to e1 is:

a10 b8 c10 a9 b7 a5 b3 a1 c2 a3
b1 d2 f1 h2 j1 i3 j5 i7 j9 h10
i8 j10 h9 j8 i10 g9 e10 c9 a8 b10
d9 f10 e8 d10 b9 a7 c8 e9 g10 i9
j8 h8 f9 d8 f7 h6 g8 e7 c6 b4
a6 c7 b5 d6 c4 b6 a4 b2 a4 c3
a2 c1 e2 g1 i2 jj4 i6 g7 h5 j6
i4 j2 h1 g3 f5 d4 e6 f8 h7 g5
e4 c5 d7 f6 d5 e3 g4 f2 h3 i1
j3 i5 g6 e5 d3 f4 g2 h4 f3 e1


Erk! That was harder to transcribe than to scribble the numbers. :?

GoSeigen
Lemon Quarter
Posts: 2825
Joined: November 8th, 2016, 11:14 pm
Has thanked: 799 times
Been thanked: 786 times

Re: Knight

#366595

Postby GoSeigen » December 16th, 2020, 4:59 am

staffordian wrote:I try these from time to time in the i newspaper and find them frustrating.

My strategy (if what I do is worthy of that term :) ) is to write out the numbers 1 to 100 in a grid.

Then I cross off the ones already in the puzzle.

Next, I look at my grid for any "single jump" numbers, i.e. those with an already entered number either side of them.

I enter any which have just one possibility.

Repeat the above for any double jump numbers, then treble jumps.

Then back to the singles, and so on.

I suspect this is a sledge hammer rather than refined approach, but even so, it's incredibly easy to overlook a move and put in what looks a certainty, only to realise later it wasn't...


That's basically how I solved it.
-You don't need to start at 1 or go forwards: you can start anywhere and work backwards too.
-Numbers closest together are easiest to resolve generally.
-There is also a spacial aspect: where the board is already filling up there are fewer alternative squares for the next knight's jump.

The puzzle resembled sudoku I thought...

GS

GoSeigen
Lemon Quarter
Posts: 2825
Joined: November 8th, 2016, 11:14 pm
Has thanked: 799 times
Been thanked: 786 times

Re: Knight

#366596

Postby GoSeigen » December 16th, 2020, 5:00 am

UncleEbenezer wrote:In the absence of a program to manipulate numbers like this, I found a pen and paper.

A text editor works well... copy and paste.

GS

UncleEbenezer
Lemon Half
Posts: 6084
Joined: November 4th, 2016, 8:17 pm
Has thanked: 828 times
Been thanked: 1363 times

Re: Knight

#366639

Postby UncleEbenezer » December 16th, 2020, 9:15 am

GoSeigen wrote:
UncleEbenezer wrote:In the absence of a program to manipulate numbers like this, I found a pen and paper.

A text editor works well... copy and paste.

GS

I'd've been forever adjusting the layout to preserve the grid, at the expense of getting on with it. With pen and paper I scribble the grid once, then for all its imperfection it doesn't need readjusting as I enter the numbers.

I wouldn't use a text editor for sudoku either!

I did most of it the way you describe, but that gets harder to follow as the board fills. So then I scribbled a line tracing the journey - so I could focus on the breaks in it - and eventually listed the then-missing numbers (by then there were about half a dozen). If I do another I'll improve that visualisation: instead of tracing the journey, use a couple of tokens (maybe +/-) alongside each number indicating that its predecessor and successor are there - although that'll need the original grid to be a little bigger!

Does anyone else find it mildly unsatisfying that it's not a closed loop, with a knight's move from 100 back to 1?

GoSeigen
Lemon Quarter
Posts: 2825
Joined: November 8th, 2016, 11:14 pm
Has thanked: 799 times
Been thanked: 786 times

Re: Knight

#366669

Postby GoSeigen » December 16th, 2020, 10:21 am

UncleEbenezer wrote:
GoSeigen wrote:
UncleEbenezer wrote:In the absence of a program to manipulate numbers like this, I found a pen and paper.

A text editor works well... copy and paste.

GS

I'd've been forever adjusting the layout to preserve the grid, at the expense of getting on with it. With pen and paper I scribble the grid once, then for all its imperfection it doesn't need readjusting as I enter the numbers.

It might be the editor I use that makes it easy (TextEdit on MacOS). To insert 56 for example, I double click the cell, which selects all three space characters within it, then type <space><5><6> and it's done. Not so hard really.

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?

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!

Gengulphus
Lemon Quarter
Posts: 3764
Joined: November 4th, 2016, 1:17 am
Been thanked: 2144 times

Re: Knight

#366707

Postby Gengulphus » December 16th, 2020, 12:15 pm

staffordian wrote:My strategy (if what I do is worthy of that term :) ) is to write out the numbers 1 to 100 in a grid.

Then I cross off the ones already in the puzzle.

Next, I look at my grid for any "single jump" numbers, i.e. those with an already entered number either side of them.

I enter any which have just one possibility.

Repeat the above for any double jump numbers, then treble jumps.

Then back to the singles, and so on.

My strategy, spoiler-protected because it's a partial spoiler for this puzzle:

Start with the corners, which only have two knights moves available from them, so unless they contain the starting or ending number, the path must use both of those moves, one to enter it and the other to exit it. So for this puzzle:

* Top left corner contains 1, the starting point. Both of the moves from it go to an empty square and one of them must contain 2. Looking ahead a bit, a two-move path is available from each of them to 4, so it's not quickly resolvable which of the empty squares contains 2. Park this for the moment and move on...

* Top right corner contains 22, and the two moves from it lead to 23 and an empty square. That square must contain 21, and looking ahead (or is that behind?) a bit from it, I see that 19 is close to it and there's only one possible route from 19 to 21, so fill in 20 on that route, and continuing from 19, there's only one move available from it to an empty square (and none to a square that already contains 18), so that square must contain 18. Looking further ahead from 18, I don't see 16 or 17 close by; maybe I spot 16 four squares lower down, but there are two routes available to it and no immediately obvious way of choosing between them; either way, park further development of the path from 18 for the moment. Also, looking ahead from 23, I spot 25 close by, and there's only one route from 23 to 25, so fill 24 in on that route. Looking further ahead from 25, I spot 26 a move away from it, but then don't see 27 or 28 anywhere close, so park that as well.

* Bottom left corner contains 8, and the two moves from it are to empty squares, which must contain 7 and 9. I easily spot 10 close by, and it's a move away from only one of those empty squares, so that square must contain 9 and the other must contain 7. Looking ahead (or behind) from 7, I might remember having seen 4 near the top left corner when I was considering that corner; let's suppose I do and see that it's six rows above - only within range of three moves if each of them goes two down and one left or right, and it doesn't take much to see that there is only one available path between them and so 5 and 6 can be filled in on that path. Then looking further back from 4, of the three possible moves from it, one is blocked because it contains 37, another has just been filled in as going to 5, and the remaining one must therefore go to 3, and looking further back still, there's only one place 2 can be - so we've now dealt with the top left corner, and no further extension of the path is wanted in that direction. Looking ahead from 10 doesn't reveal 11 or 12 anywhere nearby, so park that for the moment.

* Bottom right corner is empty, but the two moves from it go to 14 and 16, so it must contain 15. Looking ahead from 16, I probably remember my considerations of the top right corner ending at 18, but there are still two possible places for 17 between 16 and 18, so park that. And similarly, I probably remember my considerations of the bottom left corner ending at 10, but the path from 10 to 14 isn't clear, so park that as well.

Something that can be useful is to strike through numbers that you have completely dealt with (i.e. both neighbours on the path known, or the only neighbour in the case of 1 and 100) as you go along. With that done and the newly discovered numbers italicised, what we now have is:

-----------------------------------------
| 1| | 3| | | | 39| 20| 25| 22|
-----------------------------------------
| 4| | | 31| | | 26| 23| | 19|
-----------------------------------------
| 29| 2| 37| | 33| 78| | 42| 21| 24|
-----------------------------------------
| 36| 5| | 83| 48| 45| | 79| 18| |
-----------------------------------------
| 51| | | 54| | 84| 93| | | 70|
-----------------------------------------
| 6| | 82| | | | | | | |
-----------------------------------------
| | | | | | 96| 87| 98| | 66|
-----------------------------------------
| 10| 7| | | | | 74| 89| 16| 91|
-----------------------------------------
| 61| 58| 9| | | | | 14| | 72|
-----------------------------------------
| 8| | | |100| | 64| | | 15|
-----------------------------------------

That's probably as far as one can go from the corner squares. The squares with the next fewest possible moves from them are the squares orthogonally adjacent to the corners: there are three possible moves from each of them, but there's a good chance that one of those moves can be ruled out. In this case:

* Top left corner - square to its right is a move away from 29, 31 and 37 and to be next to two of them it must contain 30. Square below it contains 4 and has already been dealt with completely.

* Top right corner - both orthogonally adjacent squares have already been dealt with completely.

* Bottom left corner - neither of the orthogonally adjacent squares produces any easy deductions, so park them for now.

* Bottom right corner - square above it contains 72 and one of the moves is not used because it goes to 89, so the other two go to 71 and 73. 74 is nearby, but a move away from both of them, so it doesn't resolve which is which. But looking a bit further afield, 70 is four squares above 72 and does resolve which of the moves from 72 goes to 71 and which to 73. The square to the left of the bottom right corner has possible moves going to 89, 91 and an empty square and must be next to two of them: 90 is tempting, but 92 with the empty square containing 93 is also possible (88 with the empty square containing 87 can be ruled out easily by spotting 87 nearby), so park that for now

As for the original looks at the corners themselves, each of the deductions made in that list should be looked at to see whether one can extend the path further. I won't go into full detail, but the four moves from 70 go to 21, 79, 71 (just filled in) and an empty square - which must therefore contain 69.

Once that's been done, revisit the deductions made about the corner squares themselves to see whether the bits of path worked out then can now be extended further - and indeed one can, because the square that has just been filled with 69 was on one of the two possible routes from 16 to 18, so 17 must lie on the other of those two routes.

I probably won't have got everything worked out by the time I've worked out the full easy consequences of the corner squares and those orthogonally adjacent to them, so then move on to the squares with four moves available from them, which are the squares diagonally adjacent to the corner squares and the six middle squares on each edge. And so it goes on - basically, the idea is to go for low-hanging fruit, parking anything difficult in the hope that finding and picking further low-hanging fruit will pull it down to within reach (a technique that often works well for puzzles, though not recommended for real fruit trees!).

Gengulphus

UncleEbenezer
Lemon Half
Posts: 6084
Joined: November 4th, 2016, 8:17 pm
Has thanked: 828 times
Been thanked: 1363 times

Re: Knight

#366718

Postby UncleEbenezer » December 16th, 2020, 12:48 pm

GoSeigen wrote:It might be the editor I use that makes it easy (TextEdit on MacOS). To insert 56 for example, I double click the cell, which selects all three space characters within it, then type <space><5><6> and it's done. Not so hard really.

So the editor sets up a grid for you. I wouldn't think of that as a text editor, but I guess that's quibbling about terminology.

Guess I could've used a higher-level tool. But the pen and paper actually felt like less effort. Especially since I had a sheet of paper that was good for nothing else after a printer mishap.

Gengulphus
Lemon Quarter
Posts: 3764
Joined: November 4th, 2016, 1:17 am
Been thanked: 2144 times

Re: Knight

#366804

Postby Gengulphus » December 16th, 2020, 4:41 pm

GoSeigen wrote:
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.

I think (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.

Gengulphus

9873210
2 Lemon pips
Posts: 123
Joined: December 9th, 2016, 6:44 am
Has thanked: 13 times
Been thanked: 27 times

Re: Knight

#366835

Postby 9873210 » December 16th, 2020, 6:15 pm

UncleEbenezer wrote:I'd've been forever adjusting the layout to preserve the grid, at the expense of getting on with it. With pen and paper I scribble the grid once, then for all its imperfection it doesn't need readjusting as I enter the numbers.

I wouldn't use a text editor for sudoku either!


I use a spreadsheet for these types of problems. You can use colours, fonts, etc. to note special conditions. It's easy to make a copy for trial solutions.

Of course this requires some familiarity with spreadsheets, but I've been using one as a substitute for a desk blotter, scratch pad, calculator etc. since the time in the 1980's when the task switching time became less than my attention span.

GoSeigen
Lemon Quarter
Posts: 2825
Joined: November 8th, 2016, 11:14 pm
Has thanked: 799 times
Been thanked: 786 times

Re: Knight

#366839

Postby GoSeigen » December 16th, 2020, 6:34 pm

UncleEbenezer wrote:
GoSeigen wrote:It might be the editor I use that makes it easy (TextEdit on MacOS). To insert 56 for example, I double click the cell, which selects all three space characters within it, then type <space><5><6> and it's done. Not so hard really.

So the editor sets up a grid for you. I wouldn't think of that as a text editor, but I guess that's quibbling about terminology.


No it doesn't, I just copied and pasted the one in the OP.

EDIT: I should probably have written "cell" in quotes in my earlier post: it's not an actual cell as in a spreadsheet or wordprocessor table -- I wrote cell to mean a square on the 10x10 chessboard (represented in ASCII in the text editor). Sorry if that was confusing...


GS

jfgw
Lemon Quarter
Posts: 1635
Joined: November 4th, 2016, 3:36 pm
Has thanked: 438 times
Been thanked: 560 times

Re: Knight

#366842

Postby jfgw » December 16th, 2020, 7:01 pm

I just printed it out and filled in the blanks with a pen. I found it quite straightforward. The important thing is to be careful and avoid mistakes, like checking that I wasn't adding a number that was already there. (I didn't need too many sticky labels.)

I made a list of known numbers and sequences as I went, for example, 1 - 10, 18 - 27, and repeatedly worked through the list until I had joined them all up.


Julian F. G. W.

UncleEbenezer
Lemon Half
Posts: 6084
Joined: November 4th, 2016, 8:17 pm
Has thanked: 828 times
Been thanked: 1363 times

Re: Knight

#366850

Postby UncleEbenezer » December 16th, 2020, 7:35 pm

9873210 wrote:I use a spreadsheet for these types of problems. You can use colours, fonts, etc. to note special conditions. It's easy to make a copy for trial solutions.


Indeedie, a spreadsheet was the first thing that sprang to mind when GoS mentioned a text editor.

I'm not even sure in retrospect whether I thought of it, or a word processor, when I originally resorted to pen and paper. I do recollect we were told it came from a newspaper, so pen-and-paper seemed closest to the original. Not to mention a nice change from a life that's spent mostly at the keyboard and screen - at least when at home (this year more than ever) and awake!

I note we have another regular now mentioned having done it on paper.

Gengulphus
Lemon Quarter
Posts: 3764
Joined: November 4th, 2016, 1:17 am
Been thanked: 2144 times

Re: Knight

#366888

Postby Gengulphus » December 16th, 2020, 10:56 pm

Gengulphus wrote:* 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.

I think (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.

On looking again, I find that I should have been certain - the very first paragraph of the PDF link says "The total number of undirected tours is 13,267,364,410,532 and the number of equivalence classes under rotation and reflection of the board is 1,658,420,855,433." - i.e. the 13267364410532 count for the 8x8 board does regard the results of rotating or reflecting the board as different unless they're identical to each other apart from starting the numbering from a different square and/or setting off in a different direction, and if you regard the results of such rotations and reflections as essentially the same, the count reduces to 1658420855433.

Gengulphus

Gengulphus
Lemon Quarter
Posts: 3764
Joined: November 4th, 2016, 1:17 am
Been thanked: 2144 times

Re: Knight

#372274

Postby Gengulphus » January 2nd, 2021, 9:39 am

I'm uncertain whether people have tried and failed to answer the following from viewtopic.php?p=366804#p366804 above, or just failed to notice it buried in the middle of a longish post, but here's a reminder in case it's the latter:

Gengulphus wrote: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.

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 0 guests