The Knight’s Tour Problem as a Conceptual Tool
for
Interdisciplinary Studies
Ronald R. Brown
569 Lake Warren Road
Upper Black Eddy, PA 18972
E-mail: rrbrown@epix.net
This paper appears in Bridges: Mathematical Connections in Art, Music, and Science; Conference Proceedings, 2002; edited by Reza Sarhangi. The paper appears on pages 169 – 180. The Conference was held at Towson University, Towson, MD during the summer of 2002. ISBN 0-9665201-4-9 ISNN 1099-6702
NOTE: The conference proceedings had no color graphics. The electronic version of this presentation contains color graphics. The colors used in Figure 3.3 were chosen so that a black/white image has proper contrast.
The Knight’s Tour Problem as a Conceptual Tool
for
Interdisciplinary Studies
Ronald R. Brown
569 Lake Warren Road
Upper Black Eddy, PA, 18972, USA
E-mail: rrbrown@epix.net
Abstract
The “Knight’s Tour” problem, to move a knight on a chessboard so that all sixty-four squares are occupied only once, was originally used by the author to explore 2-D designs and 3-D constructions. Over the years, however, his fascination with the concept has led him to explore other topics that one would hardly consider being related to the problem as stated, such as music, weaving, and Islamic-style tiling patterns. This article introduces the reader to these and other areas as well. It is hoped that the reader will learn something new from the experience.
1. The Knight’s Tour Problem
1.1. Definition: Knight’s Tour. The “Knight’s Tour” problem is to move a knight on a chessboard so that all sixty-four squares are jumped on only once. A knight’s tour is said to be ‘closed’ or ‘re-entrant’ if position ‘1’ is a knight’s move away from position ‘64’. An ‘open’ or ‘non-re-entrant’ tour is one whereby it is not possible to move to position ‘1’ from position ‘64’.
In this paper I share with the reader how the Knight’s Tour concept (and the knight move itself) can be used to explore diverse areas.
Everything that we can see, everything that we can understand is related to structure — perception is in patterns not fragments. Cyril S. Smith [1].
1.2. Methodology. In the early 1970’s I happened to come upon a knight’s tour solution attributed to Euler [2] and began ‘experimenting’ with it. Examples of ‘rules’ I used were:
· Connect all the points in numerical succession to produce the knight’s path.
· Skip points, i.e., connect the odd numbers to the even numbers such as: 1 – 2, 3 – 4, etc., or, the even numbers to the odd numbers, such as: 2 – 3, 4 – 5, etc.
· Connect only the even-numbered points in increasing order.
· Connect only the odd-numbered points in increasing order.
· Connect the first ‘half’ of the points to the ‘second’ half of the points, namely, 1 – 33, 2 – 34, 3 – 35, …, 31 – 63, 32 – 64
· Connect the points from the ‘extremities’ inward, i.e., 1 – 64, 2 – 63, …,
1.3. One Solution. The knight’s tour used in this article is shown in Figure 1.3. What is interesting about this knight’s tour is that it is ‘closed’ and the sum of every row and every column is the same, namely, 260 [3]. Some authors refer to such tours as being ‘Magic’. Unless stated otherwise, all examples in this paper are based on this knight’s tour. Some of my ideas regarding the knight’s tour can be found in [4].
|
|
|
Figure 1.3: The Knight’s Tour and its path used in this discussion.
2. 2-D Explorations
2.1. Unexpected Symmetry. I discovered that applying the rules in Section 1.2 to the knight’s tour produced totally unexpected results. Figure 2.1 shows the hidden order of the numbers in the array. The union of the first two yields the path in Figure 1.3.
|
|
|
|
|
Figure 2.1: Applying different rules to the number grid reveals hidden order.
2.2. Graphics. Three examples of my early computer graphic endeavors are shown below. One shows 32 shades of gray from 1 à 32 and 33 à 64 (starting with black and ending with white). Another shows small squares within larger squares where the outer areas decrease in intensity while the inner areas increase in intensity, and the third shows the alternation of three shades of gray.
|
|
|
|
Figure 2.2: Examples using different shading rules – can you determine the rules?
2.3. Truchet Tiles. Father Sebastien Truchet (1657-1729) invented the typographic point and defined the Romain du Roi typeface. He became interested in tiling patterns after observing several quarried tiles that had been divided into two colors by a diagonal line. He was the first to publish a detailed study of all combinations of a tiling system [5]. Instead of using a square cut by a single diagonal line using two colors I have experimented by using a square cut by two diagonal lines and using two or four different colors. Figure 2.3 shows the effect of rotating a square with four colors of blue (different shades of gray here) 90 degrees when moving from position to position and the result of rotating an isosceles triangle 90 degrees as the knight’s tour path is progressed. Compare the triangles on the right with those on the left. Even though there is no apparent overall visual symmetry in these graphics there is symmetry on a local scale. In fact, there is overall symmetry (whatever it may be classified as); notice that the position of the triangle(s) in the upper leftmost location and lower rightmost location match as do all other triangles as one snakes ‘forward’ and ‘backward’ beginning at the extremities.
|
|
|
Figure 2.3: Four rotated triangles and a single rotated triangle – the right image lies within the left one.
2.4. Islamic-style Tiling Patterns. An Islamic tiling pattern is a tiling pattern which satisfies one or more of the following criteria [6]:
1. The pattern is transcribed with Arabic Calligraphy from the Quran.
2. The pattern was invented between 900 A.D. and 1500 A.D. and was used to decorate architectural surfaces or other works of art for Muslims, in a culture where the majority of the population, or at least the ruling element, professed the faith of Islam.
3. The pattern is derived from one or more patterns which satisfy criteria 2 and is such that the characteristic shapes from the original (or originals) are recognizable.
“No author so far has been able to offer an account of the evolution of Islamic patterns. How, where, and when did Islamic patterns evolve from the simple to the complex? How did they get transmitted widely, so that the same pattern may be seen in India and Spain? These are fascinating questions to which there are at present no sufficiently detailed answers. Much research is needed.“ [7] (Emphasis is mine.)
Could there be a relationship between a knight (or other pieces) moving on a chessboard and the tiling patterns that developed in Islamic art? Could it be that tiling patterns spread with the spread of chess? Indeed, with the censorship of chess often being imposed by both Moslem and Christian rulers [8] it would be ironic if saboteurs spread the patterns using moves found in an outlawed game. Below I demonstrate that a knight moving on a chessboard can produce patterns that satisfy criteria 2 and 3 of the above definition. Perhaps, a scholar knowledgeable in both chess and Islamic tiling patterns can better answer the relationship between the two developments.
Consider a knight being allowed to ‘wander’ in a random way on the chessboard. A grid is eventually produced that can be used as a template to generate patterns. This template can be ‘enhanced’ significantly by drawing the squares themselves and connecting their centers. With these additional elements the complexity of the patterns can be increased. Figure 2.4a shows four of many patterns that can be generated by the simple template. Figure 2.4b shows the enhanced template and a pattern derived from it. This enhanced template also appears in [9].
|
|
|
|
|
Figure 2.4a: Tiling patterns from the template using just the knight’s moves.
|
|
|
Figure 2.4b: An enhanced template provides for more complexity.
Perhaps the fact that some patterns generated this way can be found in scholarly works on Islamic tiling patterns is not an accident. Perhaps early artisans were inspired by chess and the movements of its pieces! As Jacob Bronowski states, “The artist and the mathematician in Arab civilization have become one.”[10]
2.5. Fractals. Reference [11] describes how I have used a readily available software application to create fractals. The software utilizes a ‘seed’ and any number of copies of it to create a template that is used for fractal generation. The templates I’ve created use a thin rectangle as the seed and two copies of it which are placed in such a way as to be three consecutive moves of a knight on the chessboard. Figure 2.5a shows the base template using a seed and two copies of it. You will notice that these rectangles are the first three moves of the path of the knight’s tour. By manipulating the original template by rotating and/or stretching the copies a fractal is formed. Of course, other consecutive moves could be used to create a template.
Figure 2.5a: Template for generating fractals.
Three examples of fractals generated by this template are shown in Figure 2.5b.
|
|
|
|
Figure 2.5b: Fractals generated by rotating and stretching the components of the template.
3. 3-D Explorations
3.1. Structures. Below are photographs of structures I have made utilizing the knight’s tour used in this discussion. They are Rotated Monoliths, Cylindrical Tour and Tour de Four I.
|
|
|
|
Figure 3.1: Structures based on the knight’s tour.
3.2. Stereograms. These images were created to be viewed with red and blue colored glasses. They are of a ‘3-D’ knight’s tour created from eight 2-D knight’s tours. Images are from the side, from an angle and from the top looking down. Refer to [12] for software used.
|
|
|
|
Figure 3.2: A ‘3-D’ knight’s tour consisting of eight identical 2-D knight’s tours.
3.3. Virtual Reality. Below are examples of pieces that were created using virtual reality software. With VR software one can ‘pass’ through objects and ‘fly’ amongst the pieces. Refer to [13] for explanations and software used.
|
|
|
Figure 3.3: Stacked cylindrical rods and floating rectangles.
4. Music and Weaving
4.1. Music. In 1996 I was a presenter at the Art and Math conference held at SUNY, Albany. At the conference I played “knight’s tour” music composed by a musician, Kevin Murray. I had requested that he compose music based on the knight’s tour with note positions mapped according to Figure 4.1. I told him to use his own creative talents as long as the basic concept was followed. Notice that the second half of the composition is a mirror image of the first half! I will play a tape of Kevin’s piano rendition followed by an orchestral rendition. Each is about one minute in duration.
|
|
|
Figure 4.1: ‘Note’ positions are determined by the row the number lies in – notice the symmetry.
4.2. Weaving. Several months after the Art and Math conference in Albany I received a package from one of the attendees of the conference, Erica Voolich. She said that seeing the above ‘note’ positions had inspired her to create a weaving piece based on them. Because her loom only had six harnesses she had to modify the pattern to accommodate her limitations. I became curious as to what the pattern would have looked like had she not had the hardware limitations. Figure 4.2 shows the weaving piece and what the result would have been without the hardware limitation.
|
|
|
Figure 4.2: Weaving pattern using six harnesses and pattern without the hardware limitation.
The algorithm for generating the pattern can best be understood by listing the sixty-four ‘note’ positions horizontally and leaving a blank line beneath them. It may help to look at the upper left corner of the rightmost image in Figure 4.2. The algorithm is as follows:
1 – Starting at ‘note’ position #1, copy the whole line it is on as the first line of the pattern.
2 – Take ‘note’ position #2 and copy its line as the second line of the pattern.
….
n – Take ‘note’ position #n and copy its line as the nth line of the pattern.
…
64 – Take ‘note’ position #64 and copy its line as the 64th line of the pattern.
Make a reflection about a vertical line after column 64 of the pattern.
Make a reflection about a horizontal line after line 64 of the pattern.
5. f – The Divine Ratio or Golden Section
5.1. Definition. The ‘Divine Ratio’ or the ‘Golden Section’, is simply a number, a number approximately equal to 1.618. The Greek letter ‘phi’, f, is used to represent this number. Consider a rectangle with length L and width W. If the rectangle is such that the ratio L/W equals the ratio of (L+W)/L then the rectangle is said to be a ‘Golden Rectangle’ and both of these ratios equals f. Thus, L/W = (L+W)/L = f. It can be shown that f = (1 + √5)/2. Thus f » 1.61803398875.
5.2. Fibonnaci Sequence. I’ve always been amazed that the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … is related to the Golden Section. As more terms are generated (the next term in the sequence is the sum of the two previous terms) the ratio of any two consecutive terms approximates f; the further out one goes in the sequence the closer the approximation. For example, 21/13 = 1.61538… while 89/55 = 1.618181818… and 233/144 = 1.618055…
5.3. The Knight Move and f. Consider the triangle that is formed by the knight’s movement as shown in Figure 5.3. All the numbers there can be used to express the value of f.
|
|
Using the Pythagorean theorem, i.e., c2 = a2 + b2, where a = 1 unit, b = 2 units, c2 = 5 c = √5.
It will be seen that f = average of the shortest and longest sides, f = (a + c)/2 and 2 just so happens = b. f = (1 + √5)/2 |
Figure 5.3: The triangle a knight makes can be used to remember the Divine Ratio.
6. Knots
6.1. Definition: Alternating Knot. An alternating knot is a knot with a projection that has crossings that alternate between over and under as one travels around the knot in a fixed direction [14]. Various alternating knot knight’s tours can be drawn that provide limited 3-D effect. Because of space limitations it is not possible for me to show a knight’s tour connected as an alternating knot.
7. Cryptology
7.1. A Message for All. The first part of [15] deals with secret ciphers and codes and how they are used (cryptography) while the second part discusses important methods of unauthorized entry into a secret message (cryptanalysis). I leave the following message for you to decipher at your leisure. Needless to say, the key is the topic of this paper.
I**LMCUOLRDTHTEOEADAEI*MOLH**AM***WN**FN**TTOYFTSEOH*RI*WEIHTTOO
8. Computer Programming
8.1. Two Algorithms. In the early 1990’s I wrote a computer program that found solutions to the knight’s tour problem based on the observation that an 8 x 8 board can be partitioned into four quadrants with each quadrant containing two diamond shapes and two rotated squares as shown in Figure 8.1a [16]. It should be noted that Peter M. Roget (of the Thesaurus) utilized this fact in devising a generalized method for finding a knight’s tour solution from a specific starting position to a specific final position. The logic I use in my program is to remain on an ‘object’ for as long as possible (three ‘jumps) before jumping off onto a different object and repeating the jumping behavior. A solution found using my computer program lies to the right of the partitioned board. My program allows one to literally watch and listen as the computer finds a solution. When a solution is found the operator can listen to the pattern and view the resulting path.
If you observe carefully you will notice that the knight’s tour discussed in this paper follows similar logic. Notice that positions ‘1, 2, 3 and 4’ lie on a diamond, positions ‘5, 6, 7 and 8’ lie on a square, positions ‘9, 10, 11 and 12′ lie on a different square, etc., and positions ’61, 62, 63 and 64’ lie on a diamond.
|
|
|
Figure 8.1a: A knight’s tour solution found using a program based on the pattern to the left.
Rob Weggel, a Drexel University co-op student at the time we met, wrote a computer program to find knight’s tours using an exhaustive search approach. What is nice about his approach is that it allows tours to be ordered in numerical sequence as each is found. Consider the eight possible movements of the knight arranged in the array shown in Figure 8.1b:
Figure 8.1b: Allowable knight moves can be used to define the tour numerically.
Rob’s approach was to move from the current position starting with the smallest operation. If that operation caused the knight to be off the board, or jump on a previously occupied square, or to be boxed in, he would back up and try the next larger operation. Starting at the upper left position of the chessboard and moving according to his algorithm the first knight’s tour and the one millionth knight’s tour are:
212343600524500050520544124656000305642245710643410671424632031 Tour# 1
212343600524500050520564743160534310764341032067053547134613031 Tour# 1,000,000
The knight’s tour used in this discussion can be identified by the sixty-three digit number:
450360276022723436775712135245070147246324663670723313565716014.
I also wrote a program that allows a knight to jump randomly on a non-bounded ‘board’ (pixels were my ‘squares’). Figure 8.1c show two examples of random wanderings and two examples of wanderings using horizontal and vertical lines of symmetry.
|
|
Figure 8.1c: Two examples of random knight moves and two using axes of symmetry.
9. Other Areas To Be Explored
· Computing with DNA: Finding a knight’s tour lies in the realm of finding what is called a Hamiltonian cycle in graph theory. Leonard M. Adelman (one of the inventors of the RSA public key cryptosystem) has investigated how DNA can be used to solve the Hamilton Path problem. Although his DNA computer was programmed to find the solution of a 7-node network one would think that larger networks would be capable of being examined, specifically, 64-node networks [17].
· Combinatorics: How many knight’s tours are there? How many knight’s tours are ‘Magic’ (where the row and column sums are the same number)? How many distinct paths are there? These questions lie in the realm of counting large numbers of objects without really counting the objects. Estimates for the number of distinct solutions range from 31 million [18] to 122 million [19] to 168!/(105!63!) [20] which is approximately 1.2 x 1047. Martin Loebbing and Ingo Wegener give the number of knight’s tours as being 33,439,123,484,294 [21] but Brendan McCay claims there is an error in their calculation and the correct number is 13,267,364,410,532 [22]. According to the Oxford Companion to Chess [23], there are about 8,000,000 closed tours and only 2,032 tours that are ‘Magic’. The Oxford Companion also states that it appears to be impossible to make such a tour where the diagonals also add up to 260 but that it has not been proven mathematically. A reference on combinatorics that has a knight’s tour on its cover is [24].
· Boards of Different Sizes: There is no reason to restrict the size of the board to the dimension 8 x 8. Other m x n boards can be considered [25].
· Leapers: A knight’s motion can be described by the notation (1,2). Other moves exist that have also been studied. Many date from mediaeval times. For example, there is the Dummy (0,0), the Wazir (0,1), the Fers (1,1), the Dabbaba (0,2), the Alfil (2,2), the Threeleaper (0,3), the Camel (1,3), the Zebra (2,3), the Tripper (3,3), the Fourleaper (0,4), the Giraffe (1,4), the Lancer (2,4), the Antelope (3,4), and the Commuter (4,4) [26].
· Torus, Cylindrical and Klein Bottle Tours: Refer to [27] for a couple of Theorems regarding knight’s tours on a torus. The authors also suggest finding tours on a cylinder and a klein bottle.
· Möbius Strip Tours: I’ve often thought about knight’s tours on a Möbius strip.
· Cubic Tours: H. E. Dudeney provides a solution to the problem of having a knight jump on all 384 squares (6 x 64) of the faces of a cube [28]. A sculpture using this approach could prove interesting.
· Spherical Tours: Since a sphere is topologically the same as a cube one could ’round-out’ one’s investigations!
· Cellular Automata and Artificial Life: I’ve often thought of trying to come up with a few simple rules for propagating ‘things’ using the knight move. Perhaps a few Zebra and Giraffe leapers on an infinite board could propagate Girbras or Zebaffes!
· Dancing and Choreography: Why not? Of course, knight’s tour music would be a necessity!
· People: One should not forget the human element of it all. An incomplete list of names I’ve come across in my endeavors and mentioned briefly in this document are:
· Leonhard Euler,
· Sebastien Truchet,
· Peter M. Roget, and
· William Rowan Hamilton.
References
[1] Jay Kappraff, Connections – The Geometric Bridge Between Art and Science (McGraw-Hill, Inc, 1991) p. 209.
[2] Cowles New Enlarged Encyclopedia of Science, Industry and Technology (Cowles Book Company, Inc., NY, 1968) p. 254.
[3] Jerzy Gizycki (Translated by A. Wojciechowski, D. Ronowicz, W. Bartoszewski) A History of Chess (Murray’s Sales and Service Co., London, 1972) p. 107.
[4] Ronald R. Brown, The Use of The Knight’s Tour to Create Abstract Art, Leonardo, Vol. 25 Number 1, pp. 55-58. 1992.
[5] http://www.irisa.fr/faqtypo/truchet/truchet3E.html
[6] Syed Jan Abas and Amer Shaker Salman, Symmetries of Islamic Geometrical Patterns (World Scientific 1995) p. 7.
[7] Ibid, p. 14.
[8] http://misc.traveller.com/chess/history/0-1799.html
[9] Clifford A. Pickover, Mazes for the Mind – Computers and the Unexpected (St Martin’s Press, 1992)
p. 314.
[10] J. Bronowski, The Ascent of Man (Boston: Little, Brown, 1973) p. 172.
[11] Clifford A. Pickover, Ed., Fractal Horizons – The Future Use of Fractals, (St. Martin’s Press, 1996) Ronald R. Brown, Chapter 6, “Knight Life”; Software used is on disk included in Dick Oliver’s FractalVision: Put Fractals to Work for You (SAMS Publishing, Indianaplolis, 1992)
[12] Nicholas Lavroff, Virtual Reality Playhouse (Waite Groupe Press, 1992)
[13] Software used was Virtus WalkThrough Pro (Version 2.0). Refer to Figure 1.3. Leftmost – Imagine 64 wooden dowel rods where the rods are stacked alternately in the horizontal (the row where odd numbers appear) and vertical (the columns where even numbers appear) position. Rightmost – Each square is elevated according to its position of the tour.
[14] Colin C. Adams, The Knot Book – An Elementary Introduction to the Mathematical Theory of Knots (W.H.Freeman and Company, 1994) p. 7.
[15] F.L. Bauer, Decrypted Secrets – Methods and Maxims of Cryptology (Springer 1997) p. 91. My encrypted message is:NOW*IS*THE*TIME*FOR*ALL*HUMANITY*TO*COME*TO*THE*AID*OF*THE*WORLD
[16] http://www.ktn.freeuk.com/1c.htm [ALL pages are GREAT!].
[17] Leonard M. Adleman, “Computing with DNA”, Scientific American, August 1998, pp. 54-61.
[18] Jerzy Cizycki, A History of Chess, p. 98. Refer to [3].
[19] Henry and Joan E. Bowers, Arithmetical Excursions, (Dover Publications, 1961), p. 169.
[20] Harry Golombek, Golombek’s Encyclopedia of Chess, (Crown, 1977), p. 165.
[21] http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html
[22] http://www.combinatorics.org/Volume_3/Comments/v3i1r5.html
[23] David Hoop & Kenneth Whyld, The Oxford Companion to Chess Second Edition (Oxford University Press, 1992) p. 204, p. 242.
[24] Victor Bryant, Aspects of Combinatorics – A wide-ranging introduction (Cambridge University Press, 1993).
[25] http://www.ktn.freeuk.com/index.htm [ALL pages are GREAT!].
[26] http://www.ktn.freeuk.com/9a.htm [ALL pages are GREAT!].
[27] John J. Watkins & Rebecca L. Hoenigman, “Knight’s Tours on a Torus”, Mathematics Magazine, Vol. 70, No. 3, June 1997.
[28] H.E. Dudeney, Amusements in Mathematics (Dover Publications, 1970) p.229.