THE KNIGHT’S TOUR
by Mark R. Keen

INDEX: Section I - Leonard Euler Section II - Vandermonde Section III - Kirkman Section IV - My Experiments Section V - Squares and the cube Section VI - Conclusions, Reflections & Questions Bibliography, References and Links and finally Guestbook

This is a large site. Use this search to find a keyword by typing in the box below and pressing Find.

Reentrant Tour2Reentrant Tour3Reentrant Tour1

Introduction

As a child I was always fascinated with the game of chess, the different moves of each of the pieces, the use of tactics, planning and revision of ideas in relation to one’s opponents moves, and even simply the beauty of the pieces. The simplicity of the board and the infinite challenges that the game provides will probably never cease to intrigue me. Later in life I was amazed to discover that a Grandmaster of chess could easily defeat even the most powerful computer programs we have yet managed to create and so it was no surprise for me to find, on studying mathematics, that this puzzling pastime has been amusing mathematicians for centuries. Within the game itself there are a number of interesting puzzles to be played with each of the pieces and their respective properties and it is the knight with which I have always been most fascinated.
The Knight’s tour puzzle can be played in many different ways but the original, as far as I can tell, is to begin on an arbitrary square of the board and visit every other square once and only once using the moves of the knight. The game is over when one has successfully visited all 64 squares. According to Ted Cranshaw in his article, "The Second Parchment at Rennes-le-Chateau" [1],

"The puzzle ... may be an ancient one known to the Arabs but in relatively recent times (about 1720) it was suggested by the mathematician Brook Taylor (1685-1731). The credit for the first published solution may be in dispute, but it is generally awarded to de Moivre (1667-1754)."

My first discovery that mathematicians had looked at this puzzle was from the work of A. -T. Vandermonde in Graph Theory 1736 - 1936 [2], and his reference to the work of Leonard Euler (1707-1783) who published a solution in 1759. As you can see from Cranshaw’s article there are some discrepancies as to where the first published solution came from and anyone interested in finding out more about the puzzle’s history, a major task in itself, might try some of the references at the end of this paper.
The problem is an arguably inexhaustible one, as we shall see, and has been tackled in a variety of different ways. To begin with I will look at the work of Euler (Section I) to help define some of the terms and basic ideas underlying graph theory and then look at Vandermonde’s extension of the problem (Section II) before moving on to my own experiments. There are many different problems within the knight’s tour itself and T. P. Kirkman (1808-95) and W. R. Hamilton (1805-65) are two other notable mathematicians who approached the ideas surrounding it. I will look briefly at their work (Section III) with a view to defining and extending some of the concepts involved in the theories of the knight’s tour.
Finally the bulk of this paper (Section IV) is concerned with my own exploration of the tour (by hand!), and extrapolating Vandermonde’s original ideas about the, "problems of position" in regard to regions of space, specifically 3-dimensional objects. In all my research of the knight’s tour I have yet to find any evidence that anybody has, or is currently looking at this puzzle in various sizes of a cube.

Graph Theory (Section I) Back to top

Königsberg

This is an artist’s impression of Königsberg, the River Pregel (in blue) and its bridges (red) published in the 17th Century. I found this at http://www-groups.dcs.st-and.ac.uk/~history/Diagrams/ the colouring wasn’t in the original.

On 26 August 1735, Leonard Euler presented a talk to the Imperial Science Academy that was the basis for his paper, "The solution of a problem relating to the geometry of position." In this work Euler addressed an age-old problem that had for years bewildered the populace of the city of Königsberg in East Prussia. The city, as it was in Euler’s time was situated around the River Pregel which divided the city into 4 separate areas all linked together by a system of bridges as shown in the picture below.
The problem the people used to ponder was whether or not it was possible to walk around the city crossing each of the seven bridges only once. Of course nobody had ever succeeded but it wasn’t until Euler approached the problem from the viewpoint of a mathematician that it was actually proved. It was from this proof that Euler managed to discover some general rules to apply to other problems of this type.
Euler began by producing a topological map or graph of the bridges and their landfall such that the four parts of the city are labelled A, B, C and D, and the bridges are labelled a, b, c, d, e, f and g.

Euler Graph1

Each of the parts of the city is called a vertex and is connected by the bridges to be called edges. Euler proved that it was not possible to use all the edges once no matter where one begins because in order to do so one must exit each vertex every time it is entered and therefore each vertex requires an even number of edges. As can be seen this is not the case in Königsberg, and in fact all the vertices have odd degree or valency. If we were to add just one extra edge ‘h’ between the two vertices B and D it would then be possible to traverse each edge once and once only but we would find ourselves finishing our walk at a vertex other than the one where we began.

Euler Graph2

We now have vertex C with degree 3 and vertex A with degree 5 but B and D are now both even having degree 4. Because we must always have an entry and an exit edge to find a path through the graph this means that the vertices of odd degree must be the start and finish of the path that exists in this connected graph. If we begin our walk at vertex C and finish at vertex A then our path traverses the edges as follows: - a,g,c,d,b,e,h,f. We have fulfilled the criteria required in that we have travelled each edge once and only once but we have not returned to our starting point. These results give us Euler’s statements from the translation in Graph Theory 1736 - 1936 [2].

"If there are more than two areas (vertices) to which an odd number of bridges (edges) lead, then such a journey (Eulerian path) is not possible.

If, however, the number of bridges (edges) is odd for exactly two areas (vertices), then the journey (Eulerian path) is possible if it starts in either of these areas (vertices).

If, finally, there are no areas (vertices) to which an odd number of bridges (edges) lead, then the required journey (Eulerian path) can be accomplished starting from any area (vertex)." (My brackets.)

In this particular paper the definition of an Eulerian path is to be one that covers each edge once and only once but does not necessarily finish on the vertex it began. I’m not sure though how the burghers of Königsberg would have felt about not returning home for supper after such a long walk!
Euler was a man who loved puzzles and, although I cannot find his original discourse and systematic approach to the Knight’s tour, I am aware through the work of other mathematicians that he did look at the problem. Another mathematician of the time, A. -T. Vandermonde took up the challenge.

Graph Theory (Section II) Back to top

Alexandre - Theophile Vandermonde was a French mathematician who became interested in the problem of, "the twists and turns of a system of threads in space ... and the manner in which the threads are interlaced." How one might annotate the path of the threads in a braid, knot or net and therefore fix for all time a method for recreating these objects was what Vandermonde sought. He considered, "a well-known problem, which belongs to this category, that of the knight’s tour in chess, solved by Euler in 1759."
Vandermonde’s "Remarques sur les Problemes de Situation" (Remarks on problems of position), which I shall paraphrase here, begins by outlining his system of notation for the division of space. His method is to first establish a plane of parallel lines that is then cut by a further plane of parallel lines running perpendicular to the first set such that both sets constitute a grid.

4

1

4

2

4

3

4

4

3

1

3

2

3

3

3

4

2

1

2

2

2

3

2

4

1

1

1

2

1

3

1

4


We can now see that the shaded square in the above diagram is in the, "fourth strip of the first division and the third in the second division" of the plane. If we compare this system of notation to that of Cartesian co-ordinates then the ‘first division’ produces values of ‘x’ and the second, values of ‘y’. The shaded square can be represented by (4,3) in Cartesian notation.
Vandermonde then goes on to cut the plane into a third dimension so that the grid above becomes the face of a cube resting on a table, that one is viewing from above. Thus our shaded square now has co-ordinates 1 and the one below it co-ordinates 2 and so on. The large number at the front of the notation being the depth of each level from our viewpoint. Again using Cartesian co-ordinates we could say that the level is ‘z’ and the shaded square on a cube becomes (z, x, y). Once this method is established the possibility of realising a path through the plane that passes through a series of designated points can now be fixed and Vandermonde goes on to describe the sequence of points for a plait and a stocking-stitch.
Having now established the notation for three dimensions we will revert to our original two-dimensional model and look at the knight’s tour on the chessboard. The problem is to find a formula or rule that allows us to satisfy the criteria of the tour and so complete it.
The method Vandermonde used was to pick an arbitrary starting point and ‘reflect’ that move in three other positions on the board so as to try and simplify the solution by creating some kind of symmetry. He achieved this by: -

First list all possible squares on the board and their corresponding co-ordinates. I.e. 64 sets of co-ordinates.

1

1

1

.

.

.

6

7

8

1

2

3

.

.

.

8

8

8

Choose an arbitrary starting point and remove it from the list of all possible squares. Vandermonde chose . This square becomes the beginning of path list ‘one’.

Using successive rotational symmetry of 90o about the centre of the board create three further path lists of co-ordinates that begin with each of the three rotations’ co-ordinates i.e. , and (see diagram below). Then delete these sets of co-ordinates from the list of all possible squares leaving 60 squares.

From the starting point in path list ‘one’ pick an arbitrary knight’s move from this square (such that it is in the remainder of the list of all possible squares) and note this as move 2 in path list ‘one’. Remove it from the list of all possible squares that will now be left with 59 sets of co-ordinates.

Repeat the three rotations for move 2 and add them to their respective path lists remembering to delete them from the list of all possible squares leaving 56 sets of co-ordinates.

Continue with this process until all squares are used up and there will be four paths lists each of 16 sets of co-ordinates. Vandermonde called these four paths lists his ‘symmetric’ lists of moves.

See diagram below showing the first four moves (in colours) and their ‘symmetries’.

Vandermonde's Knight's Tour

By continuing in this way Vandermonde generated the four sequences of moves as follows: -

5

5

4

3

2

4

1

2

3

1

2

3

1

1

3

2

1

3

2

1

4

2

3

4

1

5

2

7

4

8

3

6

4

5

5

3

7

4

8

2

6

1

7

3

8

1

6

2

8

3

7

1

5

2

6

4

8

5

7

7

5

8

6

6

5

4

4

6

2

5

1

7

3

8

2

6

1

8

3

7

1

6

2

8

4

7

3

5

1

4

2

2

4

1

3

3

4

4

5

6

7

5

8

7

6

8

7

6

8

8

6

7

8

6

7

8

5

7

6

5

8

4

7

2

5

1

6

3

From these four sequences of moves Vandermonde noticed that the end of the first sequence was a knight’s move away from the beginning of the fourth and the end of the second a knight’s move away from the start of the third creating two ‘symmetric’ sequences thus: -

5

5

4

3

2

4

1

2

3

1

2

3

1

1

3

2

1

3

2

1

4

2

3

4

1

5

2

7

4

8

3

6

4

4

5

6

7

5

8

7

6

8

7

6

8

8

6

7

8

6

7

8

5

7

6

5

8

4

7

2

5

1

6

3

4

5

5

3

7

4

8

2

6

1

7

3

8

1

6

2

8

3

7

1

5

2

6

4

8

5

7

7

5

8

6

6

5

4

4

6

2

5

1

7

3

8

2

6

1

8

3

7

1

6

2

8

4

7

3

5

1

4

2

2

4

1

3

3

In order for the path to be re-entrant, and so become a circuit, he had to find a way to link these two sequences together and destroy his so called ‘symmetry’ a little. By placing the entire second sequence between the third and fourth terms of the first (blue to blue and red to red are knight’s moves apart) he completed his re-entrant tour that can begin at any one of the squares of the sequence. The path generated by this sequence is shown below.

Vandermonde's complete Tour

This sequence of moves is just one of many possible circuits for the knight’s tour and also represents a new way of looking at graphs i.e. how is it possible to find a path through a given graph that passes through every vertex once and once only? Of course we know this is possible for the knight’s tour because there are many solutions for the 8 x 8 board but the task of finding an Eulerian path might not be so easy. Here is the graph representing a 4 x 4 chessboard with all-possible vertices and edges.

All edge possibilities for 4 X 4

An Eulerian path must, as we have seen, pass through every edge of a graph once and once only. If one were to look at all possible edges on the 8 x 8 chessboard, we would find that there are eight vertices with odd degree and therefore, according to his rules, no Euler path (See diagram).

2

3

4

4

4

4

3

2

3

4

6

6

6

6

4

3

4

6

8

8

8

8

6

4

4

6

8

8

8

8

6

4

4

6

8

8

8

8

6

4

4

6

8

8

8

8

6

4

3

4

6

6

6

6

4

3

2

3

4

4

4

4

3

2

This diagram above shows the vertex degree of each square on the chessboard in relation to the knight’s move.

There are 8 vertices with odd degree and therefore no Euler path.

We now have a different class of problems that are commonly known as traveller problems. In Graph Theory [2] (the brackets are mine), "the explorer examines all possible routes (edges), whereas the traveller simply wishes to visit each place of interest (vertex) once." The most common expressions for these two varieties of problems are "The Postman" and "The Travelling Salesman". The Postman needs to minimise the distance he travels while at the same time making sure he delivers mail to all the streets (edges) and he doesn’t want to travel down any streets more than once. The Travelling Salesman needs to visit specific addresses (vertices) each once and only once and again minimise the distance he travels but of course he won’t need to use all the streets in order to do it. The latter is the essence of the knight’s tour although our knight must finish its journey one move away from its starting point in order to make a cycle, or re-entrant tour.
When T. P. Kirkman first considered circuits in his 1855 paper, "On the Representation of Polyhedra", he discovered a class of graphs that could not contain circuits and it is this result that we shall move onto next.

Graph Theory (Section III) Back to top

Thomas Penyngton Kirkman was a rector and mathematician who explored the possibility of finding a circuit that passes through each vertex of graph once and only once. His rather complex and ultimately unprovable ideas were later picked up and refined successfully by Sir William Rowan Hamilton but not before Kirkman had managed to provide a general proof for the fact that, "if a polyhedron has an odd number of vertices and each face has an even number of edges, then there is no circuit which passes through all the vertices." [2]. This introduces the concept of a graph being bipartite i.e. if a graph can divided into two separate sets of vertices such that every edge in one set joins a vertex in the other then it is called bipartite. If therefore we require a circuit, which passes through each vertex once and only once, and return to the initial vertex then a graph with an odd number of vertices will have no such circuit.
When Euler discussed this question in relation to a chessboard with n x n squares he discovered that if n is odd then there will be an odd number of squares. Since any chessboard is bipartite with two sets of squares black and white, no complete reentrant tour can exist for these boards.

Bipartite/Handshaking Lemma

First looking at the path p of the circuit that may exist can prove if the number of vertices n is odd in a bipartite connected graph then no circuit exists.

If a graph has n vertices then let the initial vertex be V0 and the final vertex Vn-1. The path for a circuit through this graph must start at the initial vertex V0 and pass through all other vertices before reaching the final vertex Vn-1. Because the last vertex must connect to the first V0 = Vn.

If the graph is bipartite then the total number of vertices will be VA + VB

If we assume that V0 is in vertex group A so that V1 is in vertex group B, V2 is in vertex group A and so on, then all vertices in group A will be even and all in group B will be odd. Because Vn must be equal to V0 if the graph has a circuit it holds that Vn must be part of group A and therefore even.

By contradiction if a possible circuit exists for even values of n then none can exist if n is odd.

At the time Kirkman was looking at polyhedra there was another mathematician, William Rowan Hamilton, who was also working on a similar problem that he published in 1857 as "The Icosian Game."

Hamilton’s game consisted of the net for a dodecahedron that had a pin at each of the 20 vertices representing important cities around the world. The problem was to find a route around the shape that passed through each city once and only once. The pins were provided so that a thread could be wound round them and make the path visible.

The Icosian Game
The Icosian Game [3].

It was directly due to the concepts involved in this game that a circuit in a graph visiting every vertex once and only once became know as a Hamiltonian Line. The problem that Euler had was using each edge once and only once and really just a case of examining the vertices in a graph to see if they are even but the Hamiltonian problem has no such simple solution and indeed still today has no general criteria.

The Knight’s Tour (Section IV) Back to top

I began looking at this problem from the original question that is, can I find a path through the chessboard, using only the moves of the knight, that uses every square once and only once and finishes one knight’s move away from the starting square. As I sought solutions to the problem I came across many reference sources and literature referring to previous attempts at the problem, that had looked at more general criteria concerning the finding of Hamiltonian circuits within ‘chessboard graphs’ of varying sizes. After discovering programs have been written to look at and solve this question I found they were beyond my understanding at this point and so decided to approach it from the traditional perspective - by hand!
I began by finding circuits in the 8 x 8 board using various algorithms that seemed at first most logical to me. The first of which was, "start in the corner, where there are only two possible moves (one to square 1 and the other from square 63) and work one’s way around the board sticking as close to the edge as possible bearing in mind access to square 63." This method produced the following results.

Knight's Tour4

It is worth looking at this basic algorithm more closely to see where it might be improved so as to guarantee success on the first try. The algorithm, as it is, leaves the user with a few choices that could easily result in an unsuccessful solution to the problem. Specifically I first draw your attention to move 2, which originates at square 1 and moves to square 2. The choices at square 1 are two-fold i.e. to move to what actually becomes square 48 or to square 2. In this case the reasoning behind the move is to stay as close to the corner as possible if you have choices. This decision occurs again at square 45, where both options for square 46 are on the edge of the board. However, this time both choices are equidistant from a corner. As it happens either square will do to secure the tour if we stick to the original algorithm of staying as close to the edge as possible.
So, apart from the second move, which must stay close to the corner, the algorithm holds. The greatest inadequacy with this algorithm is that it only works if we start in the corner and specify square 63 as our end point.
What happens if I apply this algorithm to any starting square? If I arbitrarily use (3, 4) as the initial vertex then... hey presto, it works!

Knight's Tour5

Unfortunately this is just a lucky second choice but does throw up a very interesting question. When using this original algorithm I have not managed to succeed every time, although if I look forward from approximately move 51 and think carefully about each of the options open to me I do succeed every time. The last quarter of the tour does seem to need refining in order to ensure a complete re-entrant tour without having to think. It certainly seems so because lengthy tours by hand using the original algorithm, resulted in many failures. Before considering what this additional statement might say I refer to an algorithm that already exists for non-re-entrant tours called the Warnsdorff algorithm.
Warnsdorff’s algorithm involves looking at the valency of each of the next possible vertices (knight’s moves) and choosing that square which has the least degree so that any square likely to be isolated will be used up before isolation occurs. This is all the more logical because no vertex has less than degree 2. The only other stipulation is that if the choices of move all have the same degree then the algorithm will look further down each of the possible avenues of moves applying the least degree rule until a successful successor is found. This algorithm has proved to be very slow for large boards and fails at 76 x 76 squares.In "Solution of the Knight's Hamiltonian Path Problem on Chessboards" [5], Ingo Wegener and his fellow researchers tried to refine the Warnsdorff system by the addition of a further rule that initially broke the larger board down into smaller sections for which there were already known tours. This is an approach that they were ultimately able to prove but is different to the Warnsdorff method. It is possible to refine the Warnsdorff algorithm so that it fails less often and this was suggested by Arnd Roth in his "Mathematica notebook"  [6]

"To amend this (the choices of move all have the same degree), I add the rule that in this case, the successor with largest Euclidean distance to the centre of the chessboard is chosen. The introduction of this global criterion substantially reduces the number of blind alleys: now it first occurs on a 428 times 428 chessboard, and the "probability" to run into one (a blind alley) is less than one percent for all chessboards smaller than 2000 times 2000 squares. (All this assumes that the starting point is in a corner of the board.)"

So, even the power of Mathematica, that was used to implement Roth’s improved algorithm, has its limitations and with it's starting point restrictions I still feel that I have made a great deal of headway with my simple algorithm. The refined version is now, "Pick an arbitrary starting square and, using the move of the knight choose your next square such that it is as close to the edge of the board as possible making sure that access to the starting square is not blocked. Where there is a choice of squares equidistant from the edge of the board one must consider the subsequent moves from each of those squares such that they must follow the previous rules." This is really about as tight as I can make it for a 8 x 8 board but is also the method I have used to approach other size boards starting with 3 x 3, the smallest board I have looked at.
With this 3 x 3 board it is clear to see that no Hamiltonian circuit exists because if we start at the centre square ‘*’ we have no moves to make and if we start in any of the other squares it is impossible to reach the centre.

3 x 3 Board

The 3 x 3 square was not a complete waste of time though because if we add just one extra column then we can start ‘outside’ our 3 x 3 section at ’0’. Then we complete the 3 x 3 line that again moves outside to ‘9’ back to ‘10’ (our previously unreachable square) and finishes at ‘11’. Although this doesn’t satisfy the rules for a re-entrant tour it does still use every vertex once and only once.

3 x 4 Board

I note at this stage that the 3 x 3 square has 1 vertex with degree 0 and 8 vertices with degree 2 and no path or circuit exists. The sum of degrees is 16 and we know that in order for a circuit to exist every vertex must have two edges leading to a sum of 18 for a nine-vertex graph and therefore a circuit cannot exist in this graph. In the 3 x 4 rectangle however there are 8 vertices of degree 2 and 4 of degree 3 giving a total of 28. I now know there are enough edges to fulfil requirements for a circuit but none exist in this graph. I still take note of these results.
For a 3 x 5 rectangle there are 8 vertices of degree 2, 4 of degree 3 and 3 of degree 4 giving a total of 40 edges. As there are 15 vertices one would expect a complete tour to have 30 edges and so it may be possible to at least find a path but I could not find one. The vertex degrees are as follows.

2

3

4

3

2

2

2

4

2

2

2

3

4

3

2

The path for a 3 x 6 has eluded me as well and the vertex degrees are: -

2

3

4

4

3

2

2

2

4

4

2

2

2

3

4

4

3

2

The path in the 3 x 7 board is seen to be the incomplete graph of the 3 x 3 board joined to the path of the 3 x 4 board.

3 x 7 Board

Finally in this section the 3 x 8 board has a path constructed from two 3 x 4 paths linked together (see dotted line in diagram below).

3 x 8 Board

I have tabulated the results below to try and uncover a rule for whether or not a path can exist. So far the table looks like this: -

Chessboard (graph)

Vertices degree 0

Vertices degree 2

Vertices degree 3

Vertices degree 4

Circuit degrees required

Total of degrees

Path?

Re-entrant Tour?

3 x 3

1

8

   

18

16

no

no

3 x 4

0

8

4

 

24

28

yes

no

3 x 5

0

8

4

3

30

40

no

no

3 x 6

0

8

4

6

36

52

no

no

3 x 7

0

8

4

9

42

64

yes

no

3 x 8

0

8

4

12

48

76

yes

no

I haven’t managed to formulate a proof for my assumptions but a path does exist in the 3 x 4 board and successfully links to the incomplete path in the 3 x 3 board to provide a path in the 3 x 7 board. If I continue with this hypothesis I can only find paths in boards for which the value of 3 x n can be subdivided into previously successful paths or that provide links to unsuccessful ones.

Squares Only Back to top

If I were to consider just those boards that are n x n then 3 x 3 is my starting point for which, as we have already seen, no path or tour exists. The next square to consider is that of 4 x 4. No path exists for this square and the valency for each vertex is as follows: -

2

3

3

2

3

4

4

3

3

4

4

3

2

3

3

2

The reason no path can exist for this board is that at least two of the degree 2 squares must have two edges attached and they cannot be in opposite corners or a closed circuit of four vertices would end the game. Therefore if the two start and finish squares are in corners on the same row or column all the degree 4 squares will be unable to take any further edges leaving the insoluble problem of negotiating a path around all the vertex degree 3 squares.

If we now look at the square 5 x 5 : -

5 x 5 Board

As can be seen there is a path for this square, above, though there is no re-entrant tour. However, there is something interesting about this square in that it is the first to have a vertex with degree 8 that occurs in the centre square. Euler proved that in the knight’s tour problem if n is greater than or equal to 5 then a path (not necessarily a re-entrant tour) does exist, however time and workload have made it impossible for me to find it at the time of going to press. I will endeavour to find it at a later date.
The circuit I found in the 6 x 6 board was the only one I could find after much searching although I can’t believe at this stage that there is only one. Of course this particular tour can start at any of its 36 squares although I choose to count this as only one knight’s tour.

6 x 6 Board

The 7 x 7 board is, as I have referred to before, bipartite and therefore unable to have a tour though one of the many paths it has is shown below.

7 x 7 Board

I have already looked at 8 x 8 circuits and the information I have discovered about all the n x n squares to this point is consolidated in the table below. There are many obvious patterns in the data though none seems to direct me to any conclusive proof about a general statement regarding the existence of a re-entrant tour in any given n x n board. I am sure that so long as n is even there will be a re-entrant tour however I cannot prove it and without the benefit of a computer I would hate to have to find one for large values of n.

Chessboard (graph)

Vertices degree 2

Vertices degree 3

Vertices degree 4

Vertices degree 6

Vertices degree 8

Circuit degrees required

Total of degrees

Path?

Re-entrant Tour?

4 x 4

4

8

4

0

 

32

48

No

No

5 x 5

4

8

8

0

1

50

76

Yes

No

6 x 6

4

8

12

8

4

72

150

Yes

Yes

7 x 7

4

8

16

12

9

98

240

Yes

No

8 x 8

4

8

20

16

16

128

336

Yes

Yes

9 x 9

4

8

24

20

25

162

448

Yes

No

10 x 10

4

8

28

24

36

200

576

Yes

Yes

11 x 11

4

8

32

28

49

242

720

Yes

No

12 x 12

4

8

36

32

64

288

880

Yes

Yes

Finally I would like to look at the possibility of extending the knight’s tour problem to finding re-entrant tours in cubes. The first fact to consider is the 3 x3 x 3 cube that has a centre vertex that cannot be reached from any other vertex of the cube, therefore a re-entrant tour cannot exist. The next cube to consider is the 4 x 4 x 4 that does have a re-entrant tour I found by hand. The problem I have is writing an algorithm to ensure success every time and I will have to leave that to a further paper. After I describe the tour using a version of Vandermonde’s original system I will attempt to describe the method I used although I don’t believe it will work every time.
I have already described Vandermonde’s system of notation in 3-dimensional objects in section II and how it can be simulated in Cartesian terms, (z, x, y). I will use this altered Cartesian system to describe a re-entrant tour in a 4 x 4 x 4 cube. The notation for the bottom left hand cube in the diagram below is (1, 1, 1) and the top back right cube is (4, 2, 3).

 Portion of a cube

I am currently working on a drawing of this tour in 3-dimensional space but for now it will have to wait. The reader should note at this point that the knight can now move freely in space but must still only move by a factor of (± 2, ± 1) or (± 1, ± 2) in any direction in 3-dimensional space as long as it stays within the volume of the designated cube. A move from (1, 1, 3) to (3, 2, 3) is an example where values of (z, x, y) satisfy these criteria.
The co-ordinate tour starts at VERTEX 0 being (4, 4, 1) with vertex 63 being (2, 4, 2), one knight’s move from the initial vertex.

4,4,1

4,3,3

4,1,4

4,2,2

4,4,3

4,2,4

4,1,2

4,3,1

4,2,3

4,4,4

4,3,2

4,1,1

3,3,1

3,4,3

3,2,4

3,1,2

3,3,3

3,1,4

3,2,2

3,4,1

4,2,1

4,4,2

4,3,4

4,1,3

3,1,1

3,3,2

3,4,4

3,2,3

3,4,2

3,3,4

3,1,3

3,2,1

1,1,1

1,3,2

1,4,4

1,2,3

1,3,1

1,4,3

1,2,4

1,1,2

1,3,3

1,1,4

1,2,2

1,4,1

2,4,3

2,2,4

2,1,2

2,3,1

2,2,3

2,1,1

2,3,2

2,4,4

1,4,2

1,3,4

1,1,3

1,2,1

2,4,1

2,3,3

2,1,4

2,2,2

2,3,4

2,1,3

2,2,1

2,4,2

Of course, in respect of previous discoveries in this paper I know that to look for a tour in a 5 cube would be fruitless because it has an odd number of vertices. However I know that a path exists because it is possible to stack up five 5 x 5 squares to make a cube and therefore just a small matter of locating the link edges between each of the ‘levels.’ This method can also be successfully used to capture the ultimate in 3-dimensional chessboards, the 512-vertex polyhedron that is the 8 x 8 x 8 cube.
We already know that the vertices 0 and 64 are one and the same in a re-entrant tour of the regular chessboard and we can use this information to combine the eight levels of the 8 cube into one tour by listing the ‘bridging ‘ vertices thus: -

1,1,4

2,1,2

4,1,3

6,1,2

8,1,3

7,1,1

5,1,2

3,1,3

And (3, 1, 3) is a knight’s move from (1, 1, 4) completing the tour.

Conclusions and Reflections on the Knight’s Tour Back to top

I have had an immense amount of fun and an intensely thought provoking experience in compiling these pages and there are still so many questions.

Can I adapt Warnsdorff’s algorithm to find paths and re-entrant tours in cubes for given values of n cubes or (p x q x r) rectangles?
Where can I find Euler’s proof for paths in squares of n is greater than or equal to  5?
What is the significance of the patterns I found when tabulating some of my data and how can I use this information to draw some definite conclusions?
There are so many more questions to ask that I don’t have the space here to go into them but I do realise from my research that I have at least lit upon an area of mathematics that is still unsettled in some areas. There is still today no general criteria for the finding of Hamiltonian circuits in a given graph and maybe my explorations might be of help in that department but as yet I can’t see it. I will try to produce a written English algorithm for my tours in a cube but for the meantime I will add some of my findings to my website because the many people out there who have also been looking at this problem might find it useful.
There is a list of references in the Bibliography that I have used in addition to those quoted in the body of this document and I would like to bring special attention to the historical use of knight’s tours in the field of cryptography. As I mentioned before, one of the French mathematicians’ de Moivre’s tours is the favourite to have been used as an encoding device in the ‘The Second Parchment at Rennes-le-Chateau’ that is fascinating reading for any budding Sherlock Holmes’ out there. And finally as a student teacher I would like to point out that the knight’s tour is a great exercise to try in the classroom both for simple educative fun and more extended work as required.

Bibliography and References Back to top

[1] Cranshaw Ted The Second Parchment at Rennes-le-Chateau (http://www.fiu.edu/~mizrachs/parchmen.htm)

[2] N. L. Biggs, E. K. Lloyd, R. J. Wilson Graph Theory 1736 - 1936 (1976) Oxford, Oxford University Press

Beineke & Wilson Graph Connections (1997) London, Clarenden Press

[5] A. Conrad, T. Hindrichs, H. Morsy & I. Wegener: Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discr. Appl. Math. 50, 125-134 (1994).

John Clark and Derek Allan Holton A first Look at Graph Theory (1991) Singapore, World Scientific

[3] Oystein Ore Graphs and their uses (1963) Stanford, California, USA, Random House

W. T. Tutte Graph Theory as I have known it (1998) London, Clarenden Press

Robin J. Wilson Introduction to Graph Theory (1972) Harlow, Longman Scientific & Technical

[6] Arnd Roth's Homepage - Studying physics in Heidelberg he spends a lot of time doing electrophysiologyalthough his main scientific interests are computational physics, computational neuroscience, and software environments for scientific computation, such as Mathematica and NEURON.

Other Graph Theory and Related Pages by Stephen C. Locke - This site covers all aspects of Graph Theory in general and is a valuable starting point if you are looking for plenty of link suggestions.

Combinatoric Object Server - Not much more I'm afraid but still useful.

Paul E. Black - A computer scientist from Maryland, USA who has some great research and links that are an absolute necessity for anyone interested in algorithms and graph theory.

Gunno Törnberg - Thoughts and research on the Travelling Salesman's Problem with other very useful links. A top chap who helped me greatly with the accuracy of these pages of mine. Gunno also has a great Knight's Tour page that is well worth a visit at this address.

All material, produced by whatever means in these pages, Copyright © Mark Richard Keen 2000

Please feel free to sign the visitor's book. My Guestbook

Back to top