Sources page biographical material

5.E. EULER CIRCUITS AND MAZES
Euler circuits have been used in primitive art, often as symbols of the passage of the soul to the land of the dead. [MTg 110 (Mar 1985) 55] shows examples from Angola and New Hebrides. See Ascher (1988 & 1991) for many other examples from other cultures.
┌────┬─────────┬────┐

│ │ │ │

├────┴────┬────┴────┤

│ │ │

└─────────┴─────────┘
Above is the 'five brick pattern'. See: Clausen, Listing, Kamp, White, Dudeney, Loyd Jr, Ripley, Meyer, Leeming, Adams, Anon., Ascher. Prior to Loyd Jr, the problem asked for the edges to be drawn in three paths, but about 1920 the problem changed to drawing a path across every wall.

Trick solutions: Tom Tit, Dudeney (1913), Houdini, Loyd Jr, Ripley, Meyer, Leeming, Adams, Gibson, Anon. (1986).

Non-crossing Euler circuits: Endless Amusement II, Bellew, Carroll 1869, Mittenzwey, Bile Beans, Meyer, Gardner (1964), Willson, Scott, Singmaster.

K_n denotes the complete graph on n vertices.

Matthäus Merian the Elder. Engraved map of Königsberg. Bernhard Wiezorke has sent me a coloured reproduction of this, dated as 1641. He used an B&W version in his article: Puzzles und Brainteasers; OR News, Ausgabe 13 (Nov 2001) 52-54. BLW use a B&W version on their dust jacket and on p. 2 which they attribute to M. Zeiller; Topographia Prussiae et Pomerelliae; Frankfurt, c1650. I have seen this in a facsimile of the Cosmographica due to Merian in the volume on Brandenburg and Pomerania, but it was not coloured. There seem to be at least two versions of this picture --??CHECK.

L. Euler. Solutio problematis ad geometriam situs pertinentis. (Comm. Acad. Sci. Petropol. 8 (1736(1741)) 128 140.) = Opera Omnia (1) 7 (1923) 1 10. English version: Seven Bridges of Königsberg is in: BLW, 3 8; SA 189 (Jul 1953) 66 70; World of Mathematics, vol. 1, 573 580; Struik, Source Book, 183 187.

My late colleague Jeremy Wyndham became interested in the seven bridges problem and made inquiries which turned up several maps of Königsberg and a list of all the bridges and their dates of construction (though there is some ambiguity about one bridge). The first bridge was built in 1286 and until the seventh bridge of 1542, an Euler path was always possible. No further bridge was built until a railway bridge in 1865 which led to Saalschütz's 1876 paper -- see below. In 1905 and later, several more bridges were added, reaching a maximum of ten bridges in 1926 (with 4512 paths from the island), then one was removed in 1933. Then a road bridge was added, but it is so far out that it does not show on any map I have seen. Bombing and fighting in 1944-1945 apparently destroyed all the bridges and the Russians have rebuilt six or seven of them. I have computed the number of paths in each case -- from 1865 until 1935 or 1944, there were always Euler paths.

L. Poinsot. Sur les polygones et les polyèdres. J. École Polytech. 4 (Cah. 10) (1810) 16 48. Pp. 28 33 give Euler paths on K_2n+1 and Euler's criterion. Discusses square with diagonals.

Endless Amusement II. 1826? Prob. 34, p. 211. Pattern of two overlapping squares has a non-crossing Euler circuit.

Th. Clausen. De linearum tertii ordinis propietatibus. Astronomische Nachrichten 21 (No. 494) (1844), col. 209 216. At the very end, he gives the five brick pattern and says that its edges cannot be drawn in three paths.

J. B. Listing. Vorstudien zur Topologie. Göttinger Studien 1 (1847) 811 875. ??NYR. Gives five brick pattern as in Clausen.

?? Nouv. Ann. Math. 8 (1849?) 74. ??NYS. Lucas says this poses the problem of finding the number of linear arrangements of a set of dominoes. [For a double N set, N = 2n, this is (2n+1)(n+1) times the number of circular arrangements, which is n²ⁿ⁺¹ times the number of Euler circuits on K_2n+1.]

É. Coupy. Solution d'un problème appartenant a la géométrie de situation, par Euler. Nouv. Ann. Math. 10 (1851) 106 119. Translation of Euler. Translator's note on p. 119 applies it to the bridges of Paris.

The Sociable. 1858. Prob. 7: Puzzle pleasure garden, pp. 288 & 303. Large maze-like garden and one is to pass over every path just once -- phrased in verse. = Book of 500 Puzzles, 1859, prob. 7, pp. 6 & 21. = Illustrated Boy's Own Treasury, 1860, prob. 49, pp. 405 & 443. In fact, if one goes straight across every intersection, one finds the path, so this is really almost a unicursal problem.

Leske. Illustriertes Spielbuch für Mädchen. 1864? Prob. 587, pp. 297 & 410: Ariadnerätsel. Three diagrams to trace with single lines. No attempt to avoid crossings.

Frank Bellew. The Art of Amusing. Carleton, NY (& Sampson Low & Co., London), 1866 [C&B list a 1871]; John Camden Hotten, London, nd [BMC & NUC say 1870] and John Grant, Edinburgh, nd [c1870 or 1866?], with slightly different pagination. 1866: pp. 269-270; 1870: p. 266. Two overlapping squares have a non-crossing Euler circuit.

Lewis Carroll. Letter of 22 Aug 1869 to Isabel Standen. Taken from: Stuart Dodgson Collingwood; The Life and Letters of Lewis Carroll; T. Fisher Unwin, London, (Dec 1898), 2nd ed., Jan 1899, p. 370: "Have you succeeded in drawing the three squares?" On pp. 369-370, the recipient is identified as Isabel Standen and she is writing Collingwood, apparently sending him the letter. Collingwood interpolates: "This puzzle was, by the way, a great favourite of his; the problem is to draw three interlaced squares without going over the same lines twice, or taking the pen off the paper". But no diagram is given.

Dudeney; Some much discussed puzzles; op. cit. in 2; 1908, quotes Collingwood, gives the diagram and continues: "This is sometimes ascribed to him [i.e. Carroll] as its originator, but I have found it in a little book published in 1835." This was probably a printing of Endless Amusement II, qv above and in Common References, though this has two interlaced squares. John Fisher; The Magic of Lewis Carroll; op. cit. in 1; pp. 58 59, says Carroll would ask for a non crossing Euler circuit, but this is not clearly stated in Collingwood. Cf Carroll-Wakeling, prob. 29: The three squares, pp. 38 & 72, which clearly states that a non-crossing circuit is wanted and notes that there is more than one solution. Cf Gardner (1964). Carroll-Gardner, pp. 52-53.

Mittenzwey. 1880. Prob. 269-279, pp. 47-48 & 98-100; 1895?: 298-308, pp. 51-52 & 100 102; 1917: 298-308, pp. 46-48 & 95-97. Straightforward unicursal patterns. The first is K₅, but one of the diagonals was missing in my copy of the 1st ed. -- the path is not to use two consecutive outer edges. The third is the 'envelope' pattern. The fourth is three overlapping squares, where the two outer squares just touch in the middle. The last is a simple maze with no dead ends and the path is not to cross itself. See also the entry for Mittenzwey in 5.E.1, below.

M. Reiss. Évaluation du nombre de combinaisons desquelles les 28 dés d'un jeu de dominos sont susceptibles d'après la règle de ce jeu. Annali di Matematica Pura ed Applicata (2) 5 (1871) 63 120. Determines the number of linear arrangements of a double 6 set of dominoes, which gives the number of Euler circuits on K₇.

L. Saalschütz. [Report of a lecture.] Schriften der Physikalisch Ökonomischen Gesellschaft zu Königsberg 16 (1876) 23 24. Sketches Euler's work, listing the seven bridges. Says that a recent railway bridge, of 1865, connecting regions B and C on Euler's diagram, can be considered within the walkable region. He shows there are 48 x 2 x 4 = 384 possible paths -- the 48 are the lists of regions visited starting with A; the 2 corresponds to reversing these lists; the 4 (= 2 x 2) corresponds to taking each of the two pairs of bridges connecting the same regions in either order, He lists the 48 sequences of regions which start at A. I wrote a program to compute Euler paths and I tested it on this situation. I find that Saalschütz has omitted two cases, leading to four sequences or 16 paths starting at A or 32 paths considering both directions. That is, his 48 should be 52 and his 384 should be 416.

Kamp. Op. cit. in 5.B. 1877. Pp. 322 327 show several unicursal problems.

No. 8 is the five brick pattern as in Clausen.

No. 10 is two overlapping squares.

No. 11 is a diagram from which one must remove some lines to leave an Eulerian figure.

C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Annalen 6 (1873) 30 32. (English is in BLW, 11 12.)

G. Tarry. Géométrie de situation: Nombre de manières distinctes de parcourir en une seule course toutes les allées d'un labyrinthe rentrant, en ne passant qu'une seule fois par chacune des allées. Comptes Rendus Assoc. Franç. Avance. Sci. 15, part 2 (1886) 49 53 & Plates I & II. General technique for the number of Euler circuits.

Lucas. RM2. 1883. Le jeu de dominos -- Dispositions rectilignes, pp. 63 77 & Note 1: Sur le jeu de dominos, p. 229.

RM4. 1894. La géométrie des réseaux et le problème des dominos, pp. 123 151.

Cites Reiss's work and says (in RM4) that it has been confirmed by Jolivald. The note in RM2 is expanded in RM4 to explain the connection between dominoes and K_2n+1. There are obviously 2 Euler circuits on K₃. He sketches Tarry's method and uses it to compute that K₅ has 88 Euler circuits and K₇ has 1299 76320. [This gives 28 42582 11840 domino rings for the double-6 set.] He says Tarry has found that K₉ has 911 52005 70212 35200.

Tom Tit, vol. 3. 1893. Le rectangle et ses diagonales, pp. 155-156. = K, no. 16: The rectangle and its diagonals, pp. 46 48. = R&A, The secret of the rectangle, p. 100. Trick solutions by folding the paper and making an arc on the back.

Hoffmann. 1893. Chap. X, no. 9: Single stroke figures, pp. 338 & 375 = Hoffmann-Hordern, pp. 230-231. Three figures, including the double crescent 'Seal of Mahomet'. Answer states Euler's condition.

Dudeney. The shipman's puzzle. London Mag. 9 (No. 49) (Aug 1902) 88 89 & 9 (No. 50) (Sep 1902) 219 (= CP, prob. 18, pp. 40 41 & 173). Number of Euler circuits on K₅.

Benson. 1904. A geometrical problem, p. 255. Seal of Mahomet.

William F. White. A Scrap Book of Elementary Mathematics. Open Court, 1908. [The 4th ed., 1942, is identical in content and pagination, omitting only the Frontispiece and the publisher's catalogue.] Bridges and isles, figure tracing, unicursal signatures, labyrinths, pp. 170 179. On p. 174, he gives the five brick puzzle, asking for a route along its edges.

Dudeney. Perplexities: No. 147: An old three line puzzle. Strand Magazine 46 (Jul 1913) 110 & (Aug 1913) 221. c= AM, prob. 239: A juvenile puzzle, pp. 68 69 & 197. Five brick form to be drawn or rubbed out on a board in three strokes. Either way requires doing two lines at once, either by folding the paper as you draw or using two fingers to rub out two lines at once. "I believe Houdin, the conjurer, was fond of showing this to his child friends, but it was invented before his time -- perhaps in the Stone Age."

Loyd. Problem of the bridges. Cyclopedia, 1914, pp. 155 & 359 360. = MPSL1, prob. 28, pp. 26 27 & 130 131. Eight bridges. Asks for number of routes.

Loyd. Puzzle of the letter carrier's route. Cyclopedia, 1914, pp 243 & 372. Asks for a circuit on a 3 x 4 array with a minimal length of repeated path.

Dudeney. AM. 1917.

Prob. 242: The tube inspector's puzzle, pp. 69 & 198. Minimal route on a 3 x 4 array.

Prob. 261: The monk and the bridges, pp. 75-76 & 202-203. River with one island. Four bridges from island, two to each side of the river, and another bridge over the river. How many Euler paths from a given side of the river to the other? Answer:  16.

Collins. Book of Puzzles. 1927. The fly on the octahedron, pp. 105-108. Asserts there are 1488 Euler circuits on the edges of an octahedron. He counts the reverse as a separate circuit.

Harry Houdini [pseud. of Ehrich Weiss] Houdini's Book of Magic. 1927 (??NYS); Pinnacle Books, NY, 1976, p. 19: Can you draw this? Take a square inscribed in a circle and draw both diagonals. "The idea is to draw the figure without taking your pencil off the paper and without retracing or crossing a line. There is a trick to it, but it can be done. The trick in drawing the figure is to fold the paper once and draw a straight line between the folded halves; then, not removing your pencil, unfold the paper. You will find that you have drawn two straight lines with one stroke. The rest is simple." This perplexed me for some time, but I believe the idea is that holding the pencil between the two parts of the folded sheet and moving the pencil parallel to the fold, one can draw a line, parallel to the fold, on each part.

Loyd Jr. SLAHP. 1928. Pp. 7 8. Discusses what he calls the "Five brick puzzle", the common pattern of five rectangles in a rectangle. He says that the object was to draw the lines in four strokes -- which is easily done -- but that it was commonly misprinted as three strokes, which he managed to do by folding the paper. He says "a similar puzzle ... some ten or fifteen years ago" asked for a path crossing each of the 16 walls once, which is also impossible.

The Bile Beans Puzzle Book. 1933.

No. 32. Draw the triangular array of three on an edge without crossing.

No. 36. Draw the five-brick pattern in three lines. Folds paper and draws two lines at once.

R. Ripley. Believe It Or Not! Book 2. (Simon & Schuster, 1931); Pocket Books, NY, 1948, pp. 70 71. = Omnibus Believe It Or Not! Stanley Paul, London, nd [c1935?], p. 270. Gives the five brick problem of drawing a path crossing each wall once, with the trick solution having the path going along a wall. Asserts "This unicursal problem was solved thus by the great Euler himself." and cites the Euler paper above!!

Meyer. Big Fun Book. 1940.

Tryangle, pp. 98 & 731. Triangle subdivided into triangles, with three small triangles along each edge. Draw an Euler circuit without crossings.

Cutting the walls, pp. 637 & 794. Five-brick problem. Solution has line crossing through a vertex.

Ern Shaw. The Pocket Brains Trust - No. 2. W. H. Allen, London, nd but inscribed 1944. Prob. 29: Five bricks teaser, pp. 10 & 39.

Leeming. 1946. Chap. 6, prob. 2: Through the walls, pp. 70 & 184. Five brick puzzle, with trick solution having the path go through an intersection.

John Paul Adams. We Dare You to Solve This!. Op. cit. in 5.C. 1957? Prob. 49: In just one line, pp. 30 & 48-49. Five-brick puzzle, with answer having the path going along a wall, as in Ripley. Asserts Euler invented this solution.

Gibson. Op. cit. in 4.A.1.a. 1963. Pp. 70 & 75: The "impossible" diagram. Same as Tom Tit.

Gardner. SA (Apr 1964) = 6th Book, chap. 10. Says Carroll knew that a planar Eulerian graph could be drawn without crossings. Gives a method of O'Beirne for doing this -- two colour the regions and then make a path which separates the colours into simply connected regions.

Ripley's Puzzles and Games. 1966. P. 39. Euler paths on the 'envelope', i.e. a rectangle with its diagonals drawn and an extra connection between the top corners, looking like an unfolded envelope. Asserts the envelope has 50 solutions, but it is not clear if the central crossing is a further vertex. I did this by hand but did not get 50, so I wrote a program to count Euler paths. If the central crossing is not a vertex, then I find 44 paths from one of the odd vertices to the other, and of course 44 going the other way -- and I had found this number by hand. However, if the central crossing is a vertex, then my hand solution omitted some cases and the computer found 120 paths from one odd vertex to the other.

Pp. 40-43 give many problems of drawing non-crossing Euler paths or circuits.

W. Wynne Willson. How to abolish cross roads. MTg 42 (Spring 1968) 56 59. Euler circuit of a planar graph can be made without crossings.

[Henry] Joseph & Lenore Scott. Master Mind Brain Teasers. Tempo (Grosset & Dunlap), NY, 1973 (& 1978?? -- both dates are given -- I'm presuming the 1978 is a 2nd ptg or a reissue under a different imprint??). One line/no crossing, pp. 85-86. Non-crossing Euler circuits on the triangular array of side 3 and non-crossing Euler paths on the 'envelope' -- cf under Ripley's, above. Asserts the envelope has 50 solutions. I adapted the program mentioned above to count the number of non-crossing Euler paths -- one must rearrange the first case as a planar graph -- and there are 16 in the first case and 26 in the second case. Taking the reversals doubles these numbers so it is possible that the Scotts meant the second case and missed one path and its reversal.

David Singmaster, proposer; Jerrold W. Grossman & E. M. Reingold, solvers. Problem E2897 -- An Eulerian circuit with no crossings. AMM 88:7 (Aug 1981) 537-538 & 90:4 (Apr 1983) 287-288. A planar Eulerian graph can be drawn with no crossings. Solution cites some previous work.

Anon. [probably Will Shortz ??check with Shortz]. The impossible file. No. 2: In just one line. Games (Apr 1986) 34 & 64 & (Jul 1986) 64. Five brick pattern -- draw a line crossing each wall once. Says it appeared in a 1921 newspaper [perhaps by Loyd Jr??]. Gives the 1921 solution where the path crosses a corner, hence two walls at once. Also gives a solution with the path going along a wall. In the July issue, Mark Kantrowitz gives a solution by folding over a corner and also a solution on a torus.

Marcia Ascher. Graphs in cultures: A study in ethnomathematics. HM 15 (1988) 201 227. Discusses the history of Eulerian circuits and non-crossing versions and then exposits many forms of the idea in many cultures.

Marcia Ascher. Ethnomathematics. Op. cit. in 4.B.10. 1991. Chapter Two: Tracing graphs in the sand, pp. 30-65. Sketches the history of Eulerian graphs with some interesting references -- ??NYS. Describes graph tracing in three cultures: the Bushoong and the Tshokwe of central Africa and the Malekula of Vanuatu (ex-New Hebrides). Extensive references to the ethnographic literature.