Minimum Number of Wagons to Connect Every City in Ticket to Ride – Europe

How many wagons would you need to create a route network in the board game Ticket to Ride – Europe so that every city is connected to every other city through the network?  If you could do this you could potentially earn every destination ticket in the game.

To answer this question, we first need to make a graph out of the Ticket to Ride – Europe map.  We need to represent each city by a vertex, and we need to represent each city-to-city route by an arc with weight equal to the number of wagons it takes to claim that particular route.  Then the question entails finding a minimum spanning tree that connects all the vertices in this graph.  The total weight of the minimum spanning tree will be the answer to our question.

Fortunately, there are some fast algorithms for finding minimum spanning trees, and some of them are simple enough that we can easily perform them by hand.  For this post we’ll use Prim’s algorithm, which involves the following steps:

  1. Start at any vertex to initialize the tree.
  2. Select a minimum-weight arc that is not in the tree but that connects a vertex in the tree with one not in the tree.  Add that arc and the new vertex to the tree.
  3. Repeat Step 2 until all vertices are in the tree.

Edinburgh is a logical city in which to start, since from there the only choice for arc is the 4-wagon route to London.  Add London and the route from Edinburgh to London to our tree.

Now, there are two minimum-weight arcs out of Edinburgh or London to new cities.  These are the two-wagon routes from London to Amsterdam and from London to Dieppe.  It actually doesn’t matter which one we pick; the proof of correctness for Prim’s algorithm tells us that either would lead to a minimum spanning tree, even if we don’t eventually choose the other route for our tree.  Let’s take alphabetical order as the tiebreaker and choose the London to Amsterdam route for two wagons.

In the next iteration the shortest route available to us isn’t the two-wagon route from London to Dieppe; it’s the one-wagon route from Amsterdam to Bruxelles.  So we must take that one.

Next iteration: There are multiple two-wagon routes available now: London to Dieppe, Bruxelles to Dieppe, Bruxelles to Paris, Bruxelles to Frankfurt, and Amsterdam to Frankfurt.  Alphabetical order for the new city gives us Dieppe, and alphabetical order again would select Bruxelles over London as the city to connect Dieppe to.  (Again, any of these choices would give us a minimum spanning tree at the end, so all we need is some tiebreaker criterion.)

Next choice is Dieppe to Paris for one wagon.

In the next iteration there are multiple two-wagon routes available again: Dieppe to Brest, Bruxelles to Frankfurt, and Amsterdam to Frankfurt.  We do not include the London-to-Dieppe route or the Bruxelles-to-Paris route because we only consider arcs from cities already in our tree to new cities.  Alphabetical order as the tiebreaker criterion means we select Dieppe to Brest as our new arc.

From here, I’ll just list the remaining arcs that are added, in order of selection (again using our alphabetical order tiebreaker).  For completeness I’ll include the arcs and vertices we’ve already selected.

  1. Edinburgh (start)
  2. Edinburgh to London (4 wagons)
  3. London to Amsterdam (2)
  4. Amsterdam to Bruxelles (1)
  5. Bruxelles to Dieppe (2)
  6. Dieppe to Paris (1)
  7. Dieppe to Brest (2)
  8. Amsterdam to Frankfurt (2)
  9. Frankfurt to Essen (2)
  10. Essen to Berlin (2)
  11. Frankfurt to Munchen (2)
  12. Munchen to Venezia (2)
  13. Venezia to Roma (2)
  14. Roma to Brindisi (2)
  15. Venezia to Zagrab (2)
  16. Zagrab to Budapest (2)
  17. Budapest to Wien (1)
  18. Munchen to Zurich (2)
  19. Zurich to Marseille (2)
  20. Essen to Kobenhavn (3)
  21. Brindisi to Palermo (3)
  22. Budapest to Sarajevo (3)
  23. Sarajevo to Sofia (2)
  24. Sofia to Bucuresti (2)
  25. Sofia to Athina (3)
  26. Athina to Smyrna (2)
  27. Smyrna to Constantinople (2)
  28. Constantinople to Angora (2)
  29. Angora to Erzurum (3)
  30. Erzurum to Sochi (3)
  31. Sochi to Rostov (2)
  32. Rostov to Kharkov (2)
  33. Sochi to Sevastopol (2)
  34. Kobenhavn to Stockholm (3)
  35. Marseille to Barcelona (4)
  36. Barcelona to Madrid (2)
  37. Barcelona to Pamplona (2)
  38. Madrid to Cadiz (3)
  39. Cadiz to Lisbon (2)
  40. Berlin to Danzig (4)
  41. Danzig to Warszawa (2)
  42. Danzig to Riga (3)
  43. Warszawa to Wilno (3)
  44. Wilno to Kyiv (2)
  45. Kyiv to Smolensk (3)
  46. Smolensk to Moskva (2)
  47. Moskva to Petrograd (4)

This gives us a total of 108 required wagons.  Since you only have 45 wagons you can play in a game of Ticket to Ride – Europe, you can’t get anywhere close to connecting all of the cities in this game.  Even two complete sets (i.e., 90 wagons) wouldn’t be enough.  (We haven’t considered stations in this analysis, but even if you play all three of your stations to substitute for the three four-wagon routes required in the minimum spanning tree, you still need 96 wagons to complete the rest of the tree.)

So, even if it were possible in the game to hold all the destination tickets, you cannot actually earn them all.  (That should not surprise anyone who has played Ticket to Ride – Europe, I imagine.)  What may be a bit more surprising is what our answer of 108 implies about just how far from possible it is to earn every destination ticket.

A couple of fun observations: (1) At one point Zagrab actually wins the alphabetical order criterion!  This is because the alternative choice is Zurich.  (2)  For quite a long time after selecting Edinburgh to London we can avoid choosing a route that requires more than two wagons.  This is because many of the cities in northwestern and central Europe on the map are connected by only one- or two-wagon routes.

This entry was posted in combinatorial optimization, games, graph theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s