Sources page biographical material



Yüklə 2,59 Mb.
səhifə10/40
tarix27.10.2017
ölçüsü2,59 Mb.
#15566
1   ...   6   7   8   9   10   11   12   13   ...   40

5.E.2.a. PANTACTIC SQUARES
Haubrich's 1995-1996 surveys, op. cit. in 5.H.4, include this.
B. Astle. Pantactic squares. MG 49 (No. 368) (May 1965) 144 152. This is a two dimensional version of the memory wheel. Take a 5 x 5 array of cells marked 0 or 1 (or Black or White). There are 16 ways to take a 2 x 2 subarray from the 5 x 5 array. If these give all 16 2 x 2 binary patterns, the array is called pantactic. The author shows a number of properties and some types of such squares.

C. J. Bouwkamp, P. Janssen & A. Koene. Note on pantactic squares. MG 54 (No. 390) (Dec 1970) 348 351. They find 800 such squares, forming 50 classes of 16 forms.

[Surprisingly, neither paper considers a 4 x 4 array viewed toroidally, which is the natural generalization of the memory wheel. Precisely two of the fifty classes, namely nos. 25 & 41, give such a solution and these are the same pattern on the torus. One can also look at the 4 x 4 subarrays of a 131 x 131 or a 128 x 128 array, etc., as well as 3 and higher dimensional arrays. I submitted the question of the existence and numbers of these as a problem for CM, but it was considered too technical.]

Ivan Moscovich. US Patent 3,677,549 -- Board Game Apparatus. Applied: 14 Jun 1971; patented: 18 Jul 1972. Front page, 1p diagrams, 2pp text. Reproduced in Haubrich, About ..., 1996, op. cit. in 5.H.4. 2pp + 2pp diagrams. This uses the 16 2 x 2 binary patterns as game pieces. He allows the pieces to be rotated, scoring different values according to the orientation. No mention of reversing pieces or of the use of the pieces as a puzzle.

John Humphries. Review of Q-Bits. G&P 54 (Nov 1976) 28. This is Moscovich's game idea, produced by Orda. Though he mentions changing the rules to having non-matching, there is no mention of two-sidedness.

Pieter van Delft & Jack Botermans. Creative Puzzles of the World. (As: Puzzels uit de hele wereld; Spectrum Hobby, 1978); Harry N. Abrams, NY, 1978. The colormatch square, p. 165. See Haubrich,1994, for description.

Jacques Haubrich. Pantactic patterns and puzzles. CFF 34 (Oct 1994) 19-21. Notes the toroidal property just mentioned. Says Bouwkamp had the idea of making the 16 basic squares in coloured card and using them as a MacMahon-type puzzle, with the pieces double-sided and such that when one side had MacMahon matching, the other side had non-matching. There are two different bijections between matching patterns and non-matching patterns, so there are also 800 solutions in 50 classes for the non-matching problem. Bouwkamp's puzzle appeared in van Delft & Botermans, though they did not know about and hence did not mention the double-sidedness. [In an email of 22 Aug 2000, Haubrich says he believes Bouwkamp did tell van Delft and Botermans about this, but somehow it did not get into their book.] The idea was copied by two manufacturers (Set Squares by Peter Pan Playthings and Regev Magnetics) who did not understand Bouwkamp's ideas -- i.e. they permitted pieces to rotate. Describes Verbakel's puzzle of 5.H.2.

Jacques Haubrich. Letter: Pantactic Puzzles = Q-Bits. CFF 37 (Jun 1995) 4. Says that Ivan Moscovich has responded that he invented the version called "Q-Bits" in 1960-1964, having the same tiles as Bouwkamp's (but only one-sided [clarified by Haubrich in above mentioned email]). His US Patent 3,677,549 (see above) is for a game version of he idea. The version produced by Orda Ltd. was reviewed in G&P 54 (Nov 1976) (above). So it seems clear that Moscovich had the idea of the pieces before Bouwkamp's version was published, but Moscovich's application was to use them in a game where the orientations could be varied.


5.F. HAMILTONIAN CIRCUITS
For queen's, bishop's and rook's tours, see 6.AK.

A tour is a closed path or circuit.

A path has end points and is sometimes called an open tour.
5.F.1. KNIGHT'S TOURS AND PATHS
GENERAL REFERENCES
Antonius van der Linde. Geschichte und Literatur des Schachspiels. (2 vols., Springer, Berlin, 1874); one vol. reprint, Olms, Zürich, 1981. [There are two other van der Linde books: Quellenstudien zur Geschichte des Schachspiels, Berlin, 1881, ??NYS; and Das Erste Jartausend [sic] der Schachlitteratur (850 1880), (Berlin, 1880); reprinted with some notes and corrections, Caissa Limited Editions, Delaware, 1979, which is basically a bibliography of little use here.]

Baron Tassilo von Heydebrand und von der Lasa. Zur Geschichte und Literatur des Schachspiels. Forschungen. Leipzig, 1897. ??NYS.

Ahrens. MUS I. 1910. Pp. 319-398.

Harold James Ruthven Murray. A History of Chess. OUP, 1913; reprinted by Benjamin Press, Northampton, Massachusetts, nd [c1986]. This has many references to the problem, which are detailed below.

Reinhard Wieber. Das Schachspiel in der arabischen Literatur von den Anfängen bis zur zweiten Hälfte des 16.Jahrhunderts. Verlag für Orientkunde Dr. H. Vorndran, Walldorf Hessen, 1972.

George P. Jelliss.

Special Issue: Notes on the Knight's Tour. Chessics 22 (Summer 1985) 61 72.

Further notes on the knight's tour. Chessics 25 (Spring 1986) 106 107.

Notes on Chessics 22 continued. Chessics 29 & 30 (1987) 160.

This is a progress report on his forthcoming book on the knight's tour. I will record some of his comments at the appropriate points below. He also studies the 3 x n board extensively.


Two problems with knights on a 3 x 3 board are generally treated here, but cf 5.R.6.

The 4 knights problem has two W and two B knights at the corners (same colours at adjacent corners) and the problem is to exchange them in 16 moves. The graph of knight's connections is an 8-cycle with the pieces at alternate nodes. [Putting same colours at opposite corners allows a solution in 8 moves.]

The 7 knights problem is to place 7 knights on a 3 x 3 board in the 4 corners and 3 of the sides so each is a knight's move from the previously placed one. This is equivalent to the octagram puzzle of 5.R.6.

4 knights problem -- see: at Tilimsâni, 1446; Civis Bononiae, c1475;

7 knights problem -- see: King's Library MS.13, A.xviii, c1275; "Bonus Socius", c1275; at Tilimsâni, 1446;

Al Adli (c840) and as Suli (c880 946) are the first two great Arabic chess players. Although none of their works survive, they are referred to by many later writers who claim to have used their material.

Rudraţa: Kāvyālaʼnkāra [NOTE: ţ denotes a t with an underdot and ʼn denotes an n with an overdot.]. c900. ??NYS -- described in Murray 53 55, from an 1896 paper by Jacobi, ??NYS. The poet speaks of verses which have the shapes of "wheel, sword, club, bow, spear, trident, and plough, which are to be read according to the chessboard squares of the chariot [= rook], horse [= knight], elephant [c= bishop], &c." According to Jacobi, the poet placed syllables in the cells of a half chessboard so that it reads the same straight across as when following a piece's path. With help from the commentator Nami, of 1069, the rook's and knight's path's are reconstructed, and are given on Murray 54. Both are readily extended to full board paths, but not tours. The elephant's path is confused.

Kitâb ash shatranj mimma’l lafahu’l ‘Adli waş Şûlî wa ghair huma [Book of the Chess; extracts from the works of al 'Adlî, aş Şûlî and others]. [NOTE: ş, Ş denote s, S with underdot.] Copied by Abû Ishâq [the h should have an underdot] Ibrâhîm ibn al Mubârak ibn ‘Alî al Mudhahhab al Baghdâdî. Murray 171 172 says it is MS ‘Abd al Hamid [the H should have an underdot] I, no. 560, of 1140, and denotes it AH. Wieber 12 15 says it is now MS Lala Ismail Efendi 560, dates it July August 1141, and denotes it L. Both cite van der Linde, Quellenstudien, no. xviii, p. 331+, ??NYS. The author is unknown. This MS was discovered in 1880. Catalogues in Istanbul listed it as Risâla fi’sh shaţranj by Abû’l ‘Abbâs Ahmad [the h should have an underdot] al ‘Adlî. It is sometimes attributed to al Lajlâj who wrote one short section of this book. Murray, van der Linde and Wieber (p. 41) cite another version: MS Khedivial Lib., Cairo, Mustafa Pasha, no. 8201, copied c1370, which Murray denotes as C and Wieber lists as unseen.

Murray 336 gives two distinct tours: AH91 & AH92. The solution of AH91 is a numbered diagram, but AH92 is 'solved' four times by acrostic poems, where the initial letters of the lines give the tour in an algebraic notation. Wieber 479 480 gives 2 tours from ff. 74a 75b: L74a = AH91 and L74b = reflection of AH92. [Since the 'solutions' of AH92 are poetic, it is not unreasonable to consider the reflection as different.] Also AH94 = L75b is a knight/bishop tour, where moves of the two types alternate. These tours may be due to as Suli. AH196 is a knight/queen tour.

Arabic MS Atif Efendi 2234 (formerly Vefa (‘Atîq Efendî) 2234), Eyyub, Istanbul. Copied by Muhammad [the h should have an underdot] ibn Hawâ (or Rahwâr -- the MS is obscure) ibn ‘Othmân al Mu’addib in 1221. Murray 174 175 describes it as mostly taken from the above book and denotes it V. A tour is shown on p. 336 as V93 = AH92. Wieber 20 24 denotes it A. On p. 479, he shows the tour from f. 68b which is the same as L74b, the reflection of AH92.

King's Library MS.13, A.xviii, British Museum, in French, c1275. Described in van der Linde I 305 306. Described and transcribed in Murray 579 582 & 588 600, where it is denoted as K. Van der Linde discusses the knight's path on I 295, with diagram no. 244 on p. 245. Murray 589 gives the text and a numbered diagram of a knight's path as K1. The path splits into two half board paths: a1 to d1 and e3 to h1, so the first half and the whole are corner to corner. The first half is also shown as diagram K2 with the half board covered with pieces and the path described by taking of pieces. K3 is the 7 knights problem

"Bonus Socius" [perhaps Nicolas de Nicolaï]. This is the common name of a collection of chess problems, assembled c1275, which was copied and translated many times. See Murray 618 642 for about 11 MSS. Some of these are given below. Fiske 104 & 110 111 discusses some MSS of this collection.

MS Lat. 10286, Nat. Lib., Paris. c1350. Van der Linde I 293 295 describes this but gives the number as 10287 (formerly 7390). Murray 621 describes it and denotes it PL. Van der Linde describes a half board knight's path, with a diagram no. 243 shown on p. 245. The description indicates a gap in the path which can only be filled in one way. This is a path from a8 to h8 which cannot be extended to the full board. Murray 641 says that PL275 is the same as problems in two similar MSS and as CB244, diagrammed on p. 674. However, this is not the same as van der Linde's no. 243, though cells 1 19 and 31 32 are the same in both paths, so this is also an a8 to h8 path which does not extend to a full board.

Murray 620 mentions a path in a late Italian MS version of c1530 (Florence, Nat. Lib. XIX.7.51, which he denotes It) which may be the MS described by van der Linde I 284 as no. 4 and the half board path described on I 295 with diagram no. 245 on I 245. Fiske 210-211 describes this and says von der Lasa 163-165 (??NYS) describes it as early 16C, but Murray does not mention von der Lasa. Fiske says it contains a tour on f. 28b, which von der Lasa claims is "das älteste beispiel eines vollkommenen rösselsprunges", but Murray does not detail the problems so I cannot compare these citations. Fiske also says it also contains the 7 knights problem.

Dresden MS 0/59, in French, c1400. Murray describes this on pp. 607 613 and denotes it D. On p. 609, Murray describes D57 which asks for a knight's path on a 4 x 4 board. No solution is given -- indeed this is impossible, cf Persian MS 211 in the RAS. Ibid. is D62 which asks for a half board tour, but no answer is provided.

Persian MS 211 in Royal Asiatic Society. Early 15C. ??NYS.

Extensively described as MS 250 bequeathed by Major David Price in: N. Bland; On the Persian game of chess; J. Royal Asiatic Soc. 13 (1852) 1 70. He dates it as 'at least 500 years old' and doesn't mention the knight's tour.

Described, as MS No. 260, and partially translated in Duncan Forbes; The History of Chess; Wm. H. Allen, London, 1860. Forbes says Bland's description is "very detailed but unsatisfactory". On p. 82 is the end of the translation of the preface: '"Finally I will show you how to move a Knight from any individual square on the board, so that he may cover each of the remaining squares in as many moves and finally come to rest on that square whence he started. I will also show how the same thing may be done by limiting yourself only to one half, or even to one quarter (1) of the board." -- Here the preface abruptly terminates, the following leaf being lost.' Forbes's footnote (1) correctly doubts that a knight's tour (or even a knight's path) is possible on the 4 x 4 board.

Murray 177 cites it as MS no. 211 and denotes it RAS. He says that it has been suggested that this MS may be the work of ‘Alâ'addîn Tabrîzî = ‘Alî ash Shatranjî, late 14C, described on Murray 171. Murray mentions the knight's tour passage on p. 335. This may be in van der Linde, ??NX. Wieber 45 mentions the MS.

Abû Zakarîyâ Yahya [the h should have an underdot] ibn Ibrâhîm al Hakîm[the H should have an underdot]. Nuzhat al arbâb al ‘aqûl fî’sh shaţranj [NOTE: ţ denotes a t with an underdot] al manqûl (The delight of the intelligent, a description of chess). Arabic MS 766, John Rylands Library, Manchester.

Bland, loc. cit., pp. 27 28, describes this as no. 146 of Dr. Lee's catalogue and no. 76 of the new catalogue. Forbes, loc. cit., says that Dr. Lee had loaned his two MSS to someone who had not yet returned them, so Forbes copies Bland's descriptions (on pp. 27 31) as his Appendix C, with some clarifying notes. (The other of Dr. Lee's MSS is described below.) Van der Linde I 107ff (??NX) seems to copy Bland & Forbes.

Murray 175 176 describes it as Arab. 59 at John Rylands Library and denotes it H. He says it was Bland who had borrowed the MSS from Dr. Lee and Murray traces their route to Dr. Lee and to Manchester. Murray says it is late 15C, is based on al Adli and as Suli and he also describes a later version, denoted Z, late 18C. Wieber 32 35 cites it as MS 766(86) at John Rylands, dates it 1430 and denotes it Y1.

Murray 336 gives three paths. H73 = H75 are the same tour, but with different keys, one poetic as in Rudraţa [NOTE: ţ denotes a t with an underdot.], one numeric. H74 is a path attributed to Ali Mani with similar poetic solution. Wieber 480 shows two diagrams. Y1 39a, Y1 39b, Y1 41b are the same tour as H73, but with different descriptions, the latter two being attributed to al Adli. Y1 39a (second diagram) = H74 is attributed to ‘Ali ibn Mani.

Shihâbaddîn Abû’l ‘Abbâs Ahmad [the h should have an underdot] ibn Yahya [the h should have an underdot] ibn Abî Hajala [the H should have an underdot] at Tilimsâni alH anbalî [the H should have an underdot]. Kitâb ’anmûdhaj al qitâl fi la‘b ash shaţranj [NOTE: ţ denotes a t with an underdot] (Book of the examples of warfare in the game of chess). Copied by Muhammed ibn ‘Ali ibn Muhammed al Arzagî in 1446.

Bland, loc. cit., pp. 28 31, describes this as the second of Dr. Lee's MSS, old no. 147, new no. 77. Forbes copies this and adds notes. Van der Linde I 105 107 seems to copy from Bland and Forbes. Murray 176 177 says the author died in 1375, so this might be c1370. He says it is Dr. Lee's on 175 176, that it is MS Arab. 93 at the John Rylands Library and denotes it Man. Wieber 29 32 cites it as MS 767(59) at the Rylands Library and denotes it H. On p. 481, he shows a half board path which cannot be extended to the full board.

This MS also gives the 4 knights and 7 knights problems. Murray 337, 673 (CB236) & 690 and Wieber 481 show these problems.

Risâlahĭ Shatranj. Persian poem of unknown date and authorship. A copy was sent to Bland by Dr. Sprenger of Delhi. See Bland, loc. cit., pp. 43 44. [Bland uses á for â.] Bland says it has the problem of the knight's tour or path. [I think this is the poem mentioned on Murray 182-183 and hence on Wieber 42.]

Şifat mal ‘ûb al faras fî gamî abyât aš šaţranğ [NOTE: Ş, ţ. denote S, t with underdot.] MS Gotha 10, Teil 6; ar. 366; Stz. Hal. 408. Date unknown. Wieber 37 & 480 describes this and gives a path from h8 to e4 which occurs on ff. 70 & 68.

Civis Bononiae [Citizen of Bologna]. Like Bonus Socius, this is a collection of chess problems, from c1475, which exists in several MSS and printings. All are in Latin, from Italy, and give essentially the same 288 problems. See Murray 643 703 for description of about 10 texts and transcription of the problems. Many of the texts are not in van der Linde. Murray 643 cites MS Lasa, in the library of Baron von der Lasa, c1475, as the most accurate and complete of the texts. Two other well known versions are described below.

Paulo Guarino (di Forli) (= Paulus Guarinus). No real title, but the end has 'Explicit liber de partitis scacorum' with the writer's name and the date 4 Jan 1512. This MS was in the Franz Collection and is now (1913) in the John G. White Collection in Cleveland, Ohio. This version only contains 76 problems. Van der Linde I 295 297 describes the MS and on p. 294 he describes a half board path and says Guarino's 74 is a reflection of his no. 243. Murray 645 describes the MS but doesn't list the individual problems. He implies that CB244, on p. 674, is the tour that appears in all of the Civis Bononiae texts, but this is not the same as van der Linde's no. 243. CB236, pp. 673 & 690, is the 4 knights problem, which is Guarino's 42 [according to Lucas, RM4, p. 207], but I don't have a copy of van der Linde's no. 215 to check this, ??NX.

Anon. Sensuit Jeux Partis des eschez: composez nouvellement Pour recreer tous nobles cueurs et pour eviter oysivete a ceulx qui ont voulente: desir et affection de le scavoir et apprendre et est appelle ce Livre le jeu des princes et damoiselles. Published by Denis Janot, Paris, c1535, 12 ff. ??NYS. (This is the item described by von der Lasa as 'bei Janot gedrucktes Quartbändchen' (MUS #195).) This a late text of 21 problems, mostly taken from Civis Bononiae. Only one copy is known, now (1913) in Vienna. See van der Linde I 306 307 and Murray 707 708 which identify no. 18 as van der Linde's no. 243 and with CB244, as with the Guarino work. I can't tell but van der Linde may identify no. 11 as the 4 knights problem (??NX).

Murray 730 gives another half board path, C92, of c1500 which goes from a8 to g5. Murray 732 notes that a small rearrangement makes it extendable to the whole board.

Horatio Gianutio della Mantia. Libro nel quale si tratta della Maniera di giuocar' à Scacchi, Con alcuni sottilissimi Partiti. Antonio de' Bianchi, Torino, 1597. ??NYS. Gives half board tours which can be assembled into to a full tour. (Not in the English translation: The Works of Gianutio and Gustavus Selenus, on the game of Chess, Translated and arranged by J. H. Sarratt; J. Ebers, London, 1817, vol. 1. -- though the copy I saw didn't say vol. 1. Van der Linde, Erste Jartausend ... says there are two volumes.)

Bhaţţa Nīlakaņţha. [NOTE: ţ, ņ denote t, n with underdot.] Bhagavantabhāskara. 17C. End of 5th book. ??NYS, described by Murray 63 66. The author gives three tours, in the poetic form of Rudraţa [NOTE: ţ denotes a t with an underdot.], which are the same tour starting at different points. The tour has 180 degree rotational symmetry.

Ozanam. 1725. Prob. 52, 1725: 260 269. Gives solutions due to Pierre Rémond de Montmort, Abraham de Moivre, Jean Jacques d'Ortous de Mairan (1678-1771). Surprisingly, these are all distinct and different from the earlier examples. Ozanam says he had the problem and the solution from de Mairan in 1722. Says the de Moivre is the simplest. Kraitchik, Math. des Jeux, op. cit. in 4.A.2, p. 359, dates the de Montmort as 1708 and the de Moivre as 1722, but gives no source for these. Montmort died in 1719. Ozanam died in 1717 and this edition was edited by Grandin. Van der Linde and Ahrens say they can find no trace of these solutions prior to Ozanam (1725). See Ozanam-Montucla, 1778.

Ball, MRE, 1st ed., 1892, p. 139, says the earliest examples he knows are the De Montmort & De Moivre of the late 17C, but he only cites them from Ozanam-Hutton, 1803, & Ozanam-Riddle, 1840. In the 5th ed., 1911, p. 123, he adds that "They were sent by their authors to Brook Taylor who seems to have previously suggested the problem." He gives no reference for the connection to Taylor and I have not seen it mentioned elsewhere. This note is never changed and may be the source of the common misconception that knight's tours originated c1700!

Les Amusemens. 1749. Prob. 181, p. 354. Gives de Moivre's tour. Says one can imagine other methods, but this is the simplest and most interesting.

L. Euler. Letter to C. Goldbach, 26 Apr 1757. In: P. H. Fuss, ed.; Correspondance Mathématique et Physique de Quelques Célèbres Géomètres du XVIIIème Siècle; (Acad. Imp. des Sciences, St. Pétersbourg, 1843) = Johnson Reprint, NY, 1968, vol. 1, pp. 654 655. Gives a 180o symmetric tour.

L. Euler. Solution d'une question curieuse qui ne paroit soumise à aucune analyse. (Mém. de l'Académie des Sciences de Berlin, 15 (1759 (1766)), 310 337.) = Opera Omnia (1) 7 (1923) 26 56. (= Comm. Arithm. Coll., 1849, vol. 1, pp. 337 355.) Produces many solutions; studies 180o symmetry, two halves, and other size boards.

[Petronio dalla Volpe]. Corsa del Cavallo per tutt'i scacchi dello scacchiere. Lelio della Volpe, Bologna, 1766. 12pp, of which 2 and 12 are blanks. [Lelio della Volpe is sometimes given as the author, but he died c1749 and was succeeded by his son Petronio.] Photographed and printed by Dario Uri from the example in the Libreria Comunale Archiginnasio di Bologna, no. 17 CAPS XVI 13. The booklet is briefly described in: Adriano Chicco; Note bibliografiche su gli studi di matematica applicata agli scacchi, publicati in Italia; Atti del Convegno Nazionale sui Giochi Creative, Siena, 11 14 Jun 1981, ed. by Roberto Magari; Tipografia Senese for GIOCREA (Società Italiana Giochi Creativi), 1981; p. 155.

The Introduction by the publisher cites Ozanam as the originator of this 'most ingenious' idea and says he gives examples due to Montmort, Moivre and Mairan. He also says this material has 'come to hand' but doesn't give any source, so it is generally thought he was the author. He gives ten paths, starting from each of the 10 essentially distinct cells. He then gives the three cited paths from Ozanam. He then gives six tours. Each path is given as a numbered board and a line diagram of the path, which led Chicco to say there were 38 paths. The line drawing of the first tour is also reproduced on the cover/title page.

Ozanam-Montucla. 1778. Prob. 23, 1778: 178-182; 1803: 177-180; 1814: 155-157. Prob. 22, 1840: 80 81. Drops the reference to de Mairan as the source of the problem and adds a fourth tour due to "M. de W***, capitaine au régiment de Kinski". All of these have a misprint of 22 for 42 in the right hand column of De Moivre's solution.

H. C. von Warnsdorff. Des Rösselsprunges einfachste und allgemeinste Lösung. Th. G. Fr. Varnhagenschen Buchhandlung, Schmalkalden, 1823, 68pp. ??NYS -- details from Walker. Rule to make the next move to the cell with the fewest remaining neighbours. Lucas, L'Arithmétique Amusante, p. 241, gives the place of publication as Berlin.

Boy's Own Book. Not in 1828. 1828-2: 318 states a knight's tour can be made.

George Walker. The Art of Chess-Play: A New Treatise on the Game of Chess. (1832, 80pp. 2nd ed., Sherwood & Co, London, 1833, 160pp. 3rd ed., Sherwood & Co., London, 1841, 300pp. All ??NYS -- details from 4th ed.) 4th ed., Sherwood, Gilbert & Piper, London, 1846, 375pp. Chap. V -- section: On the knight, p. 37. "The problem respecting the Knight's covering each square of the board consecutively, has attracted, in all ages, the attention of the first mathematicians." States Warnsdorff's rule, without credit, but gives the book in his bibliography on p. 375, and asserts the rule will always give a tour. No diagram.

Family Friend 2 (1850) 88 & 119, with note on 209. Practical Puzzle -- No. III. Find a knight's path. Gives one answer. Note says it has been studied since 'an early period' and cites Hutton, who copies some from Montucla, an article by Walker in Frasers Magazine (??NYS) which gives Warnsdorff's rule and an article by Roget in Philosophical Magazine (??NYS) which shows one can start and end on any two squares of opposite colours. Describes using a pegged board and a string to make pretty patterns.

Boy's Own Book. Moving the knight over all the squares alternately. 1855: 511-512; 1868: 573; 1881 (NY): 346-347. 1855 says the problem interested Euler, Ozanam, De Montmart [sic], De Moivre, De Majron [sic] and then gives Warnsdorff's rule, citing George Walker's 'Treatise on Chess' for it -- presumably 'A New Treatise', London, 1832, with 2nd ed., 1833 & 3rd ed., 1841, ??NYS. Walker also wrote On Moving the Knight, London, 1840, ??NYS. 1868 drops all the names, but the NY ed. of 1881 is the same as the 1855. Gives a circuit due to Euler.

Magician's Own Book. 1857. Art. 46: Moving the knight over all the squares alternately, pp. 283-287. Identical to Boy's Own Book, 1855, but adds Another Method. = Book of 500 Puzzles; 1859, art. 46, pp. 97-101. = Boy's Own Conjuring Book, 1860, prob. 45, pp. 246 251.

Landells. Boy's Own Toy-Maker. 1858. Moving the knight over all the squares alternately, p. 143. This is the Another Method of Magician's Own Book, 1857. Cf Illustrated Boy's Own Treasury, 1860.

Illustrated Boy's Own Treasury. 1860. Prob. 47: Practical chess puzzle, pp. 404 & 443. Knight's tour. This is the Another Method of Magician's Own Book.

C. F. de Jaenisch. Traité des Applications de l'Analyse Mathématiques au Jeu des Échecs. 3 vols., no publisher, Saint-Pétersbourg. 1862-1863. Vol. 1: Livre I: Section III: De la marche du cavalier, pp. 186-259 & Plate III. Vol. 2: Livre II: Problème du Cavalier, pp. 1-296 & 31 plates (some parts ??NYS). Vol. 3: Addition au Livre II, pp. 239-243 (This Addition ??NYS). This contains a vast amount of miscellaneous material and I have not yet read it carefully. ??NYR

Leske. Illustriertes Spielbuch für Mädchen. 1864? Prob. 323, pp. 153-154 & 393: Rösselsprung-Aufgaben. Three arrays of syllables and one must find a poetic riddle by following a knight's tour. Arrays are 8 x 8, 8 x 8, 6 x 4.

C. Flye Sainte Marie. Bull. Soc. Math. de France (1876) 144 150. ??NYS -- described by Jelliss. Shows there is no tour on a 4 x n board and describes what a path must look like.

Mittenzwey. 1880. Prob. 222-223, pp. 40 & 91; 1895?: 247-248, pp. 44 & 93; 1917: 247 248, pp. 40-41 & 89. First is a knight's path. Second is a board with word fragments and one has to make a poem, which uses the same path as in the first problem.

Paul de Hijo [= Abbé Jolivald]. Le Problème du Cavalier des Échecs. Metz, 1882. ??NYS -- described by Jelliss and quoted by Lucas. Jelliss notes the BL copy of de Hijo was destroyed in the war, but he has since told me there are copies in The Hague and Nijmegen. First determination of the five 6 x 6 tours with 4-fold rotational symmetry, the 150 ways to cover the 8 x 8 with two circuits of length 32 giving a pattern with 2 fold rotational symmetry, the 378 ways giving reflectional symmetry in a median, the 140 ways with four circuits giving 4-fold rotational symmetry and the 301 ways giving symmetry in both medians (quoted in Lucas, L'Arithmétique Amusante, pp. 238-241).

Lucas. Nouveaux jeux scientifiques ..., 1889, op. cit. in 4.B.3. (Described on p. 302, figure on p. 301.) 'La Fasioulette' is an 8 x 8 board with 64 links of length 5 to form knight's tours.

Knight's move puzzles. The Boy's Own Paper 11 (Nos. 557 & 558) (14 & 21 Sep 1889) 799 & 814. Four Shakespearean quotations concealed as knight's tours on a 8 x 8 board. Beginnings not indicated!

Hoffmann. 1893. Chap. X, no. 6: The knight's tour, pp. 335-336 & 367-373 = Hoffmann Hordern, pp. 225-229. Gives knight's paths due to Euler and Du Malabare, a knight's tour due to Monneron, and four other unattributed tours. Gives Warnsdorff's rule, citing Walker's A New Treatise on Chess, 1832.

Ahrens. Mathematische Spiele. Encyklopadie article, op. cit. in 3.B. 1904, pp. 1080 1093. Pp. 1084 1086 gives many references to 19C work, including estimates of the number of tours and results on 'semi magic tours'.

C. Planck. Chess Amateur (Dec 1908) 83. ??NYS -- described by Jelliss. Shows there are 1728 paths on the 5 x 5 board. Jelliss notes that this counts each path in both directions and there are only 112 inequivalent tours.

Ahrens. 1910. MUS I 325. Use of knight's tours as a secret code.

Dudeney. AM. 1917. Prob. 339: The four knight's tours, pp. 103 & 229. Quadrisect the board into four congruent pieces such that there is a knight's tour on the piece. Jelliss asserts that the solution is unique and says this may be what Persian MS 260 (i.e. 211) intended. He notes that the four tours can be joined to give a tour with four fold rotational symmetry.

W. H. Cozens. Cyclically symmetric knight's tours. MG 24 (No. 262) (Dec 1940) 315 323. Finds symmetric tours on various odd shaped boards.

H. J. R. Murray. The Knight's Tour. ??NYS. MS of 1942 described by G. P. Jelliss, G&PJ 2 (No. 17) (Oct 1999) 315. Observes that a knight can move from the (0, 0) cell to the (2, 1) and (1, 2) cella and that the angle between these lines is the smaller angle of a 3, 4, 5 triangle. One can see this by extending the lines to (8, 4) and (5, 10) and seeing these points form a 3, 4, 5 triangle with (0, 0).

W. H. Cozens. Note 2761: On note 2592. MG 42 (No. 340) (May 1958) 124 125. Note 2592 tried to find the cyclically symmetric tours on the 6 x 6 board and found 4. Cozens notes two are reflections of the other two and that three such tours were omitted. He found all these in his 1940 paper.

R. C. Read. Constructing open knight's tours blindfold! Eureka 22 (Oct 1959) 5-9. Describes how to construct easily a tour between given cells of opposite colours, correcting a method of Roget described by Ball (MRE 11th ed, p. 181). Says he can do it blindfold.

W. H. Cozens. Note 2884: On note 2592. MG 44 (No. 348) (May 1960) 117. Estimates there are 200,000 cyclically symmetric tours on the 10 x 10 board.

Roger F. Wheeler. Note 3059: The KNIGHT's tour on 42 and other boards. MG 47 (No. 360) (May 1963) 136 141. KNIGHT means a knight on a toroidal board. He finds 2688 tours of 19 types on the 42 toroid. (Cf Tylor, 1982??)

J. J. Duby. Un algorithme graphique trouvant tous les circuits Hamiltoniens d'un graphe. Etude No. 8, IBM France, Paris, 22 Oct 1964. [In English with French title and summary.] Finds there are 9862 knight's tours on the 6 x 6 board, where the tours all start at a fixed corner and then go to a fixed one of the two cells reachable from the corner. He also finds 75,000 tours on the 8 x 8 board which have the same first 35 moves. He believes there may be over a million tours.

Karl Fabel. Wanderungen von Schachfiguren. IN: Eero Bonsdorff, Karl Fabel & Olavi Riihimaa; Schach und Zahl; Walter Rau Verlag, Düsseldorf, 1966, pp. 40-50. On p. 50, he says that there are 122,802,512 tours where the knight does two joined half-board paths. He also says there are upper bounds, determined by several authors, and he gives 1.5 x 1026 as an example.

Gardner. SA (Oct 1967) = Magic Show, chap. 14. Surveys results of which boards have tours or paths.

D. J. W. Stone. On the Knight's Tour Problem and Its Solution by Graph Theoretic and Other Methods. M.Sc. Thesis, Dept. of Computing Science, Univ. of Glasgow, Jan. 1969. Confirms Duby's 9862 tours on the 6 x 6 board.

David Singmaster. Enumerating unlabelled Hamiltonian circuits. International Series on Numerical Mathematics, No. 29. Birkhäuser, Basel, 1975, pp. 117 130. Discusses the work of Duby and Stone and gives an estimate, which Stone endorses, that there are 1023±3 tours on the 8 x 8 board.

C. M. B. Tylor. 2 by 2 tours. Chessics 14 (Jul Dec 1982) 14. Says there are 17 knight's tours on a 2 x 2 torus and gives them. Doesn't mention Wheeler, 1963.

Robert Cannon & Stan Dolan. The knight's tour. MG 70 (No. 452) (Jun 1986) 91 100. A rectangular board is tourable if it has a knight's path between any two cells of opposite colours. They prove that m x n is tourable if and only if mn is even and m  6, n  6. They also prove that m x n has a knight's tour if and only if mn is even and [(m  5, n  5) or (m = 3, n  10)] and that when mn is even, m x n has a knight's path if and only if m  3, n  3, except for the 3 x 6 and 4 x 4 boards. (These later results are well known -- see Gardner. The authors only cite Ball's MRE.)

George Jelliss. Figured tours. MS 25:1 (1992/93) 16-20. Exposition of paths and tours where certain stages of the path form an interesting geometric figure. E.g. Euler's first paper has a path on the 5 x 5 such that the points on one diagonal are in arithmetic progression: 1, 7, 13, 19, 25.

Martin Loebbing & Ingo Wegener. The number of knight's tours equals 33,439,123,484,294  -- Counting with binary decision diagrams. Electronic Journal of Combinatorics 3 (1996) article R5. A somewhat vague description of a method for counting knight's tours -- they speak of directed knight's tours, but it is not clear if they have properly accounted for the symmetries of a tour or of the board. Several people immediately pointed out that the number is incorrect because it has to be divisible by four. Two comments have appeared, ibid. On 15 May 1996, the authors admitted this and said they would redo the problem, but they have submitted no further comment as of Jan 2001. On 18 Feb 1997, Brendan McKay announced that he had done the computation another way and found 13,267,364,410,532.

In view of the difference between this and my 1975 estimate of 1023±3 tours, it might be worth explaining my reasoning. In 1964, Duby found 75,000 tours with the same first 35 moves. The average valence for a knight on an 8 x 8 board is 5.25, but one cannot exit from a cell in the same direction as one entered, so we might estimate the number of ways that the first 35 moves can be made as 4.2535 = 9.9 x 1021. Multiplying by 75,000 then gives 7.4 x 1026. I think I assumed that some of the first moves had already been made, e.g. we only allow one move from the starting cell, and factored by 8 for the symmetries of the square, to get 2.2 x 1025. I can't find my original calculations, and I find the estimate 1025 in later papers, so I suppose I tried to reduce the effect of the 4.2535 some more. In retrospect, I had no knowledge of how many of these had already been tried. If about half of all moves from a cell had already been tried before any circuit was found, then the estimate would be more like 2.2534 x 75,000 = 7.1 x 1016. If we divide the given number of circuits by 75,000 and take the 34th root, we get an average valence of 1.78 remaining, far less than I would have guessed.

I am grateful to Don Knuth for this reference. Neither he nor I expected to ever see this number calculated!


Yüklə 2,59 Mb.

Dostları ilə paylaş:
1   ...   6   7   8   9   10   11   12   13   ...   40




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin