# Metroville: the confluent drawing puzzle

I just returned from a pleasant post-SoCG visit to Bettina Speckmann in the Netherlands. While there, she presented me with a copy of Metroville, a puzzle based on confluent drawing. (Image below stolen from the manufacturer's web site.)

Metroville consists of a game board with nine rotating pieces on it, each containing a section of train track with turns and junctions. The pieces can be permuted to form eight different "cities", and for each city there are eight puzzles, in which one must rotate the pieces so that the resulting configuration of track can allow a train to pass through a given sequence of cities in order without reversals.

I haven't worked out the details, but I'm pretty sure that larger versions of the game would be NP-complete (that is, it should be NP-complete to test, for a fixed city, whether there exists a set of rotations that allows a given train route to work) by a reduction from 3-SAT very similar to the one in my Phutball paper in which the train zigzags horizontally across the board through tracks representing variables and then zigzags again vertically through tracks representing clauses.

Regardless, it's a fun puzzle. Thanks, Bettina!

Also, slides from Elena Mumford's talk on area-universal cartograms (my SoCG paper with Bettina, Elena, and Bettina's student Kevin Verbeek) are now online.