# Is it possible to form a shape with all the Carcassonne tiles?

*Posted July 3rd, 2018, Standalone archive*

## TL;DR

No, it’s mathematically impossible.

## 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, 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 coursepossible, 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.

`V`

indicates village wall`R`

a road`P`

plains

For instance, the tile below will be 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`

.

`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*

*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*

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.

- Create a list of length 72 containing all the tiles (even if the same tile gets repeated)
- Create an empty 2-dimentional array. This is a grid which tracks the progress of the algorithm
- For every cell in the grid (starting from the upper left side), try to place a tile of the list
- If it is possible
- Remove the tile from the list of tiles
- Add the tile to the grid
- 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

- If it is possible
- 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×10^{103}, that’s 6 and 103 zero’s behind it, which is 10^{21} 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*

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

## Proof by disproof

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.

*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.

*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!

Universe today,

*How Many Atoms Are There in the Universe?*↩︎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×10^{584}↩︎