Category Archives: Operations research

Sliding block puzzles


One of our daughters obtained a nice sliding puzzle app on her ipad, and it features various levels, each level with several hundreds of puzzles.


The app is also available on android as “unblock me”, by Kiragames. It is also available in Googles play store for windows, see https://play.google.com/store/apps/details?id=com.kiragames.unblockmefree&hl=en.

I tried the app and the puzzles start out easy, but soon turn out to present decent challenges. Reason enough for a post on this type of puzzles. I’ll limit myself in this post to 2d sliding block puzzles. There are many 3d sliding block puzzles too: puzzle collectors may remember the many secret boxes puzzles, often beautifully crafted by woodworkers. But those are worth a different post.

There are many types of sliding block puzzles. Sam Loyds 15 puzzle is probably the most famous one. Many sliding block puzzles have been computerized, and the Sokoban puzzles are perhaps the first type of sliding block puzzle that exists only as a computer puzzle and not as a mechanical puzzle. But in this post I’d like to take a closer look at the type of sliding block puzzle that at the English wikipedia is called Klotski. I feel some doubt at this name: it may be derived from polish, as the article says, but when I view the history of the article I think it is more likely that Klotski is the name of a computer or video game instead of the name of this type of puzzle. I have never encountered the name Klotski for this type of puzzle in any puzzle book.

Klotski game shot

Sliding Piece Puzzles (by Edward Hordern, 1986, Oxford University Press, ISBN 0-19-853204-0) is said to be the definitive volume on this type of puzzle. It lists 270 of his sliding block puzzles, all neatly categorized and with the solution in the shortest number of moves. That brings us of course to the question: what is a move?

Hordern lists 4 possibilities:
a) a sliding block is moved as many ‘units’ in one or more directions
b) a sliding block is moved one ‘unit’ in 1 direction
c) a group of sliding blocks is moved one or more units in 1 direction.
d) a sliding block is moved one or more units in one direction.
Option a) is most common among puzzlers, mainly because it corresponds with a physical action: move a block as far as you want without lifting your finger from the piece.

Horderns also subdivides sliding block puzzles in four categories:
I. Sliding block pieces – pieces move independent of each other.
II. Warehouse/soko puzzles: one piece pushes others.
III. Railway shunting puzzles – one or two pieces push or pull all the others
IV. Puzzles with plungers or levers.
I already treated railway shunting puzzles, and category IV is a group of rather rare and complicated puzzles. This post deals entirely with group I, and with the subgroup where pieces are rectangular and of unequal size.

The nice thing about mechanical puzzles is that you can patent them, such as USA patent 207,124.

I’m not sure about the early history of sliding block puzzles. Sam Loyds puzzles goes back to the 1870’s. One Henry Walton filed U.S. Patent 516,035 on 1893-03-14 for a sliding puzzle resembling 15-puzzle. According to Edward Hordern, this is the first even known sliding puzzle with rectangular blocks.

Horderns book “sliding block puzzles”, mentioned above, is the standard work of reference for this type of puzzle.

Links:
* http://www.novelgames.com/gametips/?id=121: Only 3 levels, but nrs 2 and 3 are a nice challenge
* http://www.spel.nl/game/sliding-block-puzzle.html – several classics

* http://www.cleverwood.com/about_sliding_block_puzzles.htm – general information and some links
* http://www.johnrausch.com/slidingblockpuzzles/
* http://home.comcast.net/~stegmann/sliding.htm – robs puzle page, examples of sliding block puzzles

http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf

Advertisements

Barrels, Cans, Flasks, Glasses, Tanks and Vessels pouring puzzles


1) 3, 4 and 5*
My grandfather was a milkman in the time when milkmen went from door to door, and the women came out with a can to buy some milk. His car held a large tank with tens of liters of milk.
Normally my granddad had a number of measures with him, but one day he had just a 3 quarter can with him. One woman came out with her 5 quarter can and wanted to purchase exactly 4 quarter.
How did my grandfather arrange this? Of course no milk should be spilled.

If you solved it, you can check your solution.

2) 3, 5 and 8 – divide equally*
Sam Loyd mentions the puzzle above as a very old problem. Actually, this is a simplified form of an old puzzle, popularized by Niccolo Fontana (1500-1559), nicknamed the Stammerer (Tartaglia), which ran:

There are three jugs A, B, C, with capacities 3, 5, and 8 quarts, respectively. Jug C is filled with wine, and we wish to divide the wine into two equal parts by pouring it from one container to another – that is, without using any measuring devices other than these jugs.

Fontana probably got it from an older manuscript dated around 1200.

This puzzle was discussed mathematically by Alexander Bogomolny

If you solved it, you can check your solution

.

3) Three glasses puzzle*
There are three glasses on the table – 3, 5, and 8 oz. The first two are empty, the last contains 8 oz of water. By pouring water from one glass to another make at least one of them contain exactly 4 oz of water.
This is a waterdown version of the previous puzzle, so we’ll skip this and instead propose a version described by puzzle blogger Professor Richard Wiseman:

There are 3 glasses of 3, 5 and 8 oz. The 3 oz glass holds 2 oz, the 5 oz glass holds 3 oz and the 8 oz glass holds 5 oz.
Can you measure 1 oz in only 2 pourings?
solution

4) Divide 24 liters in three equal portions*
Divide 24 fluid ounces of a liquid into three equal parts, given that there are three containers available holding 5, 11 and 13 fluid ounces.
This problem was posed by Claude Gaspard Bachet de Méziriac in his Problèmes plaisans et délectables (1612). He may have copied this problem from an older resource such as Tartaglia.
Henry Dudeney remarked about this puzzle: There are many different solutions to this puzzle in six manipulations, or pourings from one vessel to another.
solution

In the second half of the 19th century, both Sam Loyd and Henry Dudeney produced puzzles of this type:
5) The Wassail bowl*
One Christmas Eve three Weary Willies came into possession of what was to them a veritable wassail bowl, in the form of a small barrel, containing exactly six quarts of fine ale. One of the men possessed a five-pint jug and another a three-pint jug, and the problem for them was to divide the liquor equally amongst them without waste. Of course, they are not to use any other vessels or measures. If you can show how it was to be done at all, then try to find the way that requires the fewest possible manipulations, every separate pouring from one vessel to another, or down a man’s throat, counting as a manipulation.
solution

6) The barrel puzzle*

The men in the illustration are disputing over the liquid contents of a barrel. What the particular liquid is it is impossible to say, for we are unable to look into the barrel; so we will call it water. One man says that the barrel is more than half full, while the other insists that it is not half full. What is their easiest way of settling the point? It is not necessary to use stick, string, or implement of any kind for measuring. I give this merely as one of the simplest possible examples of the value of ordinary sagacity in the solving of puzzles. What are apparently very difficult problems may frequently be solved in a similarly easy manner if we only use a little common sense.
This puzzle stems from Dudeneys “Amusement in mathematics”
solution

7) 4, 5, 10 and 10**
Here is a new poser (wrote Henry Dudeney at the end of the 19th century) in measuring liquids that will be found interesting. A man has two ten-quart vessels full of wine, and a five-quart and a four-quart measure. He wants to put exactly three quarts into each of the two measures. How is he to do it? And how many manipulations (pourings from one vessel to another) do you require? Of course, waste of wine, tilting, and other tricks are not allowed.
This puzzle stems from Dudeneys “Amusement in mathematics”
solution

8) The brook*
Another Dudeney: A man goes to a brook with two measures of 15 and 16 pints. How is he to measure exactly 8 pints in the fewest possible moves?
I need hardly add that no tricks such as tilting or marking are allowed.
solution

9) The barrels of beer*
The america prohibition authority discovered a full barrel of beer, and were about to destroy the liquid by letting it run down a drain when the owner the owner pointed to 2 vessels standing by and begged to be allowed to retain in them a small quantity for the immedeat consumption of his household. One vessel was a 7 quart and the other a 5 quart measure. The officer was a wag, and believing it to be impossible, said that if the man could measure an exact quart into each vessel, without pouring anything back into the barrel, he might do so.
How was it to be done in the fewest possible transactions without any tricks such as marking?
Perhaps I should add that an american barrel of beer contains exactly 120 quarts. Wasting beer is in this instance of course allowed.
solution

10) The merchant of Bagdad*

Sam Loyd presented the following problem on page 188 of his “Cyclopedia of Puzzles”.
Ae merchant of Baghdad who catered to the wants of pilgrims who ncrossed the desert, was once confronted by the following perplexing problem:

He was visited by the leader of of a caravan, who desired to purchase a store of wine and water. Presenting three 10 gallon vessels, he asked that three gallons of wine be put in the first, three gallons of water in the second, and three of wine and three of water mixed in the third, and that three gallons of water be given to each of the thirteen camels.

As both water and wine, according to Oriental usage, are only sold in quantities of an even number of gallons, the merchant had only a two and a four gallen measure wherewith to perform a feat which presents some unexpected difficulties; nevertheless, without resorting to any trick or device, or expedient not pertaining to the ordinary measuring problem, as already referred to, he dispensed the water from a full hoggshead, and the wine from a barrel, in the required proportions, without any waste whatever.
In how few manipulations can the feat be performed, counting every time that liquid is drawn from one receptacle to another as a manipulation?

Sam Loys son, Sam Loyd jr, added: This puzzle is undoubtedly the most remarkable problem of its extant, anf for many years baffled the puzzlists of the world to reduce to the least possuiible number of “moves”, as the manipulations were then termed. By many it has been referred to as Sam Loyds greatest puzzle.
From a contemporary view, it may be useful to note that a hoggshead contains 63 gallons, while a barrel contains 31.5 gallons.
solution

This one too comes from Sam Loyd:
11) Milkmans puzzle**

There are practical problems in all trades, so it is safe to say that no one is an adept at his business unless he had pickesd up a few wrinkles which pertain to his calling.

Honest John says that what he “dont know about milk is scarcely worth mentioning”, but he was nearly flabbergasted when he had two 10 gallon cans full of milk and two customers with a four and a five quarter measure wanted two quarts in each measure.

It is a juggling trick pure and simple, devoid of trick or device, but it calls for much cleverness to get two exact quarts of milk in those two measures employing no receptacles of any kind except the two measures and the two full cans. You cab try the problem with the fullest assurance that it is a legitimate problem and not a silly catch.

According to professor Knuths index, this puzzle was first published in Women’s Home Companion 34,3 (March 1907).
solution

12) Three glasses puzzle – again**

A variant of my own:
You have three glasses with a capacity of 3, 5 and 8 oz, partly filled with water.
The 3oz glass holds 2oz.
The 5oz glass holds 3oz.
The 8oz glass holds 5oz.
If spilling water is not considered a move, how can you measure 1 oz in 1 move?
solution

Captain Brownbeard’s hourglasses


Brownbeards hour glasses

Captain Brownbeard of the pirateship “The northern star” told his first officer: “Tonight I want to sleep for 7 hours. Wake me exactly 7 hours after I leave the bridge.”

The unfortunate first officer knew that captain Brownbeard had only 1 punishment: eat so many chocolates that you never can stand the sight of chocolate again. He didnt want to suffer such a dreadful fate. To make things worse, he had only two hourglasses, one of 5 hours and one of 3 hours. How can he measure exactly 7 hours? Does he need to make any preparations in advance, and if so, which?

This puzzle is based on a puzzle with hourglasses of 4 and 7 hours which I found in both “More games for the superintelligent,” by James F. Fix and in “Denkspielereien” by Tom Werneck. The same problem can be found on numerous places on the web, with hourglasses of 7 and 11 minutes. This raises of course the question who invented this puzzle, and when?
Oh, by the way, the times used in this puzzle introduce a slight variation.

You can check your solution

Railway problems


1) Two trains pass
Train shunting puzzle - two trains must pass each other
In the old days when single track was still customary, two trains met at the spot of a side track. The track was long enough to hold 1 engine and 4 wagons or 5 wagons. That corresponded with every day traffic, but yesterday was a strike and now both trains pull 8 wagons.
An extra complication is a not-so-strong bridge at the right end of the side track, which no engine may pass, though it is strong enough for normal wagons.
Both engines can both push and pull wagons with their front- and rear ends.
If both a stop and a reversal of direction of an engine counts as 1 move, what is the minimum number of moves needed for the two trains to pass each other?

If you wish you can check your solution

According to the English language wikipedia, there are about several categories of railway shunting puzzles. This post is about one of these categories, where a train or trains have to be maneuvered around a given track with some limitations.

The history of train shunting puzzles can’t go back further then that of railroads themselves, but a quick Google search did not reveal much.

British puzzle master Henry Dudeney also seems to have published several puzzles in this class, but his American counterpart Sam Loyd published two of them in his Encyclopedia of Puzzles. Besides these two, there is one classical which I’d like to present to you, if only because it’s the first one I ever encountered.

Let’s start with the two puzzles by Sam Loyd:
2) Primitive railroading
On page 89 of the cyclopedia of puzzles Sam Loyd poses the following problem:
primitive railroading
Owing to the widespread interest taken in a simple railroad switch problem which I sprung on my friends some time ago, as well as in response to the request from many for another practical lesson in railroading, I present one which is an offshot from the first, and illustrates the difference between sidetracking a train or passing it through an y-branch., which reverses the direction of the trains.
In this specimen of primitive railroading we have an engine and four cars meeting an engine and three cars, and the problem, as in the previous one, is to ascertain the most expeditious way of passing the two trains by means of the switch or side track, which is only large enough to hold one engine or one car at a time.
No ropes, poles or flying switches are to be used, and it is understood that a car can not be connected to the front of an engine. It shows the primitive way of passing trains before the advent of modern methods, and the puzzle is to tell just how many times it is necessary to back or reverse the direction of the engines to accomplish the feat, each reversal of an engine being counted as a move in the solution.

This puzzle also appeared as nr 48 in Henry Dudeneys “Modern Puzzles”, and as nr 95 in Martin Gardners selection from Loyds Encyclopedia of Puzzles.

If you wish you can check the solution

3) The Switch Problem
Further down in his collection, on page 167, Sam Loyd presents a second problem. You may have noted that in the problem above Sam Loyd referred to a ‘first’ puzzle in this class, and I suppose that he had this puzzle in mind, even though this puzzle is listed after the first. The puzzle collection was probably first published in same daily or weekly newspaper column, and collected afterwards in his cyclopedia. According to Donald Knuth’s reference, the switch problem appeared in the Brooklyn Daily Eagle on 14 March 1897.

the switch problem

This is a practical problem for railroadmen, given to illustrate some of the complications of every-day affairs and is based upon the reminiscences of the days when railroading was in its infancy, before the introduction of double tracks, turn tables or automatic switches.
Yet, I am not going back to the days of our great-grandfathers, for there are those among us who are familiar with the advent of the iron horse, and the good lady who furnished me with the subject matter of the puzzle based it upon personal experience of what she called “the other day”. To tell the story in her own way, she said:
“We had just arrived at the switch station, where the trains always pass, when we found that the Limited Express had broken own. I think the conductor man said the smokestack had got hot and collapsed, so there was no draught to pull it off the track.”

The picture shows the Limited Express, with its collapsed engine, and the approach of the accommodation train from Wayback, which, by some means or other, must pass the stalled train.

The problem being to make the two trains pass, it is understood, that no ropes, poles, flying switches, etc. are to be employed; it is a switch puzzle pure and simple, the object being to get the accommodation train past the wreck and leave the latter train and each of its cars in the position as shown in the sketch.
It is necessary to say that upon the side switch there is but room enough for one car or engine, which is also true of the sections of the switch A, B, C and D.
The problem is tom tell just how many times the engineer must reverse; that is, change the direction of his engine to perform the feat. Of course the broken down engine can not be used as a motor, but must be pushed or pulled along just as if it were a car. The cars may be drawn singly or coupled together in any required numbers.
The problem complies with ordinary rules of practice and it is given to test your ingenuity and cleverness in discovering the quickest possible way to pass the broken down train.

This problem appeared as Puzzle no 30 in Tit Bits, and on March 14, 1897 in the Brooklyn Daily Express.

If you wish you can check the solution

4) Dudeney’s puzzle of passing two trains
How are the two trains in our illustration to pass one another, and proceed with their engines in front? The small sidetrack is only large enough to hold one engine or one car at a time, and no tricks such as ropes or flying switches, are allowed. Every reversal – that is, change of direction – of one of the engines is counted as a move in the solution. What is the smallest number of moves necesary?

To work on the problem, make a sketch of the track, and on it place a nickel and three pennies (heads up) for the engine and cars at the left, and a nickel and two pennies (tails up) for the engine and two cars on the right.
As you can see, this puzzle is identical to one of Sam Loyds puzzles above, so I’m not gonna publish the solution again. This version comes from Dudeney’s collection: 536 puzzles and curious problems, a collection published after Dudeneys death. In this book, it was puzzle 374.

5) Dudeney’s chifu chemulpo puzzle
Here is a puzzle that was once on sale in the London shops. It represents a military train—an engine and eight cars. The[Pg 135] puzzle is to reverse the cars, so that they shall be in the order 8, 7, 6, 5, 4, 3, 2, 1, instead of 1, 2, 3, 4, 5, 6, 7, 8, with the engine left, as at first, on the side track. Do this in the fewest possible moves. Every time the engine or a car is moved from the main to the side track, or vice versa, it counts a move for each car or engine passed over one of the points. Moves along the main track are not counted. With 8 at the extremity, as shown, there is just room to pass 7 on to the side track, run 8 up to 6, and bring down 7 again; or you can put as many as five cars, or four and the engine, on the siding at the same time. The cars move without the aid of the engine. The purchaser is invited to “try to do it in 20 moves.” How many do you require?

If you wish you can check the solution

6) Dudeney published a third puzzle, Mudville railway muddle, with two trains (engine + 40 cars each), which have to pass each other, but I have not been able to locate this puzzle. Professors Knuth short summary suggests to me that it is a simplified version of the puzzle at the top of this blog.

7)Anonymous classic

Move the engine so that the two wagons are interchanged and the engine is in the same spot again. The wagons can not pass through the tunnel, but the engine can. The engine can both push and pull with its front and rear, and even do both at the same time when that comes in handy. What is the minimum number of stops or reversals of direction of the engine that is needed?

If you wish you can check the solution

8)Anonymous classic variation

This puzzle is identical with the previous one, but the extra track allows for a faster solution. It can be found freely in many books and magazines.

(Thanks go to my daughter Margreet for the last two illustrations!)

If you wish you can check the solution

The puzzle at the start of this post was designed by me some 20 years ago. No doubt it was based on one of the many adaptions of puzzle 5. I recently rediscovered a page with notes om railway shunting puzzles, and one of them was this puzzle which I didn’t publish before.

I also would like to thank Professor Don Knuth for his laborious work in compiling indices on the works of Dudeney en Loyd. Most of the historical notes in this post are based on his indices.

9) Online puzzles: at armorgames
There are a couple of sites where you can play online:
http://armorgames.com/play/7324/railroad-shunting-puzzle

10) Other sites
http://www.freetraingames.org/game/36/Epic-Rail.html
http://www.wymann.info/ShuntingPuzzles/ (My friend Marco Roepers kindly pointed out this site, thanks, Marco!)