Train track assembly algorithm [closed]

Question

I recently bought a toy train for my kid. And when assembling it I wondered if I could create an app where you put in what peaces and how much of them you have and the result is track diagram, with at leased one closed circuit. So, my input will be how much peaces I have from each type, this is the types:

And the output will be something like this:

What algorithm can I use for implementing this, and if you have any suggestion or pointers please tell me.

Answer 1

You could use a brute force approach where you start with piece one and then try all the remaining pieces for piece two and then all the remaining ones for piece three and so on. You'd build up lots of layouts in parallel, for example

Piece1-Piece2-Piece3-...

Piece1-Piece3-Piece4-...

Piece1-Piece4-Piece5-...

...

(Where - indicates a join).

When you get to a point that the layout becomes invalid you could stop and cross it off your list.

An advantage of this approach is that it will find a solution if there is one. A disadvantage is that it could take a long time.

If you're after a single layout the question is how to determine which is "best". One way to do this might be to assign different weightings to different pieces and then you could assess your layout using these scores.

You could optimize this by categorizing your pieces, for example into straight ones and curved ones, and then making some deductions based on how many of each you have. For example, if you have 4 curved pieces and 16 straight pieces you could conclude that you've got 4 corners and the others must be the sides. So from this starting point you would come up with several layouts in parallel and when you get to a point that the layout becomes invalid you could stop and cross it off your list.

Another optimization might be to create a list of sample layouts and build on those. For example, if you had a sample loop layout as a starting point you could try replacing one of your straight pieces with a set of points and then building from there.