Looking at some track constructions of a toy electric train, I noticed that sometimes the train would get "stuck" in a loop, or that some places could not be reached no matter how you played with the switches: it was necessary to pick up the train physically and move it to the desired spot.
Contemplating this I discovered two problems, one I solved, the other was a mystery for a long time.
A toy electric train on a track layout with two switches
Consider the layout of the photo:
Figure 1: the oval layout with two switches and a diagonal [SVG]
The locomotive is shown as a red rectangle with an arrow to indicate the sense of travel.
If you set the switches correctly and let the loco run, it will go over the diagonal, but only once. After having passed the diagonal it has effectively turned around and however you now set the switches, there is no way to make it go over the diagonal again.
and on this layout you can get from anywhere to anywhere and in any sense of travel.
Each layout has this property:
either you can get the train to any point by only playing with the switches,
or there are points you can reach only by picking up the train and putting it there.
I call this the All Points Reachable (APR) property, and for any given track layout APR is either true or false.
For the layout in figures 1 and 2 it is false, but for figure 3 it is true.
It is clearly not just a matter of how many switches there are, but also of how the segments connect them together.
The problem is: can you determine whether the APR property is true or false by just looking at the track layout?
The answer is yes, and it is even easy to write a program to do it.
We need a somewhat more precise definition of what the APR property is, and also discuss what we mean by "looking at the track layout", but first I will say something about the figures I will use to get us to the program.
Figures
Because I started thinking about the problem while playing with my granddaughter's Lego Duplo train set, I will also use the forms of rails and switches from that set, but obviously that is not a constraint.
We will define a segment of track as a stretch of rails that has no switches in it, however long or short the segment is.
A switch connects at least three segments: an ingoing one and two outgoing ones, one of which can be chosen by setting the switch in one sense or the other.
In figure 5 the stretches of rail labelled A1-A2, B1-B2 and C1-C2 are segments, connected to a switch with number 1.
A2 is the switch's incoming end, B1 and C1 are its outgoing ends.
Coming from point A1 you can choose to go to either B2 or C2. Coming from B2 or C2 you can only go to A1: switches are not symmetric.
Precise definition
First we will impose that the train cannot go backwards, it must always travel in the forward sense of its locomotive. It is also sufficient to consider just the locomotive and forget the string of cars it pulls.
Secondly we will require that the sense of travel is important, so that we can arbitrarily choose a desired sense of travel in both the point of departure and the point of arrival.
The precise definition of the APR property is then:
Let a locomotive travel over a railway layout by always advancing in the same sense.
The layout has any number of switches, each switch presents a choice of two and only two track segments when travelled over in one sense and no choices when travelled over in the other sense.
If for any given D = {d,sd} an arbitrary sense of travel sd at an arbitrary point of departure d, and A = {a,sa} an arbitrary sense of travel sa at an arbitrary point of arrival a, the locomotive can start at D and arrive at A by only operating the switches, then the All-Points-Reachable property of the layout is true.
(Note: requiring both senses of travel is somewhat stricter than just requiring that any point can be reached from any other point, though it is perhaps easier to deal with. But I don't know as I have not tried to solve the less restrictive problem).
Discussion
Complexity
For the purpose of determining the APR property, a track layout is not essentially changed if a segment is made longer or more curvy. If a segment crosses another one, either at level or by passing over it on a bridge, that does not change the essence of it either because it is not possible at a crossing to switch from one segment to the other. The only important information is in how switches connect segments.
Let us note that the precise specification does not limit complexity by only taking into account switches that fork into two segments: switches with more than two choices can easily be reduced to sequences of switches with only two.
Figure 6: a triple switch and its equivalent made of simple switches [SVG]
Another configuration that is easily dealt with is the end-to-end pair of switches:
Figure 7: a pair of end-to-end switches decoupled by introducing a small segment [SVG]
In general, if two switches are directly linked, a short segment should be insserted to separate them for the purposes of the calculation of the APR property.
Trivial cases
There are large numbers of trivial layouts for which the value of the APR property can be decided instantly.
If the track is just a straight segment as in figure 1 above, then the train cannot reach points behind it (since it is not allowed to travel backwards) but it cannot turn around either: it cannot reach any other spot if it has to arrive there travelling in the other sense.
Any layout that has pieces of track that are "dead ends" presents this problem: we can put the train on a dead end facing away from the rest of the track, and we immediately know that the APR property is false for that layout.
Non-trivial Cases
Only layouts without dangling dead ends need to be considered further. These are all "closed".
Obviously it is possible to get to any point from any point, but it is again not possible to turn the train around without picking it up. We need some switches to get to interesting layouts.
Number of Switches
If we do not allow dangling segments of track, because we know that the APR property for such layouts is false anyway, then the number of switches in a layout must be even.
This is fairly easy to see: if the layout is closed to begin with, and you put a new switch in at any point of an existing segment of track, then one of its ends will lead to a dangling end unless you connect that dangling end to another (or the same) segment by putting in another switch. For non-trivial layouts one new switch always means another new switch, hence an even number of switches in total.
Number of Segments
The number of segments is always equal to three times the number of pairs of switches:
0 switches = 1 segment
2 switches = 3 segments = 1×3
4 switches = 6 segments = 2×3
6 switches = 9 segments = 3×3
8 switches =12 segments = 4×3
Solving the problem
Consider again our oval with two switches and a diagonal segment. To make things clear, I gave each switch a number, and I gave each segment a name. I also labelled each end of each segment by the segment's name and a number 1 or 2.
Say the locomotive starts at position A1 and heads towards A2. Starting from any other position on segment A and going in the same sense will make no difference in whether the locomotive can reach some other point on the layout.
All these equivalent positions can be called by the same name A1, the first position on that segment. Likewise, we will use the name A2 to designate all positions on segment A, in which the locomotive travels in the sense A2 to A1. Therefore, saying the loco is at C1 means it is on segment C and travels in the sense from C1 to C2.
With that in mind we can now look at figure 9 again. If I'm at A1, I can travel over switch 2 and get to B2. If I started at B2, I can get to C1. It follows that if I start at A1 I can get to C1. And that gives us a hint as to how we could figure out if the APR property is true or not.
We have two switches, and for each we have two senses of travelling over them. The list of points we can reach is easy to make:
Using switch 1:
from C2 we can get to A1 or to B1
from A2 we can get to C1
from B2 we can get to C1
Using switch 2:
from A1 we can get to B2 or C2
from B1 we can get to A2
from C1 we can get to A2
(remember that you have to start from C2 if you want to travel over switch 1!)
Let us put that in a table:
A1
A2
B1
B2
C1
C2
A1
√
√
A2
√
B1
√
B2
√
C1
√
C2
√
√
Vertically on the left we put the points we may start from, horizontally at the top the points we may reach. Then in each cell we put a checkmark if the point listed at the top that can be reached from the point listed at the left. E.g. row 3 shows that from B1 we can reach A2 (column 2).
But row 2 shows that from A2 we can reach C1. So we can also place a checkmark in the C1 column of the B1 row. If we add these checkmarks consistently, we get a more filled table:
A1
A2
B1
B2
C1
C2
A1
√
√
√
√
√
A2
√
√
B1
√
√
B2
√
√
C1
√
√
C2
√
√
√
√
√
We can repeat this process on the new table. Then we get a third version:
A1
A2
B1
B2
C1
C2
A1
√
√
√
√
√
√
A2
√
√
B1
√
√
B2
√
√
C1
√
√
C2
√
√
√
√
√
√
Only two more checkmarks this time. The new table tells us that we can reach all points starting from A1, and also from C2. For the other points we are not sure yet. But if we repeat the process a third time, we get in fact no more checkmarks at all. If we don't get more checkmarks, it is useless to try yet again, the table will not change.
We end up with a table that has some empty cells.
The final table gives us the answer: the APR property for that layout is false, because there are some empty cells. For example, it is not possible to reach either position B1 or B2 starting from position C1, i.e. starting from there we cannot at all get onto the diagonal. We knew this, but now we have computed it by just starting from the initial switch connections, without looking at the layout or tracing the rails on a drawing with a finger.
If you make a similar table for the layout of figure 3, after having numbered the switches and labelled the segments, you will find that the table becomes completely filled with checkmarks. The APR property for that layout is true.
Ending the process
How often do we need to repeat the process of propagating the checkmarks in the table? It would seem that the more complex a layout is, the more often we need to do it to get the answer.
The table is always square, say it has n rows and n columns. A checkmark may propagate to a different row at each iteration, but at most to n rows. Thus we know that for a table of dimension n we will find the answer in at most n iterations. After that number of repetitions of the process the table is either completely filled with checkmarks and APR is true, or there are still some empty cells and APR is false.
Capturing a layout's essentials
Consider a last time our oval with two switches and a diagonal segment:
Figure 9 again: again the oval with two switches and a diagonal [SVG]
We have defined the point A1 as the equivalent of all points on segment A with the locomotive travelling in the sense from A1 towards A2. That is rather uncomfortable when we want to describe the switches, since A1 is on the other side of A2, the nearest point to switch 2. We are less likely to make errors if we describe a switch by giving the segment labels closest to it. If we consistently use the suffixes 1 and 2 for the ends of s segment, then there will be no problem.
For the purpose of computing the APR property, a layout can be described completely as follows:
Give each segment of a layout a unique name.
Label one end of a segment with the segment's name and the suffix number 1, the other end with the segment's name and the suffix number 2.
Give a unique number to each switch
Describe each switch by noting down
the switch's number,
the label of the segment end connected to its incoming end, and
the labels of the segment ends connected to its outgoing ends (in either order).
The layout is unambiguously defined by the list of switch descriptions only.
The description of the switch in figure 5 is:
1 A2 B1 C1
or alternatively, since the order of naming the outgoing ends does not matter:
1 A2 C1 B1
The description of the layout with the diagonal and two switches is:
1 C1 A1 B1
2 A2 B2 C2
A complex layout
Below is a fairly complex layout.
Figure 11: six switches a bridge and a crossing. [SVG]
Noteworthy aspects of this layout and its labelling are:
there is indeed an even number of switches
segment C is curvy and long, it crosses segment E at level (light blue rail element), but on such a crossing the train has no choice but to stay on segment C
segment F goes over a bridge and crosses segment C in that way, but again this is irrelevant to the value of the APR property
segment I is very long while segment A is very short, and this too makes no difference to the APR value
Because I copied this design from a set of drawings I made for Lego Duplo trains, there are some strange rails. I used some half-rails from the previous type of Duplo rails, and there are some mismatch problems in nearly all Duplo layouts, but that is a topic for the Lego pages.
But before you follow that link: read the rest here, because it involves the second problem.
The Second Problem
We found earlier that the process of iterating the table would end in at most n repetitions for a table of size nxn.
It is better than that.
I thought the computations might take quite some time for very large tables, so I put a check into the program: I made it stop as soon as the next version of the table was identical to the previous one.
When I ran the program I noticed that no matter how complex the layout was (no matter how many switch pairs there were) it always stopped after the second iteration! This was quite surprising and I spent some time trying to prove that only two iterations were necessary. For about a year I failed miserably each time I tried. Then it occurred to me that a switch gives only two choices, and that might have something to do with the proof.
There are a few observations one can make:
In the original table, each row must have either one or two check marks. If it has two, then the corresponding columns have only one check mark. If it has one, then that mark occurs in a column that has two marks. These are obvious consequences of the fact that the switch at that end of the segment is connnected to it at its incoming end or at one of its outgoing ends.
We now (2013-12) do have a mathematical proof, but any suggestions or references to mathematical literature are still welcome. To the best of my knowledge, this problem has nothing to do with the famous Königsberg Bridges problem that Euler solved elegantly.
It also turned out that the properties of a switch have nothing to do with the observation of two iterations. In fact, the iteration ends after at most 2 for any starting pattern, it has nothing to do with the APR property at all. It is a cpnsequence of how the algorithm works.
The proof allows us to change the program so it does only two iterations and stops. That version has not been implemented here.
