[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.
[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.
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.
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.
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).
Draughts (checkers) is played on a 10 × 10 board in most countries, although the 8 × 8 variant is usual in Britain and the USA.
Borders have changed since this was written in 1882: e.g. Sweden was then united with Norway.
i.e. Le Petit Poucet, in the folk-tale of that name (retold by Perrault).
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).
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.
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.
This, however, does not establish the extra fact that we can arrange for the two traversals of each path to be in opposite directions.
É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.
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.
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.