Overthinking Carcassonne

TL;DR

No.

Problem

Recently my brother became very interested in the game Carcassonne and while playing, he asked me a question:

Is it possible to create a 9×8 rectangle using all 72 Carcassonne tiles?

Carcassonne tiles Carcassonne tiles, from graphics.cs.cmu.edu

These are all the tiles used in the game. Let’s get started!

First approach: frickin brute force

My initial reaction was along the lines of:

Yea, of course possible, and if not a rectangle, there should be at least one formation of tiles that use all 72.

So I wanted to figure out all of the possible combinations to pave a rectangle. Here was my approach for a brute force algorithm.

1. Categorizing the tiles

Label all the tiles with what they contain, going clockwise from the north position.

For instance, the tile below will be labeled VRPR.

This is labeled VRPR This is labeled VRPR

To take into account that the tiles can be rotated, we can shift letters in the label. The last tile rotated 90° clockwise makes it RVRP.

The previous tile rotated 90° clockwise VRPR rotated 90° clockwise

2. Following the rules

The base rule of the game is that tiles placed next to one another need to have similar sides. For instance, the formation above is valid, but below isn’t.

Valid formation Valid formation

Invalid formation Invalid formation

In terms of labels, two tiles can be placed next to each other if the letters corresponding to opposite sides are equal. To get the letter of a label corresponding to an orientation, we can assign each direction to a number to lineup with the order in which we labeled the sides. North is 0, East is 1, South is 2, and West 3. This way, the index of the letter in the label corresponds to its orientation. In our example, "VRPR"[1] yields R, because there is a road on the East side of the tile.

The PPRR tile The PPRR tile

If we want to place PPRR on the east side of the VRPR, we need to check if the west side is also a road. And sure enough, "PPRR"[3] yields "R", so the placement of PPRR on the east of VRPR is valid.

We see that adding two to the direction gives the opposite direction, as long as you keep the value between 0 and 3. This you do using the modulo function: 2+2=4 becomes 0 (North), 3+2=5 becomes 1 (East), etc. So generally, this condition needs to be true for a placement to be correct: tileA[direction] === tileB[(direction+2)%4], being the modulo operator.

The brute force algorithm will need to check if a placement is valid using this function:

function isValidPlacement(tileA, tileB, direction) {
    if (tileA[direction] === tileB[(direction+2)%4]) {
        return true;
    } else {
        return false;
    }
}

Or, simplified,

function isValidPlacement(tileA, tileB, direction) {
    return tileA[direction] === tileB[(direction+2)%4]
}

3. Brute force, baby

The time has come to tackle the brute force algorithm. After thinking for a bit, here is what I came up with.

  1. Create a list of length 72 containing all the tiles (even if the same tile gets repeated)
  2. Create an empty 2-dimentional array. This is a grid which tracks the progress of the algorithm
  3. For every cell in the grid (starting from the upper left side), try to place a tile of the list
    • If it is possible
      1. Remove the tile from the list of tiles
      2. Add the tile to the grid
      3. Move to the next cell: neighbor right if possible, next row left if not
    • If it is not, rotate the tile and try again
    • If the list of usable tiles has been depleted, it means that the current combination is not a possible solution
      • Go back one step
      • Remove possible tile at that spot
      • Try next tile on the list
    • For cells located at the edge of the grid, you can suppose the outer wall of the rectangle is composed of plains only
  4. When you arrive at the last cell and a possible tile has been found, display the grid and act as if the tile is not valid

I’ve not yet implemented this algorithm in JavaScript, but I reckon it should be straightforward.

4. Wait, how many iterations?

I had done all of this without asking a crucial question: how many iterations will the brute force algorithm have to go through?

Well, you start with 72 tiles. Once you place the first tile, you’ll be left with 71 tiles to choose from for your next move. Then you’ll be left with 70, then 69, and so on until 1. So the number of possible combinations is 72×71×…×1=72!=6×10103, that’s 6 and 103 zero’s behind it, which is 1021 times as many atoms as there are estimated to be in the universe[1]. And that’s not even taking rotation into account[2]!

Mind = blown Mind = blown

Bad news for me but good for my CPU, the brute force algorithm wasn’t going to work.

Proof by counterexample

I was pretty bummed, but then it dawned on me that in science, it’s often much easier to prove something is false than to prove it is true. The new question then is: how do we prove that you can’t pave a surface with all the Carcassonne tiles?

What could possibly make the challenge impossible? Well, let’s look at villages. When you create a village, you have to start with a wall. To close said village, you also need a wall, and to extend it, you need walls on both sides perpendicular to the direction of the extension. Altogether, all villages in Carcassonne have an even number of walls.

Examples of villages A perfectly fine village has an even number of walls

And because you can’t just leave a village open (even on the border of the grid, otherwise it would be too easy), the challenge is only possible if the total number of walls is even.

Carcassonne tiles Let’s count the walls!

There are a grand total of 63 walls in the basic Carcassonne tiles, and we all know what that means…

Conclusion

It is impossible to use all the Carcassonne tiles to construct a rectangle or any figure, really.

However hard you might try and be close to succeeding the challenge, you’ll always be left with one open village.

That’s about it, thank you for reading!


  1. Universe today, How Many Atoms Are There in the Universe? ↩︎

  2. Most of the pieces can be rotated 4 times (with the exceptions of the RPRP pieces, which present one axis of symmetry), so the total number of iterations is just about (72×4)!=7×10584 ↩︎