THE KNIGHTS TOUR 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. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 ones 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.
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 Cranshaws article there
are some discrepancies as to where the first published solution came from
and anyone interested in finding out more about the puzzles history,
a major task in itself, might try some of the references at the end of
this paper. Graph Theory (Section I) Back to top
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 Eulers 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. 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. 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 Eulers statements from the translation in Graph Theory 1736 - 1936 [2].
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. Im not sure though how the burghers of Königsberg
would have felt about not returning home for supper after such a long
walk! 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 knights tour in chess, solved
by Euler in 1759."
See diagram below showing the first four moves (in colours) and their symmetries.
By continuing in this way Vandermonde generated the four sequences of moves as follows: -
From these four sequences of moves Vandermonde noticed that the end of the first sequence was a knights move away from the beginning of the fourth and the end of the second a knights move away from the start of the third creating two symmetric sequences thus: -
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 knights 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. This sequence of moves is just one of many possible circuits for the knights 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 knights 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. 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).
This diagram above shows the vertex degree of each square on the chessboard in relation to the knights 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 doesnt
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 wont need
to use all the streets in order to do it. The latter is the essence of
the knights 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. 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. 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.
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 Knights 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 knights
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! 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. 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.
So,
even the power of Mathematica, that was used to implement Roths
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. 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 doesnt satisfy the rules for a re-entrant tour it does still use every vertex once and only once. 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.
The path for a 3 x 6 has eluded me as well and the vertex degrees are: -
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. 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). 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: -
I havent 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. 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: -
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 : - 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 knights 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 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. 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.
Finally
I would like to look at the possibility of extending the knights
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 Vandermondes original system
I will attempt to describe the method I used although I dont believe
it will work every time. 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.
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.
And (3, 1, 3) is a knights move from (1, 1, 4) completing the tour. Conclusions and Reflections on the Knights 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.
|