Forty-Seven For The Win

Last time, I told you that to construct any road shape you wish, you needed forty-seven distinct tiles, and that it was a very unwholesome number. Today, we take a look at how I arrived at that number.

To begin, let us first revisit how the previous method used to enumerate the required tiles, and identify where it is deficient. We constructed the tiles by enumerating the 2^4 different possible configurations of tiles in the four cardinal directions from our tile of interest. This was deficient because what we must actually do for arbitrary shapes is enumerate the possible configurations of all eight cardinal directions: north, northeast, east, southeast, south, southwest, west, and northwest. This gives 2^8=256 options, and is a much larger number than the proposed solution of forty-seven.

We know that the solution for the arbitrary-shape solution is a superset of the solution for the road-shap problem, so sixteen of the forty-seven tiles must be the sixteen from the previous post. We are left with the following information:

The problem, once again, is that the tiles don't link up along the diagonals. As a starting point, let's consider the bottom tile, which connects to all four lateral neighbours. It does not connect to any of its diagonal neighbours. Let's try producing different versions of that tile that do link up diagonally. We find that there are four diagonal neighbours, and so we should get 2^4=16 different forms, and we do:

This is a fairly satisfying result. There is a nice parallel between the sixteen different lateral neighbour options and the sixteen diagonal options. One of the tiles is doing double-duty, so we only have thirty-one, not thirty-two, but we can live with that.

Let's now continue using this approach with the other lateral configurations:

Hmm. That didn't generate as many as we might have hoped. Four of the tiles only have a single 'corner', and so there are only two configurations. Four more have only two 'corners', and they only generate 2^2 = four configurations.

It turns out, however, that we have actually generated all the tiles we require. (If you count them, there are forty-seven, as promised). Some of the tiles can be recycled in multiple configurations, and the rules for when they can be recycled can be summed up with the following lemma:

A given road square is only sensitive to whether its north-eastern neighbour is a road square, if both its north and east neighbours are roads. (Analogous statements can be made for the other three diagonals.)

Consider a road square connecting to the west and south. According to the lemmas, only the southwest diagonal neighbour will impact which tile is used. The other three diagonals do not. Thus, we expect that the tile can be reused in 2^3 = eight different configurations, and that is indeed the case:

It also turns out that forty-seven isn't that unwholesome a number after all, since 47 = 16 * 3 - 1. If you include the not-road tile (all green, in our example), you get forty-eight, which isn't so bad after all.

For concreteness, here are all fourty-eight tiles in our road-and-grass example:

They can be used to produce the thick road we desired from the previous example:

Beauty.