A few days ago I posted the following puzzle to my Google+ stream:
Can you find a route around the London Underground map taking in exactly one stop on each line (including DLR and Overground)? That is, get on the tube at one station, go one stop, change to another line, lather, rinse, repeat until you’ve been on every line.
I teased that I had a solution but I wanted to give people some time to work on their own solutions before describing my own. If you feel like giving it a shot, stop reading now. I’m about to describe how I went about finding a solution.
I started by recognising that any path between two stations that had only a single line but more than one leg could not be part of the solution. For example, the (direct) journey from Baker Street to Oxford Circus uses only the Bakerloo line but takes in an extra stop at Regent’s Park along the way, so it can’t be used if we’re to travel only one stop on each line.
There’s a bit more flexibility for a route that’s covered by more than one line. For example you would be allowed to travel from South Kensington to Victoria via Sloane Square by using the Circle line for one leg and the District line for the other. But you’re limited here to journeys of no more than two stops along these lines. Similarly, you can go three stops along the short route served by the Metropolitan, Circle and Hammersmith & City lines.
So I took the standard Tube map (above) and opened it in a graphics editor, and just started erasing pieces that couldn’t possibly form part of the solution. I left only stations that are served by more than one line, and which are connected directly (over a single-leg journey) to other stations served by more than one line.
Actually this approach removes some stations that could still potentially form part of a solution, because the two stations at the start and end of your route don’t need to be served by more than one line. It would be a simple matter to add those stations back at the end if it turned out to be necessary (though in fact it doesn’t).
Once I had my trimmed down map it was very easy to see that there would be a pretty even split with about half of the lines being west of the Waterloo & City line and half being east. The Waterloo & City line was really what made this a tractable problem, because it forces you to use Bank and Waterloo stations in any solution.
I spent a bit of time convincing myself it was impossible to get from the Metropolitan or Hammersmith & City lines down to Waterloo (via either Kings Cross or Baker Street), so those had to be on the east side of the solution. Victoria, Piccadilly and Bakerloo were all obviously on the west. The DLR could only ever have been on the east side, as could the Overground. The Jubilee looked unlikely to fit on the east. The Central, Circle, District and Northern lines were a bit more ambiguous, but it’s quite easy to show that you can’t get from Waterloo to the Piccadilly line without using at least two of Northern, Circle or District.
That reduced the field enough to just try out a few variations. The route I finally came up with was:
- Start at Moorgate
- Take the Metropolitan line to Liverpool Street
- Take the Hammersmith & City line to Aldgate East
- Take the District line to Whitechapel
- Take the Overground to Shadwell
- Take the DLR to Bank
- Take the Waterloo & City line to Waterloo
- Take the Jubilee line to Westminster
- Take the Circle line to Embankment
- Take the Northern line to Charing Cross
- Take the Bakerloo line to Piccadilly Circus
- Take the Piccadilly line to Green Park
- Take the Victoria line to Oxford Circus
- Take the Central line to Bond Street
Of course you could substitute Aldgate for Moorgate and/or Tottenham Court Road for Bond Street, or do the whole thing in reverse. Aside from those variations, I think this is the only possible solution, though I haven’t proved it.