Sources page biographical material

5.E.1. MAZES
This section is mainly concerned with the theory. The history of mazes is sketched first, with references to more detailed sources. There is even a journal, Caerdroia (53 Thundersley Grove, Thundersley, Essex, SS7 3EB, England), devoted to mazes and labyrinths, mostly concentrating on the history. It is an annual, began in 1980 and issue 31 appeared in 2000.

Mazes are considered under Euler Circuits, since the method of Euler Circuits is often used to find an algorithm. However, some mazes are better treated as Hamiltonian Circuits -- see 5.F.2.

A maze can be considered as a graph formed by the nodes and paths -- the path graph. For the usual planar maze, one can also look at the graph formed by the walls -- the wall graph, which is a kind of dual to the path graph. In later mazes, the walls do not form a connected whole, and an isolated part of the wall appears as a region or 'face' in the path graph. Such isolated bits of walling are sometimes called islands, but they are the same as the components of the wall graph, with the outer wall being one component, so the number of components is one more than the number of islands. The 'hand-on-wall' method will solve a maze if and only if the goals are adjacent to walls in the component of the outer wall.

A 'ring maze' is a plate with holes and raised areas with an open ring which must be removed by moving it from hole to hole. I have put these in 11.K.5 as they are a kind of mechanical or topological puzzle, though there are versions with a simple two legged spacer.

HISTORICAL SOURCES
W. H. Matthews. Mazes & Labyrinths: A General Account of Their History and Developments. Longmans, Green and Co., London, 1922. = Mazes and Labyrinths: Their History and Development. Dover, 1970. (21 pages of references.) [For more about the book and the author, see: Zeta Estes; My Father, W. H. Matthews; Caerdroia (1990) 6-8.]

Walter Shepherd. For Amazement Only. Penguin, 1942; Let's go amazing, pp. 5-12. Revised as: Mazes and Labyrinths -- A Book of Puzzles. Dover, 1961; Let's go a mazing, pp. v xi. (Only a few minor changes are made in the text.) Sketch of the history.

Sven Bergling invented the rolling ball labyrinth puzzle/game and they began being produced in 1946. [Kenneth Wells; Wooden Puzzles and Games; David & Charles, Newton Abbot, 1983, p. 114.]

Walter Shepherd. Big Book of Mazes and Labyrinths. Dover, 1973, More amazement, pp. vii-x. Extends the historical sketch in his previous book, arguing that mazes with multiple choices perhaps derive from Iron Age hill forts whose entrances were designed to confuse an enemy.

Janet Bord. Mazes and Labyrinths of the World. Latimer, London, 1976. (Extensively illustrated.)

Nigel Pennick. Mazes and Labyrinths. Robert Hale, London, 1990.

Adrian Fisher [& Georg Gerster (photographer)]. The Art of the Maze. Weidenfeld and Nicolson, London, 1990. (Also as: Labyrinth; Solving the Riddle of the Maze; Harmony (Crown Publishers), NY, 1990.) Origins and History occupies pp. 11-56, but he also describes many recent developments and innovations. He has convenient tables of early examples.

Adrian Fisher & Diana Kingham. Mazes. Shire Album 264. Shire, Aylesbury, 1991.

Adrian Fisher & Jeff Saward. The British Maze Guide. Minotaur Designs, St. Alban's, 1991.

┌────────────────────────────────────────────┐

│ │

│ ┌──────────────────────────────────────┐ │

│ │ │ │

│ │ ┌────────────────────────────────┐ │ │

│ │ │ │ │ │

│ │ │ ┌──────────────────────────┐ │ │ │

│ │ │ │ │ │ │ │

│ │ │ │ ┌────────────────────┐ │ │ │ │

│ │ │ │ │ │ │ │ │ │

│ │ │ │ │ ┌──────────────┐ │ │ │ │ │

│ │ │ │ │ │ │ │ │ │ │ │

│ │ │ │ │ │ ┌────────┐ │ │ │ │ │ │

│ │ │ │ │ │ │ │ │ │ │ │ │ │

│ │ │ │ │ │ │ ┌──┐ │ │ │ │ │ │ │

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

│ │ │ │ │ │ ││ │ │ │ │ │ │

│ │ │ │ └─────┘ │ └─────┘ │ │ │ │ │

│ │ │ │ │ │ │ │ │ │

│ │ │ └───────────┼───────────┘ │ │ │ │

│ │ │ │ │ │ │ │

│ │ └───────────┐ │ ┌───────────┘ │ │ │

│ │ │ │ │ │ │ │

│ └──────────── │ │ │ ────────────┘ │ │

│ │ │ │ │ │

└─────────────────┤ │ └─────────────────┘ │

│ │ │

│ ├───────────────────────┘



HISTORICAL SKETCH
Up to about the 16C, all mazes were unicursal, i.e. with no decision points. The word labyrinth is sometimes used to distinguish unicursal mazes from others, but this distinction is not made consistently. Until about 1000, all mazes were of the classical 'Cretan' seven-ring type shown above. (However, see Shepherd's point in his 1973 book, above.) The oldest examples are rock carvings, the earliest being perhaps that in the Tomba del Labirinto at Luzzanas, Sardinia, c 2000 [Fisher, pp. 12, 25, 26, with photo on p. 12]. (In fact, Luzzanas is a local name for an uninhabited area of fields, so does not appear on any ordinary map. It is near Benetutti. See my A Mathematical Gazetteer or Mazing in Sardinia (Caerdroia 30 (1999) 17-21). Jeff Saward writes that current archaeological feeling is that the maze is Roman, though the cave is probably c-2000.) On pottery, there are labyrinths on fragments, c 1300, from Tell Rif'at, Syria [the first photos of this appeared in [Caerdroia 30 (2000) 54-55]), and on tablets, c 1200, from Pylos. Fisher [p. 26] lists the early examples. Staffen Lundán; The labyrinth in the Mediterranean; Caerdroia 27 (1996) 28-54, catalogues all known 'Cretan' labyrinths from prehistory to the end of antiquity, c250, excluding the Roman 'spoked' form. All these probably had some mystical significance about the difficulty of reaching a goal, often with substantial mythology -- e.g. Theseus in the Labyrinth or, later, the Route to Jerusalem.

Roman mosaics were unicursal but essentially used the Cretan form four times over in the four corners. Lundán, above, calls these 'spoked'. Most of the extant examples are 2C 4C, but some BC examples are known -- the earliest seems to be c-110 at Selinunte, Sicily. Fisher [pp. 36-37] lists all surviving examples. Saward says the earliest Roman example is at Pompeii, so  79.

In the medieval period, the Christians developed a quite different unicursal maze. See Fisher [pp. 60-67] for detailed comparison of this form with the Roman and Cretan forms. The earliest large Christian example is the Chemin de Jerusalem of 1235 on the floor of Chartres Cathedral. Fisher [pp. 41 & 48] lists early and later Christian examples.

The legendary Rosamund's Bower was located in Woodstock Park, Oxfordshire, and its purported site is marked by a well and fountain. It was some sort of maze to conceal Rosamund Clifford, the mistress of Henry II (1133 1189), from the Queen, Eleanor of Aquitaine. Legend says that about 1176, Eleanor managed to solve the maze and confronted Rosamund with the choice of a dagger or poison -- she drank the poison and Henry never smiled again. [Fisher, p. 105]. Historically, Henry had imprisoned Eleanor for fomenting rebellion by her sons and Rosamund was his acknowledged mistress. Rosamund probably spent her last days at a nunnery in Godstow, near Oxford. The legend of the bower dates from the 14C and her murder is a later addition [Collins, Book of Puzzles, 1927, p. 121.] In the 19C, many puzzle collections had a maze called Rosamund's Bower.

The earliest record of a hedge maze is of one destroyed in a siege of Paris in 1431.

Non-unicursal mazes and islands in the wall graph start to appear in the late 16C. Matthews [p. 96] says that: "A simple "interrupted-circle" type of labyrinth was adopted as a heraldic device by Gonzalo Perez, a Spanish ecclesiastic ... and published ... in 1566 ..." in his translation of the Odyssey. Matthews doesn't show this, but he then [pp. 96-97] describes and illustrates a simple maze used as a device by Bois-dofin de Laval, Archbishop of Embrum. He copies it from Claude Paradin; Devises Héroiques et Emblèmes of the early 17C. It has four entrances and possibly three goals, with walls having 8 components, two being part of the outer wall. The central goals is accessible from two of the entrances, but the two minor goals are each accessible from just one of the other entrances. Presumably this sort of thing is what Matthews meant as an "interrupted circle".

However, Saward has found a mid 15C anonymous English poem, The Assembly of Ladies, which describes the efforts of a group of ladies to reach the centre of a maze, which, as he observes, implies there must be some choices involved.

[Matthews, p. 114] has three examples from a book by Androuet du Cerceau; Les Plus Excellents Bastiments de France of 1576. Fig. 82 was in the gardens at Charleval and has four entrances, only one of which goes to the central goal. There are four minor goals. The N entrance connects to the NE and SE goals, with several dead ends. The E entrance is a dead end. The S entrance goes to the SW goal. The W entrance goes to the central goal, but the NW goal is on an island, though 'left-hand-on-wall' goes past it. Figs. 83 and 84 are essentially identical and seem to be corruptions of unicursal examples so that most of the maze is bypassed. In fig. 84, one has to walk around to the back of the maze to find the correct entrance to get to the central goal, which is an interesting idea. A small internal change in both cases and moving the entrances converts them to a standard unicursal pattern.

Matthews' Chap. XIII [pp. 100-109] is on floral mazes and reproduces some from Jan Vredeman De Vries; Hortorum Viridariorumque Formae; Antwerp, 1583. Fig. 74 is one of these and has two components and a short dead-end, but the 'hand-on-wall' rule solves it. Fig. 73 is another of De Vries's, but it is not all shown. It appears to have two entrances and there is certainly a decision point by the far gate, but one route goes to the apparent exit at the bottom of the page. There is a small dead end near the central goal. Fig. 78 shows a maze from a 17C manuscript book in the Harley Manuscripts at the BL, identified on p. 224 as BM Harl. 5308 (71, a, 12). This has two components with the central goal in the inner component, so the 'hand-on-wall' rule fails, but it brings you within sight of the centre and Matthews describes it as unicursal! Fig. 79 is from Adam Islip; The Orchard and the Garden, compiled from continental sources and published in 1602. It has 5 components, but four of these are small enclosures which could be considered as minor goals, especially if they had seats in them. The 'hand-on-wall' rule gets to the central goal. There is a lengthy dead end which goes to two of the inner islands. Fig. 80 is from a Dutch book: J. Commelyn; Nederlantze Hesperides of 1676. It has two components, a central goal and four minor goals. The 'hand-on-wall' gets you to the centre and passes two minor goals. One minor goal is on a dead end so 'left-hand-on-wall' gets to it, but 'right-hand-on-wall' does not. The fourth minor goal is on the island.

At Versailles, c1675, André Le Nôtre built a Garden Maze, but the objective was to visit, in correct order, 40 fountains based on Aesop's Fables. Each node of the maze had at least one fountain. Some fountains were not at path junctions, but one can consider these as nodes of degree two. This is an early example of a Hamiltonian problem, except that one fountain was located at the end of a short dead end. [Fisher, pp. 49, 79, 130 & 144-145, with contemporary map on p. 144. Fisher says there are 39 fountains, and the map has 40. Close examination shows that the map counts two statues at the entrance but omits to count a fountain between numbers 37 and 38. Matthews, pp. 117 121, says it was built by J. Hardouin-Mansart and his map has 39 fountains.] It has a main entrance and exit but there is another exit, so the perimeter wall already has three components, and there are 14 other components. Sadly, it was destroyed in 1775.

Several other mazes, of increasing complexity, occur in the second half of the 17C [Matthews, figs. 93-109, opp. p. 120 - p. 127]. Several of these could be from 20C maze books. Fig. 94, designed for Chantilly by Le Nôtre, is surprisingly modern in that there are eight paths spiralling to the centre. The entrance path takes you directly to the centre, so the real problem is getting back out! One of the mazes presently at Longleat has this same feature.

The Hampton Court Maze, planted c1690, is the oldest extant hedge maze and one of the earliest puzzle mazes. ([Christopher Turner; Hampton Court, Richmond and Kew Step by Step; (As part of: Outer London Step by Step, Faber, 1986); Revised and published in sections, Faber, 1987, p. 16] says the present shape was laid out in 1714, replacing an earlier circular shape, but I haven't seen this stated elsewhere.) Matthews [p. 128] says it probably replaced an older maze. It has dead ends and one island, i.e. the graph has two components, though the 'hand on wall' rule will solve it.

The second Earl Stanhope (1714-1786) is believed to be the first to design mazes with the goal (at the centre) surrounded by an island, so that the 'hand on wall' rule will not solve it. It has seven components and only a few short dead ends.. The fourth Earl planted one of these at Chevening, Kent, in c1820 and it is extant though not open to the public. [Fisher, p. 71, with photo on p. 72 and diagram on p. 73.] However, investigation in Matthews revealed the earlier examples above. Further Bernhard Wiezorke (below at 2001) has found a hedge maze in Germany, dating from c1730, which is not solved by the 'hand on wall' rule. This maze has 12 components.

In 1973, Stuart Landsborough, an Englishman settled at Wanaka, South Island, New Zealand, began building his Great Maze. This was the first of the board mazes designed by Landsborough which were immensely popular in Japan. Over 200 were built in 1984-1987, with 20 designed by Landsborough. Many of these were three dimensional -- see below. About 60 have been demolished since then. [Fisher, pp. 78 79 & 118-121 has 6 colour photos, pp. 156-157 lists Landsborough's designs.]

If Minos' labyrinth ever really existed, it may have been three dimensional and there may have been garden examples with overbridges, but I don't know of any evidence for such early three dimensional mazes. Lewis Carroll drew mazes which had paths that crossed over others making a simple three dimensional maze, in his Mischmasch of c1860, see below. John Fisher [The Magic of Lewis Carroll; (Nelson, 1973), Penguin, 1975, pp. 19-20] gives this and another example. Are there earlier examples? Boothroyd & Conway, 1959, seems to be the earliest cubical maze. Much more complex versions were developed by Larry Evans from about 1970 and published in a series of books, starting with 3-Dimensional Mazes (Troubador Press, San Francisco, 1976). His 3 Dimensional Maze Art (Troubador, 1980) sketches some general history of the maze and describes his development of pictures of three dimensional mazes. The first actual three dimensional maze seems to be Greg Bright's 1978 maze at Longleat House, Warminster. [Fisher, pp. 74, 76, 94-95 & 152-153, with colour photos on pp. 94-95.] Since then, Greg Bright, Adrian Fisher, Randoll Coate, Stuart Landsborough and others have made many innovations. Bright seems to have originated the use of colour in mazes c1980 and Fisher has extensively developed the idea. [Fisher, pp. 73-79.]
Abu‘l-Rayhan Al Biruni (= ’Abû-alraihân [the h should have an underdot] Muhammad ibn ’Ahmad [the h should have an underdot] Albêrûnî). India. c1030. Chapter XXX. IN: Al Beruni's India, trans. by E. C. Sachau, 2 vols., London, 1888, vol. 1, pp. 306-307 (= p. 158 of the Arabic ed., ??NYS). In describing a story from the fifth and sixth books of the Ramayana, he says that the demon Ravana made a labyrinthine fortress, which in Muslim countries "is called Yâvana-koti, which has been frequently explained as Rome." He then gives "the plan of the labyrinthine fortress", which is the classical Cretan seven-ring form. Sachau's notes do not indicate whether this plan is actually in the Ramayana, which dates from perhaps -300.

Pliny. Natural History. c77. Book 36, chap. 19. This gives a brief description of boys playing on a pavement where a thousand steps are contained in a small space. This has generally been interpreted as referring to a maze, but it is obviously pretty vague. See: Michael Behrend; Julian and Troy names; Caerdroia 27 (1996) 18-22, esp. note 5 on p. 22.

Pacioli. De Viribus. c1500. Part II: Cap. (C)XVII. Do(cumento). de saper fare illa berinto con diligentia secondo Vergilio, f. 223v = Peirani 307-308. A sheet (or page) of the MS has been lost. Cites Vergil, Æneid, part six, for the story of Pasiphæ and the Minotaur, but the rest is then lost.

Sebastiano Serlio. Architettura, 5 books, 1537-1547. The separate books had several editions before they were first published together in 1584. The material of interest is in Book IV which shows two unicursal mazes for gardens. I have seen the following.

Tutte l'Opere d'Architetture et Prospetiva, .... Giacomo de'Franceschi, Venice, 1619; facsimile by Gregg Press, Ridgewood, New Jersey, 1964. F. 199r shows the designs and f. 197v has some text, partly illegible in my photocopy. [Cf Caerdroia 30 (1999) 15.]

Sebastiano Serlio on Architecture Volume One Books I-V of 'Tutte l'Opere d'Architettura et Prospetiva'. Translated and edited by Vaughan Hart and Peter Hicks. Yale Univ. Press, New Haven, 1996. P. 388 shows the designs and p. 389 has the text, saying these 'are for the compartition of gardens'. The sidenotes state that these pages are ff. LXXVr and LXXIIIIr of the 3rd ed. of 1544 and ff. 198v-199r and 197v-198r of the 1618/19 ed.

William Shakespeare. A Midsummer Night's Dream. c1610. Act II, scene I, lines 98-100: "The nine men's morris is fill'd up with mud, And the quaint mazes in the wanton green For lack of tread are undistinguishable." Fiske 126 opines that the latter two lines may indicate that the board was made in the turf, though he admits that they may refer just to dancers' tracks, but to me it clearly refers to turf mazes.

John Cooke. Greene's Tu Quoque; or the Cittie Gallant; a Play of Much Humour. 1614. ??NYS -- quoted by Matthews, p. 135. A challenge to a duel is given by Spendall to Staines.

Staines. I accept it ; the meeting place?

Spendall. Beyond the maze in Tuttle.

This refers to a maze in Tothill Fields, close to Westminster Abbey.

Lewis Carroll. Untitled maze. In: Mischmasch, the last of his youthful MS magazines, with entries from 1855 to 1862. Transcribed version in: The Rectory Umbrella and Mischmasch; Cassell, 1932; Dover, 1971; p. 165 of the Dover ed. John Fisher [The Magic of Lewis Carroll; (Nelson, 1973), Penguin, 1975, pp. 19-20] gives this and another example. Cf Carroll-Wakeling, prob. 35: An amazing maze, pp. 46-47 & 75 and Carroll-Gardner, pp. 80-81 for the Mischmasch example. I don't find the other example elsewhere, but it was for Georgina "Ina" Watson, so probably c1870.

Mittenzwey. 1880. Prob. 281, pp. 50 & 100; 1895?: 310, pp. 53-54 & 102; 1917: 310, pp. 49 & 97. The garden of a French place has a maze with 31 points to see. Find a path past all of them with no repeated edges and no crossings. The pattern is clearly based on the Versailles maze of c1675 mentioned in the Historical Sketch above, but I don't recall the additional feature of no crossings occurring before.

C. Wiener. Ueber eine Aufgabe aus der Geometria situs. Math. Annalen 6 (1873) 29 30. An algorithm for solving a maze. BLW asserts this is very complicated, but it doesn't look too bad.

M. Trémaux. Algorithm. Described in Lucas, RM1, 1891, pp. 47 51. ??check 1882 ed. BLW assert Lucas' description is faulty. Also described in MRE, 1st ed., 1892, pp. 130 131; 3rd ed., 1896, pp. 155-156; 4th ed., 1905, pp. 175-176 is vague; 5th-10th ed., 1911 1922, 183; 11th ed., 1939, pp. 255 256 (taken from Lucas); (12th ed. describes Tarry's algorithm instead) and in Dudeney, AM, p. 135 (= Mazes, and how to thread them, Strand Mag. 37 (No. 220) (Apr 1909) 442 448, esp. 446 447).

G. Tarry. Le problème des labyrinthes. Nouv. Annales de Math. (3) 4 (1895) 187 190. ??NYR

Collins. Book of Puzzles. 1927. How to thread any maze, pp. 122-124. Discusses right hand rule and its failure, then Trémaux's method.

M. R. Boothroyd & J. H. Conway. Problems drive, 1959. Eureka 22 (Oct 1959) 15-17 & 22-23. No. 2. 5 x 5 x 5 cubical maze. Get from a corner to an antipodal corner in a minimal number of steps.

Anneke Treep. Mazes... How to get out! (part I). CFF 37 (Jun 1995) 18-21. Based on her MSc thesis at Univ. of Twente. Notes that there has been very little systematic study. Surveys the algorithms of Tarry, Trémaux, Rosenstiehl. Rosenstiehl is greedy on new edges, Trémaux is greedy on new nodes and Trémaux is a hybrid of these. ??-oops-check. Studies probabilities of various routes and the expected traversal time. When the maze graph is a tree, the methods are equivalent and the expected traversal time is the number of edges.

Bernhard Wiezorke. Puzzles und Brainteasers. OR News, Ausgabe 13 (Nov 2001) 52-54. This reports his discovery of a hedge maze in Germany -- the first he knew of. It is in Altjessnitz, near Dessau in Sachsen-Anhalt. (My atlas doesn't show such a place, but Jessnitz is about 10km south of Dessau.) This maze dates from 1720 and has 12 components, with the goal completely separated from the outside so that the 'hand on wall' rule does not solve it. Torsten Silke later told Wiezorke of two other hedge mazes in Germany. One, in Probststeierhagen, Schleswig-Holstein, about 12km NE of Kiel, is in the grounds of the restaurant Zum Irrgarten (At the Labyrinth) and is an early 20C copy of the Altjessnitz example. The other, in Kleinwelka, Sachsen, about 50km NE of Dresden, was made in 1992 and is private. Though it has 17 components, the 'hand on wall' method will solve it. He gives plans of both mazes. He discusses the Seven Bridges of Königsberg, giving a B&W print of the 1641 plan of the city mentioned at the beginning of Section 5.E -- he has sent me a colour version of it. He also describes Tremaux's solution method.
5.E.2. MEMORY WHEELS = CHAIN CODES
These are cycles of 2ⁿ 0s and 1s such that each n tuple of 0s and 1s appears just once. They are sometimes called De Bruijn sequences, but they have now been traced back to the late 19C. An example for n = 3 is 00010111.
Émile Baudot. 1884. Used the code for 2⁵ in telegraphy. ??NYS -- mentioned by Stein.

A. de Rivière, proposer; C. Flye Sainte-Marie, solver. Question no. 58. L'Intermédiare des Mathématiciens 1 (1894) 19-20 & 107-110. ??NYS -- described in Ralston and Fredricksen (but he gives no. 48 at one point). Deals with the general problem of a cycle of kⁿ symbols such that every n tuple of the k basic symbols occurs just once. Gives the graphical method and shows that such cycles always exist and there are k!^g(n)/ kⁿ of them, where g(n) = k^n 1. This work was unknown to the following authors until about 1975.

N. G. de Bruijn. A combinatorial problem. Nederl. Akad. Wetensch. Proc. 49 (1946) 758 764. ??NYS -- described in Ralston and Fredricksen. Gives the graphical method for finding examples and finds there are 2^f(n) solutions, where f(n) = 2^n-1 - n.

I. J. Good. Normal recurring decimals. J. London Math. Soc. 21 (1946) 167-169. ??NYS -- described in Ralston and Fredricksen. Shows there are solutions but doesn't get the number.

R. L. Goodstein. Note 2590: A permutation problem. MG 40 (No. 331) (Feb 1956) 46 47. Obtains a kind of recurrence for consecutive n tuples.

Sherman K. Stein. Mathematics: The Man made Universe. Freeman, 1963. Chap. 9: Memory wheels. c= The mathematician as explorer, SA (May 1961) 149 158. Surveys the topic. Cites the c1000 Sanskrit word: yamátárájabhánasalagám used as the mnemonic for 01110100(01) giving all triples of short and long beats in Sanskrit poetry and music. Describes the many reinventions, including Baudot (1882), ??NYS, and the work of Good (1946), ??NYS, and de Bruijn (1946), ??NYS. 15 references.

R. L. Goodstein. A generalized permutation problem. MG 54 (No. 389) (Oct 1970) 266 267. Extends his 1956 note to find a cycle of aⁿ symbols such that the n tuples are distinct.

Anthony Ralston. De Bruijn sequences -- A model example of the interaction of discrete mathematics and computer science. MM 55 (1982) 131 143 & cover. Deals with the general problem of cycles of kⁿ symbols such that every n tuple of the k basic symbols occurs just once. Discusses the history and various proofs and algorithms which show that such cycles always exist. 27 references.

Harold Fredricksen. A survey of full length nonlinear shift register cycle algorithms. SIAM Review 24:2 (Apr 1982) 195-221. Mostly about their properties and their generation, but includes a discussion of the door lock connection, a mention of using the 2³ case as a switch for three lights, and gives a good history. The door lock connection is that certain push button door locks will open when a four digit code is entered, but they open if the last four buttons pressed are the correct code, so using a chain code reduces the number of button pushes required by a burglar to 1/4 of the number required if he tries all four digit combinations. 58 references.

At G4G2, 1996, Persi Diaconis spoke about applications of the chain code in magic and mentioned uses in repeated measurement designs, random number generators, robot location, door locks, DNA comparison.

They were first used in card tricks by Charles T. Jordan in 1910. Diaconis' example had a deck of cards which were cut and then five consecutive cards were dealt to five people in a row. He then said he would determine what cards they had, but first he needed some help so he asked those with red cards to step forward. The position of the red cards gives the location of the five cards in a cycle of 32 (which was the size of the deck)! Further, there are simple recurrences for the sequence so it is fairly easy to determine the location. One can code the binary quintuples to give the suit and value of the first card and then use the succeeding quintuples for the succeeding cards.

Long versions of the chain code are printed on factory floors so that a robot can read it and locate itself.

In Jan 2000, I discussed the Sanskrit chain code with a Sanskrit scholar, Dominik Wujastyk, who said that there is no known Sanskrit source for it. He has asked numerous pandits who did not know of it and he said there is is a forthcoming paper on it, but that it did not locate any Sanskrit source.