Sequential Movement Puzzles

Mechanical puzzles in the Sequential Movement class are those that can be solved by progressing from some initial state to some goal state using sequences of moves executed in the proper order. It is important that at any moment, the set of possible legal next moves is easily enumerable, finite (typically small), and apparent. This distinguishes this class from trick disassembly puzzles, where though the solution might indeed require a specific sequence of moves, the available moves are typically not apparent, and from tanglements, where though all possible movements are visible, movements are "analog" and legal or meaningful moves are not easily enumerated. Typically, the options available at any moment are constrained and depend on the current state of the puzzle, as determined by the history of past moves made since the initial state. This distinguishes this class from an assembly or packing puzzle, where any piece can typically be manipulated at any time.

There are several subclasses. My sections on the subclasses can be accessed from this central page via the menu below.

 Peg Solitaire and Jumping Puzzles Sliding Piece Twisty Polyhedra 3D Sliding Piece Route-Finding Gray Code River Crossing, Measuring, and Weighing Puzzles

Gray Code Puzzles

Several puzzles can be solved using some variation of a Gray code (named after the Bell Labs researcher Frank Gray, who patented a vacuum tube using them in 1953). A Gray code is a sequence of binary numbers in which any adjacent numbers are different in only one bit.

 If you count from one to seven in binary, you'll see that more than one bit changes at a time, so simply counting does not follow a Gray code... ``` 2 1 0 <-- column number 4 2 1 <-- bit value in decimal (bits from left to right 2^2, 2^1, 2^0) 0) 0 0 0 1) 0 0 1 <-- so far so good, only the 1 bit (column 0) changed 2) 0 1 0 <-- uh oh, both the 1 bit and the 2 bit changed 3) 0 1 1 4) 1 0 0 <-- between 3 and 4, all 3 columns changed! 5) 1 0 1 6) 1 1 0 7) 1 1 1 ``` Here is a 3-bit Gray Code: ``` 2 1 0 <-- column number 4 2 1 <-- bit value in decimal (bits from left to right 2^2, 2^1, 2^0) 0) 0 0 0 1) 0 0 1 3) 0 1 1 <-- change only the 2 bit 2) 0 1 0 <-- now change the 1 bit 6) 1 1 0 7) 1 1 1 5) 1 0 1 4) 1 0 0 ``` Notice that the Gray code still encompasses all the numbers, just not in normal counting order.

 One classic of this type is the Patience puzzle, which I discuss in my Tanglements section. Another is the Towers of Hanoi [Wikipedia entry]. The Towers of Hanoi puzzle was invented by the French mathematician Edouard Lucas (1842-1891) in 1883. Lucas was born in Amiens, France in 1842. He marketed the Towers puzzle under the nickname N. Claus de Siam, an anagram of Lucas d'Amiens. The simplest version of the Towers puzzle comprises 3 pegs or towers, and a set of n discs in graduated sizes, having central holes such that they can be stacked in size order from largest on the bottom to smallest on the top, on one of the pegs. This peg is the starting peg. The objective is to transfer the pile of discs to another peg, moving one disc at a time. Only the top disc from any peg can be moved, and it can only be moved to either any empty peg, or a peg where the top disc is larger than the disc to be moved onto it - i.e. you can never put a larger disc on top of a smaller disc. The puzzle is usually supplied with n = from 6 to 10 discs. The number of moves required to solve a tower of n discs is 2n-1, so for n=1,2,3...10 discs, you will need to perform 1,3,7,15,31, 63, 127, 255, 511, or 1023 moves, without errors. The Towers design has appeared in many forms. Here are a couple of patents I've found: 303946 - Ohlert 1884, also D135848 - Drueke 1943. Check out a Lego robot that can solve the Towers of Hanoi problem at J.P. Brown's site. Adams' Pyramid Journet's Brahma Craze ( U.S. Patent 2738979 - Dalton 1956 ) King Tut's Pyramid for the Puzzle Master (by Milton Bradley) Panex (Gold version) designed by Toshio Akanuma, manufactured by TRICKS Co., Ltd. of Tokyo, Japan. Panex is similar to the Towers of Hanoi, but enforces different restrictions on the movement of the pieces. The pieces ride in tracks rather than on pegs - there are three tracks, joined at the top by a single cross-track, which provides a "parking space" at the top of each track. Pieces cannot pass each other in the cross-track - so to move a piece from one track to another along the cross-track, all other pieces must be out of the way, on one of the tracks. There are two stacks of pieces rather than one - the puzzle has two goals - the first is to transfer either stack to the unoccupied track, making use of the single unrestricted "parking space" at the top of the third (occupied) track. The other goal is to exchange the two stacks. As produced, Panex has ten pieces in each stack, so even without tricky move constraints, you can look forward to performing a lot of moves to solve it! In Panex, a piece can move on top of a smaller piece, but cannot move any lower on a track than where it started even if space below is unoccupied - so if you number the pieces 9 through 0 from the top down, and the underlying spaces in the track correspondingly, piece i cannot be placed any lower than space i. This restriction is mechanically enforced by the design of the puzzle. The novel constraints make the puzzle much harder than the standard Towers. On Nov. 21, 2010, Derek Kisman verified that the shortest solution for Panex (level 10) requires 31,537 moves. The next three puzzles were all designed and patented by Dr. Valery Rudenko. See www.roscreative.ru Rudenko Matryoshka [Y] Three tracks, and a stack of 7 nesting pieces. In this case, the larger piece is on the outside, so the stack is inverted, and the rule is that larger pieces can only go on top of smaller pieces. Rudenko Disc [Y] Three tracks, and a stack of 7 pieces. The goal is to move the stack of pieces to another track. Similar to Panex, because no piece can be moved further along a track than its "home" spot, indicated by the corresponding color. Rudenko Clips [Y]

 In my opinion, two of the best puzzles of this type are the Brain from Mag-Nif and SpinOut from Binary Arts, now Thinkfun. With practice, both can be solved very rapidly despite requiring a lengthy series of specific moves. Consider the Brain puzzle. The pegs are numbered 1 through 8 - peg 1 acts as the 1 bit, or column 0. Peg 2 acts as the 2 bit, or column 1. Peg 3 acts as the 4 bit, or column 2, and so forth. When a peg is pushed in towards the puzzle center, it has a value of 0; when the peg is outwards so that the corresponding flange is extended, it has a value of 1. The mechanism ensures that no peg can be moved either in or out until only the peg immediately lower than it is out and all other lower pegs are in. This is the "prime directive" for this puzzle and its relations, and can be re-stated as "No bit can toggle unless its immediate predecessor is 1 and all other predecessors are 0." The pegs must be moved following a Gray code - the sequence begins as follows: ``` 8 4 2 1 0 0 0 0 0 0 0 0 (0 0 0 0 0 0 0 0 1 (1 <-- the lowest "bit" can always be moved 0 0 0 0 0 0 1 1 (3 <-- we can now move the next peg 0 0 0 0 0 0 1 0 (2 <-- in order to advance, we must retract bit 1 0 0 0 0 0 1 1 0 (6 0 0 0 0 0 1 1 1 (7 0 0 0 0 0 1 0 1 (5 0 0 0 0 0 1 0 0 (4 0 0 0 0 1 1 0 0 (12 0 0 0 0 1 1 0 1 (13 0 0 0 0 1 1 1 1 (15 0 0 0 0 1 1 1 0 (14 0 0 0 0 1 0 1 0 (10 0 0 0 0 1 0 1 1 (11 0 0 0 0 1 0 0 1 (9 0 0 0 0 1 0 0 0 (8 0 0 0 1 1 0 0 0 (24 and so forth... ^ This sequence is the Gray code. ``` The Spin-Out puzzle operates using the same principle. U.S. Patent 3637215 - Keister 1972. There are seven knobs attached to a slider - each knob acts as a bit. The knobs can be rotated between a vertical and horizontal position - let the vertical position represent a bit value of 1 and the horizontal position a bit value of 0. The slider is trapped in a sleeve until all the knobs are set to 0 (i.e. horizontal). The objective is to free the slider. The puzzle starts with the slider trapped and all knobs in their vertical position. There is only one location in the sleeve where a knob can be rotated between vertical and horizontal, and the slider must be moved to and fro to position the proper knob at that location as moves are made. The same "prime directive" applies - a knob can only be moved if the knob immediately below it (to its right) is set to 1, and all other knobs below it are set to 0 (thus allowing the slider to move such that the next knob to be rotated can be positioned at the necessary location in the sleeve). The sequence begins as follows: ```1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 and so forth... ```

 I was very happy to obtain an original Binary Arts Hexadecimal puzzle, designed by William Keister and originally produced by Binary Arts (which became Thinkfun) as their first commercial puzzle. Richard Whiting maintains an informative web page devoted to the Hexadecimal puzzle. Dave Janelle at Creative Crafthouse reached an agreement with Thinkfun to allow him to produce a limited run of the Hexadecimal puzzle. Dave's version is made from cherry wood and comes in a nice case. Dave was kind enough to send me a prototype. Thanks, Dave! Stack the Deck - Great American Puzzle Factory 1997. Contains a 2x3 board - Start at (0,0) and Finish at (1,2). Also contains fifteen numbered chips. Begin with the chips stacked in numerical order on Start (15 on the bottom, 1 on top). End with the chips stacked in numerical order on Finish. Move chips one by one from square to any other square, but only placing a lower number on top of a higher number, not vice versa. This is a variant of the Towers of Hanoi. The following puzzles also entail the removal of a "key" piece from the body, after one figures out the proper unlocking sequence. This is the "Key" puzzle by Goh Pit Khiam. It is a 2-dimensional version of Bill Cutler's Binary Burr. Its operation is along the same principals as the Gray-code based puzzles described above. I bought it from Bill Cutler's site. Tern Key - designed by Goh Pit Khiam - purchased from CubicDissection. This lock is based on trinary. The Cerradura Doble designed by Robrecht Louage, entered in the IPP28 Design Competition, and made from stainless steel, acrylic, and Corian. Not sure if the scheme for this lock is Gray code, but it is similar to Khiam's Key. Robrecht sent me #3/50 as a gift! Thanks very much, Robrecht! Die Welle (The Wave) - Constantin

River Crossing Puzzles

River Crossing puzzles begin with a river and a means of crossing the river. Some group of people, animals, and/or objects must be moved from one side of the river to the other, subject to various constraints on inter-relationships among them, and on the use of the conveyance. One must describe a sequence of crossings which get everyone from one bank to the other while obeying the constraints. It should be stated that none of these puzzles require or permit tricks such as ropes, swimming, reliance on currents, etc.

Some early U.S. patents on river-crossing puzzles include 232394 - Delan 1880, and 249963 - Loomis 1881.

Perhaps the most well-known puzzle of the River-Crossing variety is that of the Farmer, Wolf, Cabbages, and Goat. This has been issued in mechanical form - the French puzzle "La Chevre et le Chou" by Watilliaux circa 1885 is an example. I have the version with the nice wooden pieces (not just carboard cutouts). A Farmer is traveling with a Wolf, Cabbages, and Goat (don't ask why). There is a river to be crossed, and a boat which will accommodate only the farmer, who must row every trip, and one of the others. The goat cannot be left alone with the cabbages, which it will eat, and the goat cannot be left alone with the wolf, which will eat it. You can try this puzzle online here.

Mouseover the box below to see my answer of 7 crossings:

 The farmer rows the goat across, then returns alone. The farmer rows the wolf across, then returns with the goat. The farmer rows the cabbages across, then returns alone. The farmer rows the goat across to finish.

Here is another mechanical presentation: "Boo Boogy Mans" - a "Super Puzzle" from Sherms of Connecticut. The box contains six counters, 3 each of two different colors, A and B, and a small boat. The inside of the box has a drawing of a river. The problem is to use the boat, which can only hold two counters per trip, to get all of the counters across the river. At least one counter must be in the boat every crossing. At any time, the following constraint must be met: the number of A counters at either shore must always be zero, or greater than or equal to the number of B counters. In its original form, there are three missionaries and three cannibals. The cannibals must not be allowed to outnumber the missionaries. You can play a version online.

Mouseover the box below to see my answer of 11 crossings:

 An A and B cross together. The B stays and the A returns. Two B's cross together. One B stays and one B returns. Two A's cross together. An A and B return. Two A's cross together. One B returns alone. Two B's cross together. One B returns alone. Two B's cross together to finish.

Dudeney gives problem #373: the boat can bear only weight 150. Four passengers must cross: weights 150, 150, 75, and 75.

Mouseover the box below to see my answer of 9 crossings:

 The two 75's cross together. One stays and one returns. One 150 crosses alone, and stays. A 75 returns. The two 75's cross together. One stays and one returns. The other 150 crosses alone, and stays. The 75 returns. Both 75's finally cross together.

Dudeney also gives problem #375: Five Jealous Husbands. Five jealous husbands traveling with their wives must cross, using a boat that can hold at most three people. Every husband was so jealous that he would not allow his wife to be in the boat or on shore with any other man unless he himself was present.

Here is a similar puzzle, produced in a simple but attractive wooden implementation - River Crossing - Bepuzzled 1997 Canada. Get the 3 couples by twos across the river - A man cannot cross with any woman but his wife, and cannot be alone with other women on either bank.

Measuring Puzzles

In these puzzles, one is presented with various containers of specific capacities, and some starting quantity and distribution of material among the available containers (sometimes an inexhaustible supply from a container of unspecified capacity is provided). The problem is to achieve some specific distribution and quantities among the given containers, by some sequence of transfers between containers.

Usually none of the containers are graduated, and all transfers must either fill or empty a given container completely. Measurements of quantities besides the specific capacities of the given containers are achieved by remainders left during transfers between containers of unequal capacity. Sometimes one is required to empty the contents of a container back into the general supply, or discard it - any chemistry student will tell you the former is a bad idea, while any merchant would object to the latter - but there you have it.

One would think that by their nature, since they involve physical containers, these would appear as mechanical puzzles, but actually transferring some material, be it water, sand, etc. is much messier than simply working these out on paper.

 I have, however, run across the French puzzle pictured at right, called either "La Maligne Laitiere" (The Ingenious Milkmaid) or "La Laitiere Avisee" (The Wise Milkmaid). (These names are reminiscent of the French edge-matching puzzle pair "Le Berger Malin" and "Le Fermier Avise.") I don't have this, but it seems to come with three wooden towers which will contain specific numbers of marbles.

Given a full jug of unspecified capacity, and empty capacity-5 and capacity-3 containers, measure out 4 units.

Fill the 5 from the jug. Fill the 3 from the 5 (leaving 2 in the 5). Discard the 3 (or empty it back into the jug). Transfer the 2 from the 5 to the 3 (now the 3 will take 1 more). Fill the 5 from the jug. Lastly, use the 5 to top off the 3, leaving behind the required 4.

One can depict the solution in a tabular format:

 cap-5container cap-3container action 0 0 start 5 0 fill 5 from jug 2 3 fill 3 from 5 2 0 empty 3 0 2 transfer 2 from 5 to 3 5 2 fill 5 from jug 4 3 top off 3 from 5

Dudeney states that Tartaglia (1500-1559) posed the following problem: Given a jug containing 24 units, and empty capacity-5, 11, and 13 containers, divide the 24 units into three equal parts (i.e. get 8 units into each of three different containers). Dudeney poses the following in problem #365: Given two full capacity-10 containers, and empty capacity-4 and capacity-5 containers, end with exactly 3 units in each of the empty containers. The Merchant of Bagdad (sic) appeared in Sam Loyd.

 This is Crazy Bottles, designed and made by Jean Claude Constantin. It is a mechanical implementation of the "water jugs problem" (or "wine jugs problem"), in which specific quantities of liquid are to be obtained using only jugs of given capacities. Each pour must either empty or fill a container. Crazy Bottles uses ball bearings to simulate integer quantities of liquid, and contains three areas around its perimeter to simulate the jugs, delimited by gates and having capacities of 7, 12, and 22 balls. The center holds two small dice - shake the dice to generate a problem - all combinations are solvable. This type of puzzle can be analyzed using barycentric coordinates. Rudenko Doser - designed and patented by Dr. Valery Rudenko. Another mechanical implementation of the jugs problem, using sand as the fluid. See www.roscreative.ru [Y]

Weighing Puzzles

In these problems, you are given a collection of items and a weighing device which can either compare two quantities and tell which is heavier (or if they are equal), or a digital scale which can provide a quantitative weight in some units of the weighed item(s). You must sort the items in some way, using only a specified number of weighings.

The weighing problem I am most proud of solving on my own is as follows: You are given ten bags each containing ten marbles. All of the marbles weigh ten units each, except for one of the bags contains ten marbles from the wrong batch. Those ten marbles weigh only 9 units each. You do not know which bag contains the wrong marbles. In only one weighing using a scale which can read out digital weight, determine objectively which bag contains the wrong marbles.

Mouseover the box below to see the answer:

 Number the bags consecutively from one to ten, in any order. On the scale, place one marble from bag #1, two from bag #2, 3 from bag #3, etc. up to all ten from bag #10. Take the reading from the scale once all the marbles are placed. Now, had there been no wrong marbles, the scale would read (1+2+3+4+5+6+7+8+9+10)x10 = 55 x 10 = 550. However, at some point you will have added N of the wrong marbles from bag #N. If the wrong marbles are in bag #1, the weight will be 549, since the 55 marbles on the scale include one which weighs 9 rather than 10. If the wrong marbles are in bag #2, the weight will be 548, since now the 55 marbles on the scale include two which are weight 9 rather than 10. In general, 550 minus the reading will tell you the number of the bag containing the wrong marbles!

Given 12 identical-looking coins, 11 of which weigh exactly the same. The twelfth is a forgery and is either heavier or lighter, you don't know which. Using a balance scale, determine which coin is the forgery, and whether it is lighter or heavier, in the minimum number of weighings. It's a challenge to devise a way to do it in four weighings. However, it is possible to do it in only three!

See the answer to an equivalent puzzle here.

Counting Puzzles

 An advertisement for Crown Flavoring Extracts (I don't have this - shown for reference.) Eight circles - start on any circle, count 1,2,3,4 in either direction, and cover the fourth. Repeat, starting on any uncovered circle, counting both covered and uncovered circles, ending on an uncovered and covering it. Goal is to end with only one uncovered circle. The Great American Ball Blue 9 Puzzle (I don't have this - shown for reference.) Counting from the bottom up, in any direction, there are 9 balls. Remove two balls and rearrange to preserve this property. Le Quart d'Heure de Rabelais, also known as Les Bourgeois Punis (I don't have these - shown for reference.) Versions of the Josephus or Survivor Problem - count out every k-th man from a circle of n. Arrange the initial circle to ensure specific men survive (e.g. as last or last two). In the puzzle, stick the last two men with the bill. You can play the general version online at cut-the-knot.org. In France, the expression "le quart d'heure de Rabelais" means that it is time to pay. This saying stems from an episode when Rabelais, finding himself without money in Lyon and wanting to travel to Paris, left several packets of sugar out in plain view on which he wrote "poison for the King." Arrested, he was taken to Paris by the police and thus traveled there for free. The king, François the 1st, laughed so hard when he heard the story that he paid the sum out of goodwill. Wilhelm Ahrens wrote that Cardan first described this problem by using the story of Flavius Josephus, and naming the problem "ludus Josephi" in Cardan's "Practica Arithmeticae generalis" of 1539. Hoffmann mentions such puzzles in Chapter IV. Mentioned in Slocum and Botermans' Puzzles Old and New on page 133. Save Your A** - by Creative Crafthouse. Thanks Dave! A variation on the Josephus problem. Robinson Roulette - German version "Created by Terry Pegg of Choro Ltd. Birmingham UK." Issued by Milton Bradley 1985 See Jaap's page on Robinson Roulette. This is a solitaire sequential movement puzzle. There are 11 holes in both the outer and inner rings and each ring also has an arrow. The inner ring rotates relative to the outer. To set up, orient the outer ring so its arrow is at 12 o'clock, and the inner arrow to 6 o'clock. Populate the inner ring with 10 red pegs and 1 white peg ensuring that the white peg is not at 12 o'clock. The goal is to transfer all red pegs and lastly the white peg from the inner ring to the outer. A move consists of grabbing the peg at 12 o'clock on the inner ring and rotating until it becomes adjacent to an empty spot on the outer ring, then transfering it to that spot. This movement of course simultaneously positions some other inner hole (and its peg if present) at 12 o'clock. Choose your destinations wisely since if you haven't yet placed the white peg and you're left with no inner peg at 12 o'clock for the next move, you've lost.