Imagine having a number of straight and curved train track segments (e.g. 90° to the left and right, but they could have other values in the general case), how is it possible to find all complete (closed) tracks that can be built with them (not necessarily using all elements)?

I suppose with a low number of track segments (<20), brute forcing the problem might still be an option, especially if their number of types/the "branching factor" is low - and it may not be practically feasible to generate all possible tracks for a larger number of track segments (?, I have no intuition how many there would be).

Still, it interests me what this general problem is called, and what methods could be used to generate at least some solutions, or arrive at their total count.

I've tried to use python-ortools to formulate this problem but failed.

The runtime of the algorithm should be practical even for a larger number of segments (50+), though it can take minutes or hours if required.

  • 3
    $\begingroup$ Your question needs a lot more clarification. Are the straight and curved pieces always one unit long, like such? i.imgur.com/GiCCTtg.png May the track self-intersect? May the track form a closed loop? May the track consist of multiple independent closed loops? $\endgroup$
    – orlp
    Commented Sep 8, 2023 at 21:23
  • 3
    $\begingroup$ What about rotational symmetry? What about mirror symmetry? Are these 2, 4, or 8 different tracks, or all the same track? i.imgur.com/q75cgZ5.png $\endgroup$
    – orlp
    Commented Sep 8, 2023 at 21:37
  • 3
    $\begingroup$ When you say you have "a number of straight and curved train track segments", do you mean you have $n$ segments, which can be freely chosen to be straight or curved, or do you have $s$ straight and $c$ curved segments? $\endgroup$
    – orlp
    Commented Sep 8, 2023 at 22:38
  • $\begingroup$ @orlp These are all very good points, and I could arbitrarily specify them, but since I don't have any specific collection of tracks myself, I'm more interested in the general names and potential solution approaches to these problems. $\endgroup$
    – 2080
    Commented Sep 9, 2023 at 5:54
  • $\begingroup$ @orlp The track pieces all being one unit long probably only works in the case where curves are 90°, which will probably make some approaches much simpler, though a solution for the general case would be interesting to see too $\endgroup$
    – 2080
    Commented Sep 9, 2023 at 5:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.