Donate to Remove ads

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

Thanks to Bhoddhisatva,scotia,Anonymous,Cornytiv34,Anonymous, for Donating to support the site

Knight

Charlottesquare
Lemon Quarter
Posts: 1768
Joined: November 4th, 2016, 3:22 pm
Has thanked: 104 times
Been thanked: 559 times

Re: Knight

#374727

Postby Charlottesquare » January 8th, 2021, 12:50 pm

Thought I ought to mention the following that arrived as a Christmas present, it certainly has a knight problem amongst others.

https://www.amazon.co.uk/Bletchley-Park ... 131&sr=8-4

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

Re: Knight

#377390

Postby Gengulphus » January 15th, 2021, 10:35 am

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

I think it's about time I gave my spoiler for this "easy but interesting exercise"...

The symmetries of a square board are rotations by multiples of 90 degrees and four reflections, namely left-right reflection, top-bottom reflection and reflections across each of the square's diagonals. So we need to show that a knight's tour on an 8 x 8 board cannot be preserved by a rotation by 90 degrees in either direction or by any of the reflections. I will prove that it cannot be preserved by a clockwise rotation by 90 degrees, by a left-right reflection or by a reflection across the top-right-to-bottom-left diagonal; the other three cases are proved entirely analogously:

Clockwise rotation by 90 degrees (and anticlockwise rotation by 90 degrees)

Suppose there is a closed knight's tour that is preserved by clockwise rotation by 90 degrees. That tour must visit the top left corner of the board: choose to number that corner 64. The two squares a knight's move out from the corner must be numbered 1 and 63: make an arbitrary choice which is which. Those choices completely determine the numbering of all the squares along the knight's tour, and since the top left corner is a white square (in the standard chess board colouring), every white square will have an even number and every black square an odd number because each knight's move ends on a square of the opposite colour to where it started.

The top right corner of the board is a black square, so its number N is odd and it takes N steps in the numbers-increasing direction along the knight's tour to get from the top left corner to the top right corner. But rotating the board 90 degrees clockwise leaves us with the same knight's tour, so N steps along the tour in one direction or the other from the top right corner takes us to the bottom right corner - and since we know that N steps in the numbers-decreasing direction simply reverses what we've done so far and takes us back to the top left corner, it must be a further N steps in the numbers-increasing direction that takes us to the bottom right corner. Similarly, a further N steps in the numbers-increasing direction after that takes us to the bottom left corner, and a fourth set of N steps in the numbers-increasing direction then takes us to the top left corner.

So a total of 4N steps in the numbers-increasing direction takes us all the way around the knight's tour one or more times, and since the knight's tour is 64 steps long, 4N must be a multiple of 64. Dividing through by 4, N must be a multiple of 16. But that means that we've shown by considering square colours that N is odd and by considering steps along the tour that N is even, and since it's impossible for both of those to be true, such a knight's tour cannot exist.

Note that the corresponding argument for the 6 x 6 board ends up concluding that N is odd and a multiple of 9, which can both be true, and as my earlier example showed, at least one closed knight's tour with fourfold rotational symmetry does exist for the 6 x 6 board. More generally, the situation is that for square boards, there are no closed knight's tours at all for boards of sizes 2, 4 and any odd number, and for larger even sizes, there are closed knight's tours with fourfold symmetry if the size is twice an odd number but not if it's twice an even number.

Left-right reflection (and top-bottom reflection)

As in the last case, suppose that there is a closed knight's tour that is preserved by left-right reflection and choose to number the top left corner of the board 64. Also choose to number the square two right and one down from that corner 1, and the square one right and two down from it 63 (we could in fact make the opposite choice, and that would result in essentially the same argument - but unlike in the previous case, fixing the arbitrary choice halves the number of possibilities below). Again, these choices completely determine the numbering of all the squares along the knight's tour, and the number N of the top right square will be odd.

There are now two possibilities for how the two squares a knight's move away from the top right corner are numbered. The first is that the square two left and one down from it is numbered N+1 and the square one left and two down from it is numbered N-1, so that the top half of the board looks like:

+---+---+---+---+---+---+---+---+
| 64| | | | | | | N|
+---+---+---+---+---+---+---+---+
| | | 1| | |N+1| | |
+---+---+---+---+---+---+---+---+
| | 63| | | | |N-1| |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
: : : : : : : : :

Looking at that, the left-right reflection of the increasing-numbers tour segment from the top left corner to the top right corner (i.e. starting at square 64, then going through squares 1, 2, ..., N-1 to square N) must be the increasing-numbers tour segment from the top right corner to the top left corner (i.e. starting at square N, then going through squares N+1, N+2, ..., 63 to square 64). So those two tour segments must have the same length, and since the first has length N knight's moves, so does the second. But together, those two tour segments make up the entire tour, so N+N = 64, implying that N = 32, which contradicts the fact that N must be odd.

The other possibility is that the square two left and one down from the top right corner is numbered N-1 and the square one left and two down from it is numbered N+1, so that the top half of the board looks like:

+---+---+---+---+---+---+---+---+
| 64| | | | | | | N|
+---+---+---+---+---+---+---+---+
| | | 1| | |N-1| | |
+---+---+---+---+---+---+---+---+
| | 63| | | | |N+1| |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
: : : : : : : : :

Looking at that, the left-right reflection of the increasing-numbers tour segment from the top left corner to the top right corner (i.e. starting at square 64, then going through squares 1, 2, ..., N-1 to square N) must be the decreasing-numbers tour segment from the top right corner to the top left corner (i.e. starting at square N, then going through squares N-1, N-2, ..., 1 to square 64). I.e. that tour segment is its own reflection. But since it consists of an odd number of knight's moves, that implies that it has a central knight's move which is its own left-right reflection - which is impossible.

So both possibilities lead to contradictions, and therefore there are no closed knight's tours that are preserved under left-right reflection. This argument works for any even size board, and so on all boards for which closed knight's tours exist at all.

Reflection across the top-right-to-bottom-left diagonal (and reflection across the top-left-to-bottom-right diagonal)

As in the last case, suppose that there is a closed knight's tour that is preserved by reflection in the top-right-to-bottom-left diagonal and choose to number the top left corner of the board 64, then choose to number the square two right and one down from that corner 1, and the square one right and two down from it 63 (and again we could in fact make the opposite choice, and get essentially the same argument). Again, these choices completely determine the numbering of all the squares along the knight's tour, but this time we look at the number N of the bottom right square. Since that square is white, N is even.

There are now two possibilities for how the two squares a knight's move away from the bottom right corner are numbered. The first is that the square two left and one up from it is numbered N-1 and the square one left and two up from it is numbered N+1, so that the board looks like:

+---+---+---+---+---+---+---+---+
| 64| | | | | | | |
+---+---+---+---+---+---+---+---+
| | | 1| | | | | |
+---+---+---+---+---+---+---+---+
| | 63| | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | |N+1| |
+---+---+---+---+---+---+---+---+
| | | | | |N-1| | |
+---+---+---+---+---+---+---+---+
| | | | | | | | N|
+---+---+---+---+---+---+---+---+

Looking at that, the reflection across the top-right-to-bottom-left diagonal of the increasing-numbers tour segment from the top left corner to the bottom right corner (i.e. starting at square 64, then going through squares 1, 2, ..., N-1 to square N) must be the increasing-numbers tour segment from the bottom right corner to the top left corner (i.e. starting at square N, then going through squares N+1, N+2, ..., 63 to square 64). Together those two tour segments make up the entire knight's tour, and in particular one or other of them must visit the top right corner. But that means that its reflection also visits that corner - so the entire knight's tour visits that corner twice, contradicting the supposition that it's a knight's tour. (The same argument will work just as well using the bottom left corner as using the top right corner, or indeed any other square on the diagonal connecting them.)

The other possibility is that the square two left and one up from the top right corner is numbered N+1 and the square one left and two up from it is numbered N-1, so that the board looks like:

+---+---+---+---+---+---+---+---+
| 64| | | | | | | |
+---+---+---+---+---+---+---+---+
| | | 1| | | | | |
+---+---+---+---+---+---+---+---+
| | 63| | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | |N-1| |
+---+---+---+---+---+---+---+---+
| | | | | |N+1| | |
+---+---+---+---+---+---+---+---+
| | | | | | | | N|
+---+---+---+---+---+---+---+---+

Looking at that, the reflection across the top-right-to-bottom-left diagonal of the increasing-numbers tour segment from the top left corner to the bottom right corner (i.e. starting at square 64, then going through squares 1, 2, ..., N-1 to square N) must be the decreasing-numbers tour segment from the bottom right corner to the top left corner (i.e. starting at square N, then going through squares N-1, N-2, ..., 1 to square 64). I.e. that tour segment is its own reflection. But since it consists of an even number of knight's moves, that implies that it has a central square (numbered N/2) which is its own reflection across the top-right-to-bottom-left diagonal, i.e. which is actually on that diagonal.

Suppose that tour segment contains another square on that diagonal. If that square's number is i, we know that 1 <= i <= N-1 and i is not equal to N/2. But then the fact that the tour segment is its own reflection in that diagonal means that square N-i is the same square - i.e. that the tour segment visits that square at least twice, which is incompatible with it being a tour segment.

So it's not possible that that tour segment visits another square on the top-right-to-bottom-left diagonal, i.e. it only visits one square on that diagonal. But essentially the same argument can be applied to the increasing-numbers tour segment from the bottom right corner to the top left corner (i.e. starting at square N, then going through squares N+1, N+2, ..., 63 to square 64). So between them, those two tour segments only make two visits to squares on the top-right-to-bottom-left diagonal. But together, those two tour segments make up the entire tour, which must make eight visits to squares on that diagonal, so we've again arrived at a contradiction.

So both possibilities lead to contradictions, and therefore there are no closed knight's tours that are preserved under reflection across the top-right-to-bottom-left diagonal. This argument works for any board of even size greater than 2, and so on all boards for which closed knight's tours exist at all.

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 1 guest