Main

Links

Orders

Post

Next Page

Next + 10

In February 1956, M Apsimon posed the question: how many cyclically symmetric knight tours on a board 10x10?  In the 1970's, W H Cozens reiterated the question in The Mathematical Gazette, and published the tours below.  More recently, Donald Knuth found that exactly 2,432,932 knight's tours are unchanged by 180-degree rotation of the chessboard.  It seems the problem from 1956 might now be answerable.

1956 question - how many of these are there?

In the March 1973 issue of Games and Puzzles, Robin Merson found a non-crossing knight's tour on an 11x11 board with a length of 74 moves.  He found a longer non-crossing tour on a board with a smaller area.  Can you find it?

Keyed Tours.  Each path starts at the top left corner, and starts cycling through the KEY over and over again.  It will always take the direction suggested by the key IF a complete closed tour would still be possible.  There are three parts to the key.
1.  A direction key.  Below, a simple 1=N 2=E 3=S 4=W is used.  The eight paths of a knight could be labeled, or something more complicated.
2.  A grid.  Below, a 6x6 grid is used.  The grid could be multidimensional, or hexagonal, or even a grid of chaos tiles.
3.  A code.  Each code will produce a unique path.  On a 50x50 grid, what path would result from a 12345678 code from a knight?

CONSTANT LENGTH TOURS  by Ed Pegg Jr.

   Leonhard Euler was the first to find a closed tour of a chessboard by a knight.  Other pieces, more exotic, exist in the realm of Fairy Chess.  Until now, their tour potential hasn’t been studied.  I’ll start with definitions, most of them standard Graph Theory terms.

Point (vertex, node, junction, cell)
Line (edge, arc, branch)
Two points are adjacent (linked) if they are joined by a line.
A loop links a point to itself.  [None of the graphs in this paper contain loops.]
A line is incident to the points it joins.
The degree of a point is the number of lines incident to it.
Lattice - a graph where all points are midpoints of tiles in a regular tiling. [I’ll deal with square tilings.]
A graph is connected if there exists a sequence of points and lines from any point to any other point.
A Hamiltonian cycle is a loopless, connected graph where every point of the graph has degree 2.
A Hamiltonian path is a connected graph of N points with N-2 points of degree 2 and 2 points of degree 1.
A Re-entrant knights tour is a Hamiltonian cycle on an 8x8 lattice where each line has length   .

Board:  m x n lattice of squares.
(Closed) Tour:  A Hamiltonian cycle on a lattice.
Open Tour:  A Hamiltonian path on a lattice.
Leaper:  A knight is a (1,2) leaper.  In the same fashion, (2,3) leapers and (1,4) leapers exist.
Constant Length Tour:  A tour where every line has a constant length, c.

   For c= sqrt(5), we get knight moves.  Question: What c’s allow a tour of the 8x8 board?  Answer: The only c’s that work are c=1, c= sqrt(5), and c=5.   No tour exists on the 9x9 board, due to parity.  For the 10x10 board, c=1, c= sqrt(5), c= sqrt(13), c= sqrt(17), and c=5 are the only c’s that allow a constant length tour.
   C = 1 corresponds to the (0,1) leaper and is called a Prince.
   C = sqrt(5) corresponds to the (1,2) leaper and is called a Knight.
   C = sqrt(13) corresponds to the (2,3) leaper and is called a Zebra [traditional Fairy Chess].
   C = sqrt(17) corresponds to the (1,4) leaper and is called a Giraffe.
   Note that C =  sqrt(a^2 + b^2) corresponds to a (a,b) leaper.

   The standard puzzle seen in puzzle books involves the idea of parity.  An example of a parity argument: Prove that a knight cannot make a closed tour of an n x n chessboard, where n is odd.  Proof: fill in the board with a checkerboard coloring.  The knight will start on one of the two colors, let it be white.  After an even number of moves, the knight will be on a white square.  The closed tour has an odd number of squares.  Since a closed tour would require the knight to land on its starting square after an odd number of moves, the tour is impossible.

   We will now prove:
   1.  There is no closed tour for a (1,2) leaper [knight] on a 4 x n board.
   2.  There is no open tour for a (1,2) leaper on a 4x4 board.
   3.  There is no open tour for a (1,4) leaper on an 8x8 board.
   4.  There is no open tour for a (2,3) leaper on an 8x8 board.
   5.  There is no open tour for a (2,3) leaper on a 9x9 board.
   6.  There is no open tour for a (2,3) leaper on an 11x11 board.
   7.  There is no open tour for a (2,3) leaper on a 12x12 board.
 

   Note that the nonexistence of an open tour implies the nonexistence of a closed tour.

1.  There is no closed tour for the (1,2) leaper [knight] on a 4 x n board.
   Proof by contradiction:  Suppose such a tour existed.  As can be seen in diagram 1, every grey  point (cell) is adjacent to two clear points.  A grey  point is not adjacent to a grey  point.  Since half the tour consists of grey  points, the tour must look something like  grey white grey white .... white grey, where the first and last grey cells are the same cell.  Thus, every other move is a clear  point.
   As can be seen in diagram 2, grey  points are adjacent only to clear  points.  Every other move must be a clear  point.  By combining these two results, we get a contradiction; namely, that one fourth of the points support one half of the total moves.  The idea of this proof is used several times in the course of this paper.

2.  There is no open tour for a (1,2) leaper on a 4x4 board.
Proof A: Examine the black  points and grey  points of diagram 3.  The corner grey  points are adjacent only to the interior grey  points, the same applies to the black  corner points.  A closed tour is thus impossible, since these two colors are closed to the rest of the board.  However, we have the leeway of a spare move at the begining and end of an open tour.  We can start with a black  corner, eventually make a move from a black  interior point to the dot  points and clear  points, move to a grey interior point, and finish the tour.  Unfortunately, it is impossible to move directly from a dot  point to a clear  point.  So an open tour is impossible.
Proof B:  This proof exploits the idea of Proof 1.  Color the outer columns as shown in diagram 4.  A closed tour is impossible, as described in Proof 1.  However, an open tour is possible on a 4 x n board, provided the move sequence looks something like the following: grey white grey...white grey grey white ... grey white grey.  If we color the top and bottom rows, we reach the same conclusion.  Combining these, a tour is possible as long as we move from a white  point in diagram 5 to another white  point.  This is impossible.

3.  There is no open tour for a (1,4) leaper on an 8x8 board.
Proof A: Examine diagram 6.  Borrowing a term from Cartesian coordinants, examine the eight black  points in the first and third quadrants.  They are adjacent only to black  points in the second and fourth quadrants.  Similarly, the grey  points in the second and fourth quadrants are adjacently only to grey  points in the first and third quadrants.  From here on, the proof is identical to the proof in 2A.
Proof B: Color the board as shown in diagram 7.  The grey  points are adjacent only to clear  and dot  points.  The closed tour is impossible, see proof 1.  An open tour might be possible if we move from a non-grey  point to a non-grey  point midway through the tour.  Rotate the diagram 90 degrees, and make the same observations.  A tour is possible if two dot  points are tour-adjacent. But they aren’t, so there isn’t an open tour.

4.  There is no open tour for a (2,3) leaper on an 8x8 board.
Proof: In diagram 8, each grey  point has degree 2, unless it marks the beginning or end of a tour, in which case it can have degree 1.  The grey  points are adjacent only to dot  points.  The grey  points require at least (14*2 +  2*1 = 30) lines, but the dot  points can only accept (12*2 = 24) of these lines.  An open tour is thus impossible.

5.  There is no open tour for a (2,3) leaper on a 9x9 board.
Proof:  In diagram 9, each black  point is adjacent to two dot  points.  Each grey  point is adjacent to at least one dot  point.  The black  and grey  points require at least ( (16*2 + 16*1)/2 = 24)  dot points, but there are only 21 dot  points, so the open tour is impossible.
   A similar coloring scheme is useful for showing the impossibility of (a,b) leapers on small boards.

6.  There is no open tour for a (2,3) leaper on an 11x11 board.
Proof:  First, note that this is an odd board.  Due to parity, the grey  points and X  points can neither begin nor end the open tour.  Next, note that the X  points are adjacent only to dot  points and squiggle points.  During the course of the tour, we must have the sequence squiggle X dot X squiggle four times.  Now look at the grey  points.  As far as the tour is concerned, the grey  points cannot be adjacent to dot  points, so they must be adjacent to the greydot  points.  Since each grey  point has degree two, we have a closed loop: grey greydot grey greydot grey greydot grey greydot. The tour is impossible.
   This problem was first solved by Dan Cass.

7.  There is no open tour for a (2,3) leaper on a 12x12 board.
Proof: First, note that a closed tour is impossible.  Each greysquiggle  point has degree 2 and is only adjacent to dot  points.  There are 36 greysquiggle  points and 36 dot  points, and thus we have a closed system.
   Now then, using the methodology in Proof 1, note that the gray-shaded points are adjacent only to the white-shaded points.  Turn the diagram 90 degrees and note the same thing.  Combining, an open tour is possible only if we can move from a dot  point to a dot  point midway through the tour.  We can!  But this use of the only free move leads to the same closed system described above.  Thus the open tour is impossible.