Notes on the maze mathematics republications

by Michael Behrend unless otherwise stated

[1] tantae difficultatis causa consistit / causes so much difficulty
[Note by E. Lucas, Récréations Mathématiques, vol. 1, p. 23, n. 1; tr. MB]
This is the reason, very likely, why no-one has yet found the solution of the queens problem when their number exceeds eight; see on this subject our fourth recreation on the problem of the eight queens in chess. As for the permutations that would have to be considered here, they are permutations with repetition.
[2] multo simpliciorem fore / would be much simpler
[Note by E. Lucas, Récréations Mathématiques, vol. 1, p. 23, n. 2; tr. MB]
This remark by Euler is much more widely applicable than it seems at first sight. I have noticed that, in a great many problems in the geometry of position, there is often a considerable difference in the manner of treating possibility and impossibility; in general, impossibility is proved more easily than possibility, as will become apparent in the theories of solitaire, the sliding 15-puzzle and some other games. In the next paragraph, Euler adds that his whole method is based on a suitable notation; we shall go on to show that it is the same in all these problems. It will be seen, in our recreation on the Chinese rings (baguenaudier), how the ingenious notation of M. Gros considerably simplifies the theory of this game.
[3] nonnisi ex vna regione initium fieri potest / the start can be made in only one region
As the point may not be quite clear, the following explanation is suggested, in which “even region” is short for “region with an even number of bridges leading to it”. Here (§13) Euler is adding up the number of letter places by applying the rules found in the two preceding paragraphs. In §12 he points out that for an even region we need to take half the number of bridges if the walk does not start in that region, but half the number plus 1 if it does. Since the second case can occur only once, if at all, we simply take half the number of bridges for every even region, and then, if the walk starts in an even region, add an extra 1 at the end.
[4] d’après les Nouvelles Annales de Mathématiques
It is not clear what this refers to. There is a translation of Euler’s paper into French, by E. Coupy, in Nouvelles Annales de Mathématiques, vol. 10 (1851), 106–119. But the translation published by Lucas is quite different from this.
Unlike Coupy, Lucas is rather free in his translation. He introduces algebraic notation, which Euler did not use in this paper; and he cuts out Euler’s fig. 2, so that what Lucas calls fig. 2 is Euler’s fig. 3.
[5] dans les Mémoires de l’Académie des sciences de Berlin pour l’année 1759
Another puzzling reference. Euler’s paper on the Königsberg bridges, “Solutio problematis ad Geometriam situs pertinensis”, appeared in Commentarii Academiae Scientarum Imperialis Petropolitanae, vol. 8 (1736), 128–140. Coupy (see the preceding note) remarks that the Berlin Mémoires for 1759 include Euler’s solution of a rather similar problem, the knight’s tour on a chessboard; perhaps Lucas confused these references.
For full details of Euler’s publications, see The Euler Archive (Königsberg bridges = E53; knight’s tour = E309).
[6] the draughts board of one hundred squares
Draughts (checkers) is played on a 10 × 10 board in most countries, although the 8 × 8 variant is usual in Britain and the USA.
[7] ont des frontières en nombre impair / have an odd number of borders
Borders have changed since this was written in 1882: e.g. Sweden was then united with Norway.
[8] Tom Thumb
i.e. Le Petit Poucet, in the folk-tale of that name (retold by Perrault).
[9] Ovid, Metamorphoses, book VIII
The French translation quoted by Lucas is by Ange-François Fariau de Saint-Ange (1808). The English translation on this website is by Samuel Garth and others (1717).
[10] on prend une voie quelconque / take any path
Except that retreating along the path just used must be disallowed in this case. If retreating is allowed then the algorithm may fail: e.g. in the trivial maze below, if you start at A and then retreat at B you will be trapped at A without having traversed BC.  König correctly says you should continue “mit einer beliebigen anderen Kante”, i.e. with any other edge. Maze with 3 vertices
[11] par cette suppression / as a result of this removal
Lucas does not consider the possibility that P and Q are the same point, in which case PQ is a loop starting and ending at P. However, the conclusion that the number of odd points does not change parity when PQ is removed remains valid in this case.
[12] qui ne contient que des points d’ordre pair / that contains only points of even order
This, however, does not establish the extra fact that we can arrange for the two traversals of each path to be in opposite directions.
[13] le premier volume de la Théorie des Nombres
Édouard Lucas (1842–1891), Théorie des Nombres, vol. 1. Paris: Gauthier-Villars, 1891. Owing to the author’s untimely death, no more volumes were published. This work does not seem to have been translated into English.
[14] est égal à N × 2n. / is equal to N × 2n.
Except that if the original labyrinth (graph) consists of a single vertex with a single loop, there are 2 walks although n = 0. Such special cases need to be kept in mind when implementing maze algorithms on a computer.
[15] X est égal à 129,976,320 / X is equal to 129,976,320
In modern jargon, this is the number of Eulerian circuits on a complete graph with 7 vertices. An implementation of Tarry’s algorithm on a PC gave the number of Eulerian circuits on a complete graph with 9 vertices as 911,520,057,021,235,200. Computer time for this calculation was reduced from many hours to a few seconds by taking note of Tarry’s “important remark” and checking, for each graph that arose, whether it was isomorphic to one for which the number of walks had already been calculated.
For these and similar results, see the Online Encyclopedia of Integer Sequences.

Note on translations  Many historic papers in graph theory are reprinted (in English only) and discussed in N.L. Biggs, E.K. Lloyd & R.J. Wilson, Graph Theory 1736–1936 (Clarendon Press, 1976; repr. 1977, 1986). Chapter 1 (pp. 1–20) includes translations of Euler’s paper on the Königsberg bridges (pp. 3–8) and Tarry’s paper “Le problème des labyrinthes” (pp. 18–20).

König’s book Theorie der endlichen und unendlichen Graphen has been translated by Richard McCoart, with a commentary by W.T. Tutte, as Theory of Finite and Infinite Graphs (Birkhäuser, 1990).

There does not seem to be any English translation of Lucas’s Récréations mathématiques.