Solving Railway Mazes: 
From Image to Solution

Antonín Slavík

Charles University, Prague, Czech Republic

Stan Wagon

Macalester College, St. Paul, Minnesota, USA

Image preprocessing

A maze is given as a bitmap image. This original image will be used as a background when displaying the solution.

original1=;

For further processing, we also need a second image, which is black and white (black=background, white=maze) and such that all paths have the width of 1 pixel. This binary image will be used by to find the solution.

We apply Binarize, ColorNegate, Blur and Thinning to obtain this second image:

bin1=Binarize[original1]

neg1=ColorNegate[bin1]

bw1=DeleteSmallComponents[neg1]

If we use Thinning directly on the previous image, we get small loops at certain wyes:

thin1=Thinning[bw1]

Show[thin1, Graphics[{FaceForm[],Rectangle[{60,54},{238,149}]}],
PlotRange->{{59,238.5},{53.8,149.5}}]

The loops can be avoided by using GaussianFilter first:

thin1=Thinning[Binarize[GaussianFilter[bw1,2],0.5]]

The algorithm

Basic idea

The state of the train is characterized by its position and direction.

Perform a breadth-first search of the state space from the initial point and try whether it is possible to reach the target. If we succeed, BFS guarantees that we have found the shortest solution. The BFS is keeping records about visited vertices and their predecessors; upon reaching the target, we can reconstruct the solution by going backwards.

At a junction, we measure the turning angle between the incoming direction and all possible outgoing directions. The legal moves are only those where the corresponding angle does not exceed a certain threshold. Our curves are made up of discrete points, so we use secants to approximate the tangents. After some trial and error, we found that accepting outgoing directions with turning angle no greater than 70° is a reasonable choice.

Show[im3, Graphics[{{EdgeForm[Black], FaceForm[], Rectangle[{120, 60}, {153, 92}]}, Thickness[0.011], Arrowheads[0.1], Red, Arrow[{in, wye + .1}], Lighter@Blue, Arrow[{wye, out1 + {.1, .13}}], Arrow[{wye, out2 + {.1, 0}}]}], PlotRange -> {{120, 153}, {60, 92}}, PlotRangePadding -> 0.1, PlotRangeClipping -> True, Frame -> True, FrameTicks -> False]

Upon reaching a junction, we have to be careful to avoid reversing direction: 
Skip the neighboring pixels having degree three or more (3, 4, and 6 in the figure) and consider only moves to pixels having degree two (5 and 7 in the figure). Only the latter are allowed as possible continuations.

Graphics[{EdgeForm[{GrayLevel@.6, Thickness@.01}],Rectangle /@ {{0,0}, {1,0},{3,0}, {4,0},
{0,1}, {1,1},{3,1}, {4,1}, {1,3}, {2,3}, {3,3}, {4,3}, {0,3}},
FaceForm[White], Rectangle /@ {{2,0},{2,1},{2,2}, {3,2}, {4,2}, {1,2}, {0,2}},
Text[Style["1",22] ,{2.5, .5}],
Text[Style["2",22] ,{2.5, 1.5}],
Text[Style["3",22] ,{2.5, 2.5}],
Text[Style["4",22] ,{3.5, 2.5}],
Text[Style["5",22] ,{4.5, 2.5}],
Text[Style["6",22] ,{1.5, 2.5}],
Text[Style["7",22] ,{.5, 2.5}]}, Frame->!True, PlotRangeClipping ->True, PlotRange->{{-.1,5.1}, {-.1, 3.25}}]

Implementation

loadImage[thin_,original_]:=(railwayMaze=original;thinData=ImageData[thin];Clear[forbiddenList];)

isVertex[v_]:=(thinData[[v[[1]],v[[2]]]]==1);

pointNeighbors[{x_,y_}]:=Quiet@Select[{{x-1,y-1},{x-1,y},{x-1,y+1},{x,y-1},{x,y+1},{x+1,y-1},{x+1,y},{x+1,y+1}},isVertex]

degree[v_]:=Length[pointNeighbors[v]]

To peform the breadth-first search, we need to set up a queue:

put[e_]:=(Q[tail++]=e) (* put something on queue *)
get:=Q[head++] (* get something from queue *)
qlen:=tail-head (* queue length *)

The queue members will have the form {v, h}, where v is a vertex to be visited and h is a list containing histlen predecessors of v.

histlen=8;

At every junction, we measure the turning angles between the ingoing direction and outgoing directions. Permissible continuations are those where the corresponding angle does not exceed a certain threshold (found experimentally).

measureAngle[{v1_,v2_}]:=Module[{α},If[v1=={0,0}||v2=={0,0},0,α=N[ArcTan@@v1-ArcTan@@v2];Min[Abs[α],Abs[α-2 π],Abs[α+2 π]]]]
angleThreshold=70°;

Given a vertex v and its predecessor p, goForward proceeds forward, stops after the given number of steps, and returns the final coordinates.

goForward[{v_,p_},steps_]:=First@Nest[{First@DeleteCases[pointNeighbors[#[[1]]],#[[2]]],#[[1]]}&,{v,p},steps]

Given a vertex v with degree at least 3 (i.e., a junction) and its predecessor p, findDeg2Neighbors proceeds forward in all possible directions until it finds degree 2 vertices; these vertices are returned together with their predecessors. The implementation is based on a breadth-first search.

findDeg2Neighbors[v_,p_]:=Module[{q={{v,p}},checked={p},x,deg2Neighbors={},neighbors},
While[Length[q]>0,{x,q}={First[q],Rest[q]};AppendTo[checked,First@x];
neighbors=pointNeighbors[First@x];
If[Length[neighbors]==2,AppendTo[deg2Neighbors,x],q=Join[q,Map[{#,First@x}&,Complement[neighbors,checked,Map[First,q]]]]]];
deg2Neighbors]

For a given vertex v and its history h (which is a list of histlen predecessors), permissibleContinuations[v,hist] finds permissible continuations of v which should be put in the queue. In case of a degree 2 vertex, there is only one possible continuation. For higher degree vertices, we apply the angle measuring method.
We keep track of already visited vertices: If visited[v,p] is set to True, it means that vertex v was already visited with p as its predecessor and should not be put in the queue again. (The predecessor is important because we need to distinguish directions.)
Moreover, the user can supply a forbiddenList variable consisting of pairs of vertices. This prohibits going from the first vertex in a pair to the second vertex in that pair.

permissibleContinuations[v_,hist_]:=Module[{n=pointNeighbors[v],permissible={}},
If[Length[n]==2,permissible=Map[{#,v}&,DeleteCases[n,First@hist]]];
If[Length[n]>=3,permissible=Cases[findDeg2Neighbors[v,First@hist],n_/;(measureAngle[{v-hist[[8]],goForward[n,7]-v}]<angleThreshold)]];
DeleteCases[permissible,{x_,_}/;visited[x,v]||MemberQ[Map[Last,Cases[forbiddenList,{v,_}]],x]]]

Perform a breadth-first search from the given start and try to reach the given end. After reaching the end, we reconstruct the whole path using the information stored in the predecessor variables. We generate a message if no solution was found.

findOneSolution[start_,end_]:=Module[{v=start,h,hist,toAdd,sol={end}},head=1;tail=1;Clear[Q];Clear[visited];Clear[predecessor];
put[{start,ConstantArray[start,histlen]}];
While[v!=end &&qlen>0,{v,hist}=get;
toAdd=Union@Map[{#[[1]],Prepend[Most[hist],#[[2]]]}&,permissibleContinuations[v,hist]];
Map[(If[!ListQ[predecessor[{First[#],First[Last[#]]}]],put[#];predecessor[{First[#],First[Last[#]]}]={v,First@hist}])&,toAdd]];
If[v==end,
h=First[hist];While[h!=start,{v,h}=predecessor[{v,h}];PrependTo[sol,v]];Prepend[sol,start],
Message[findOneSolution::nosoln];{}]]
findOneSolution::nosoln="No solution found.";

Visualization functions:

transform[h_][{x_,y_}]:={y,h-x}

showOneSolution[s_]:=Show[railwayMaze,Graphics[{Red,Point[Map[transform[ImageDimensions[railwayMaze][[2]]],s]]}]]

showOneSolutionAnimation[s_,highlight_:{},tmax_:1,opts___]:=With[{h=ImageDimensions[railwayMaze][[2]],img=railwayMaze},Manipulate[Show[img,Graphics[{Red,Point[Map[transform[h],Take[s,t]]],Yellow,Point[Map[transform[h],highlight]],PointSize[0.02],Lighter@Blue,Point[transform[h][s[[t]]]]}],opts],{{t,tmax},1,Length[s],1,ControlPlacement->Top},SaveDefinitions->True,TrackedSymbols->True]]

showSolutionWyes displays a solution and mark all junctions along the way. The junctions have tooltips with pixel coordinates.

showSolutionWyes[s_]:=Module[{wyes,h=ImageDimensions[railwayMaze][[2]]},wyes=Map[{s[[#]],s[[#+1]]}&,Map[First,Position[s,v_/;degree[v]>2]]];
Show[showOneSolution[s],Graphics[{PointSize[Large],Lighter@Blue,Map[Tooltip[Point[transform[h][First[#]]],#]&,wyes]}]]]

Solving the simplest maze

loadImage[thin1,original1]

Coordinates can be obtained by right-clicking (or control-clicking) the image and using Get Indices.

start={133,80};
end={155,477};

soln1=findOneSolution[start,end];

showOneSolution[soln1]

showOneSolutionAnimation[soln1]

Looking for other solutions

Given a solution s going from start to end, findOtherSolutions tries to find other possible paths between the two vertices. For every edge along s, we check whether there exists a path from start to end which avoids this edge (using the same BFS algorithm as before).

findSolutionEdges[s_]:=Module[{deg3},
deg3={0}~Join~Map[First,Position[s,v_/;degree[v]>2]]~Join~{Length[s]+1};
Table[s[[deg3[[i]]+1;;deg3[[i+1]]-1]],{i,1,Length[deg3]-1}]]

findOtherSolutions[start_,end_,s_]:=Module[{edges,f=forbiddenList,sol,i=0,other={}},If[!ListQ[f],f={}];edges=findSolutionEdges[s];Monitor[Do[forbiddenList=Join[f,Partition[edges[[i]],2,1]];sol=Quiet@findOneSolution[start,end]; If[sol≠{},AppendTo[other,{sol,edges[[i]]}]],{i,1,Length[edges]}],StringForm["``% done.",Round[100.i/Length[edges]]]];forbiddenList=f;other=DeleteDuplicates[other,(First[#1]==First[#2]&)];Print["Number of alternative solutions found: ",Length[other]];other]

showOtherSolutions[sol_,other_]:=Manipulate[Grid[{{"Original solution","Alternative solution"},{showOneSolutionAnimation[sol,other[[i,2]],Length[sol],ImageSize->Scaled[2/5]],showOneSolutionAnimation[other[[i,1]],{},Length[other[[i,1]]],ImageSize->Scaled[2/5]]}}],{{i,1,"alternative solution number"},1,Length[other],1,Appearance->"Open"},SaveDefinitions->True,SynchronousInitialization->False,SynchronousUpdating->False,TrackedSymbols->True,ControlPlacement->Top]

findOtherSolutions[start,end,soln1];

A harder maze

original2=;

bw2=DeleteSmallComponents@ColorNegate@Binarize[original2,.75]

thin2=DeleteSmallComponents[Pruning[Thinning[Binarize[GaussianFilter[bw2,2],0.45]],{Infinity}]]

loadImage[thin2,original2]

start={510,332};
end={170,311};

soln2=findOneSolution[start,end];

showOneSolution[soln2]

showOneSolutionAnimation[soln2]

other2=findOtherSolutions[start,end,soln2];

showOtherSolutions returns a demo which allows an easy comparison between the original solution (shown in the left part) with alternative solutions found by findOtherSolutions (shown on the right). The alternative solution avoids the yellow edge highlighted in the left part.

showOtherSolutions[soln2,other2]

Note that we are dealing with oriented edges. Thus, although solution 2 looks identical to the original solution, it traverses the loop on the right in the opposite direction. Solution 1 differs only in the short initial segment and is in fact identical to the original solution.

Another difficult maze

original3=;

bw3=DeleteSmallComponents[ColorNegate[Binarize[original3]]]

thin3=Pruning[Thinning[Binarize[GaussianFilter[bw3,2],0.5]],{Infinity}]

loadImage[thin3,original3]

start={123,183};
end={741,570};

soln3=findOneSolution[start,end];

showOneSolution[soln3]

showOneSolutionAnimation[soln3]

other3=findOtherSolutions[start,end,soln3];

showOtherSolutions[soln3,other3]

Solutions 1 and 2 show two other possible ways to pass through the upper right region.

Solution 3 traverses the middle bottom loop in the opposite direction.

Solutions 4–8 show alternative ways of going through the upper left region.

Solution 9 is identical to the original solution (it uses a small artifact in the image).

Solution 10 is incorrect (illegal turn in the bottom region).

Assume that we don’t count simple loop-reversals as being different. Then solutions 4 and 5 are the same, and also 7 and 8 represent the same solution. 
To sum up, we have three distinct ways to pass through the upper right region, and four distinct ways to go through the upper left region. These possibilities can be combined against each other, which gives at least 12 distinct solutions of the current maze (note that there might be other solutions that we haven’t found).

The necessity of manual intervention

original4=;

bw4=DeleteSmallComponents[ColorNegate@Binarize[original4,.4]]

thin4=Pruning[Thinning[Binarize[GaussianFilter[bw4,2],0.5]],10]

loadImage[thin4,original4]

start={945,433};
end={217,512};

soln4=findOneSolution[start,end];

showOneSolution[soln4]

This solution is clearly incorrect as it contains illegal moves in the lower right and middle left part. The coordinates of the problematic places can be found using showSolutionWyes.

showSolutionWyes[soln4]

Each junction has a tooltip corresponding to a pair of points. We add the wrong moves to forbiddenList, which forces the algorithm to try to find a different route.

forbiddenList={{{649,168},{650,170}},{{896,742},{896,744}}};

soln5=findOneSolution[start,end];

showSolutionWyes[soln5]

Again, there is an error in the upper middle part.

AppendTo[forbiddenList,{{95,368},{95,367}}]

soln6=findOneSolution[start,end];

showSolutionWyes[soln6]

One more error in the same part.

AppendTo[forbiddenList,{{95,368},{94,369}}]

soln7=findOneSolution[start,end];

showSolutionWyes[soln7]

This solution is finally correct!

showOneSolutionAnimation[soln7]

other4=findOtherSolutions[start,end,soln7];

showOtherSolutions[soln7,other4]

Solutions 1–2, 13 are identical to the original solution (artifacts in the image).

Solutions 3–4 are incorrect.

Solution 5 traverses the loop in the middle right part in the opposite direction.

Solutions 6–12 show alternative ways of passing through the middle left part.

Assume again that we don’t count simple loop-reversals as being different. Then solutions 6 and 12 are identical, 7 and 11 are identical, 8 and 10 are identical, and 9 is the same as the original solution. 
To sum up, we have four distinct ways to pass through the middle left part, i.e. at least 4 distinct solutions of the current maze (again, there might be other solutions that we haven’t found).

Possible projects

Solve the last maze without manual intervention.

Design a program that will automatically generate railway mazes.

Find other types of mazes that are worthy of investigation and automation in this way.

References

R. Penrose, Railway mazes, in A Lifetime of Puzzles, E. D. Demaine, M. L. Demaine, T. Rodgers, eds.,
AK Peters, Wellesley, Mass., 2008, 133–148.

A. Slavík and S. Wagon, Railway Mazes: From Picture to Solution, Journal of Recreational Mathematics vol. 36, no. 3 (2011), 208–221.

A. Slavík and S. Wagon, Penrose’s Railway Mazes, http://demonstrations.wolfram.com/PenrosesRailwayMazes/.