The Game of Carcassonne and the Parity Problem

Christmas 2006: The Urban Challenge

Over the Christmas 2006 break I was playing the board game Carcassonne with my family. After a competitive game that my daughter won, we decided to do cooperative urban planning: build a nice layout of cities. We came up with one we liked, then wondered if anyone else had done the same, and what their design criteria were. A quick search found a blogger named Aaron who stated ``One primary goal was to set the board up such that it was completely contained; that is, set up such that no cities and roads led off of the board.'' That seemed like a good goal, but Aaron was unable to completely achieve his goal: one tile had one city portion going off the edge of the map. He said he would ``probably give it another try in the coming days.'' That was January 2005, and there was no follow-up post. Did he just get distracted and not try again? Think about it ...

Here's an analysis of why Aaron (or anyone else) is doomed to failure on this goal. First, define a city-edge to be any city-colored edge of a tile. A given tile can have from zero to four city-edges. Now for all the cities to be self-contained, every city-edge must abut another city-edge. That means the total number of city-edges must be even. But as Aaron showed, in fact the total number of city-edges in the basic set of tiles is odd. So no matter how you re-arrange the tiles, you won't be able to achieve the goal.

This is an example of a parity argument. We can prove that a given construction is impossible, without considering every possibility, because the parity of the solution is different from the parity of all possible arrangements. That's a good thing, because for each 72-tile rectangle there are 72! × 472 possible arrangements: over 10147. The most famous example of a parity problem is the mutilated chessboard problem.

There is a happy ending, however. We have the River Expansion Tiles for Carcassonne: a set of 12 additional tiles that contain river pieces, and happen to contain an odd number of city edges. Adding odd and odd we get an even total, and now it is theoretically possible to achieve the goal. And in a half hour or so, we were able to get this map:

I'm mostly happy with this. In the lower right there is one abbey that is upside-down and one sideways; I'd like them to be oriented rightside-up. In retrospect I'd like more cities to be closer to the river, although I thought it would be easier to use the river tiles as an edge. Thanks to Emmanuel Delaborde for explaining how to use the Photoshop Transform/Distort command to make this image more nearly rectangular.

Update: Christmas 2008: The Abbey Challenge

Over his Christmas break in 2008, Greg Auger and his family were doing pretty much the same thing I was doing in 2006. Greg added one more constraint: the abbeys had to be completely surrounded by squares (that is, not on an edge), because that way they score maximum points in the game. Since the abbeys have few or no connections, they are convenient to use as edge pieces, which is what my original solution mostly did. But Juliet and I decided to take up Greg's challenge, and we succeeded:

Again, I'm mostly happy with the result. The river starts in the mountains of the north and flows south. There is a clear distinction between the big cities of the north and the small ones of the southwest (although there are the medium twin-cities in the southeast). We retain the beautiful two-bridge approach to the river abbey, and then have a big abbey district in the south (making comparison shopping easier). The monks are apparently NASCART fans, because they have an oval racetrack on the southern border. The city folk are more into Formula I, as they have a figure-eight track reminiscent of Fiorano between the northern cities.

For next time, here are some more challenges:

1. Orient all the abbeys right-side up. I've left one abbey sideways.
2. Orient all the shields in the cities right-side up as well. (That will be tough....)
3. As Christopher Miller points out, the rules for The River Expansion state: 'Do not place a river tile so that the river makes a U turn' (which I believe means that two adjacent curves in the same direction are disallowed).
4. Abbeys score maximum points when they are surrounded by eight squares, so it would be better if they aren't on an edge.

Update: New Year's 2017: The Final Solution

I didn't get back to addressing these challenges, but Belinda Borman did. She sent me an impressive solution that satisfies all four of the challenges:

Peter Norvig