While playing the 18xx games (create routes for trains and try to get the most money with your trains), it sometimes takes a lot of time to find the optimal route for the trains.
Does anybody know if there is any software available to help with this problem?
Not to my knowledge.
One thing I've done to assist with this problem is to use a pile of D6's of a couple different colors.
Place a D6 on each city of one color to represent your smallest train and work your way up to your largest.
When you are finished, pick up the D6's generating your total run profit as you go.
Towards the end of the game, we usually help each other, as the diesel runs can become quite dramatic as I'm sure you're aware! It just speeds the game along as we don't want one person obsessing over his run for twenty minutes to gain an extra $10.
See https://www.reddit.com/r/18XX/comments/9t32gw/1846_route_finder/
The decision problem "Given this particular network, can a diesel (unbounded) train run for at least $X?" is NP-complete.
It's in NP, since the length of a route is bounded by the size of the board and its validity and payoff is easily verifiable.
It's NP-hard by a reduction from Hamiltonian path on square grids. Embed the square grid on a hex board by skewing one axis 60°. Use X-cities for vertices in the input graph and use lots of straights to connect the vertices. Place a station in an arbitrary vertex/city. There's a route worth k×n where k is the per-city dividend and n is the number of cities if and only if there's a Hamiltonian path in the input graph (with the obvious correspondence).
I don't know about hardness for bounded trains, but for practical purposes the train limit is O(1) and the train lengths are also O(1), and most notably the numbers tend to be small(ish).
For example, with 10 cities and a single 6, there are 10 choose 6 = 210 different city sets to try out. You can sort them by dividends and the answer is the first feasible route.
With 10 cities and a 5, there are 252 possibilities. With both a 5 and a 6 that's 210*252 = 52920. Once again, sorting by total dividends and finding the first feasible match should be tolerably fast.
Or maybe you find the highest-paying routes with each train unconstrained by the other, then search through two lists for a compatible match. Say you look through the 6-routes in descending order; then you have to look past the first compatible match, until you get to a 6-route which pays so little that even the best paying 5-route doesn't put you above the best match so far. Then that best match cannot be surpassed, and must be the answer.
