The math behind Carcassonne tiles

[Nareau]

If you haven't played Carcassonne, it's a little like dominoes in that you lay down tiles that have to match up edge-to-edge.

Each tile has 4 sides, and each side can have 3 different "features": A road, city, or meadow (R, C, or M).

I think this is a pretty simple permutation problem, but there's a twist in it. If you read the sides of the tile in a clockwise fashion, you might get: Road, Road, Road, City.

RRRC is the same as RRCR, RCRR, CRRR because the sides wrap around.

But a tile that is CCRR is not the same as CRCR.

Am I overthinking (or underthinking) this? Can someone help me figure out how many possible different tiles there could be?

Nareau

 

[prosfilaes]

At most, there's 3^4=81 possibilities. At worst, you can always write them all down.
One colored: 3
Two colors: any two tiles with one side one color and the rest of the sides another are the same, so there's 3*2 = 6 possibilities. If we have two sides one color, two sides the other, a color can either be across from itself or next to itself, so 2 * 3 * 2 = 12.
Three colors are more complex. If we label them starting with the duplicate color, then I think there's 3*3*2*1 = 18 possibilities, though some of them might be equivalent. So there should be at most 39 different tiles.

 

[Hypersmurf]

As far as I can tell, it's 24:
RRRR
RRRC
RRRM
RRCC
RRCM
RRMC
RRMM
RCRC
RCRM
RCCC
RCCM
RCMC
RCMM
RMRM
RMCC
RMCM
RMMC
RMMM
CCCC
CCCM
CCMM
CMCM
CMMM
MMMM

-Hyp.

 

[Pseudopsyche]

If you haven't played Carcassonne, it's a little like dominoes in that you lay down tiles that have to match up edge-to-edge.

Each tile has 4 sides, and each side can have 3 different "features": A road, city, or meadow (R, C, or M).

I just wanted to point out that the feature space you gave is not sufficient to discriminate among actual Carcasonne tiles. Consider that the game has two different tiles that have the MCMC feature, one in which the two city edges belong to the same city and one in which the two city edges belong to separate cities.

That said, I don't know the answer to the question you posed regardless.

 

[Nareau]

I just wanted to point out that the feature space you gave is not sufficient to discriminate among actual Carcasonne tiles. Consider that the game has two different tiles that have the MCMC feature, one in which the two city edges belong to the same city and one in which the two city edges belong to separate cities.

That said, I don't know the answer to the question you posed regardless.

I know. I also neglected to include internal features (such as cloisters). For the purpose of this exercise, I'm just looking for edge combinations.

I'm interested because I'd like to catalog all the tiles we've got, and be able to keep a list of "how many of what tiles" exist. I think that will help newcomers to the game predict what areas they'll be able to complete. Kind of like how Scrabble has a list of how many of each letter tiles are in the game.

Nareau

 

[orsal]

Let's work with the problem as you framed it for simplicity, ignoring philomath's comments. Start with 81, which is the number of *oriented* tiles (considering e.g. RCRR different from RRRC). Now, 9 of these have 2-fold symmetry (i.e. both pairs of opposite sides are identical), so there are 72 without any rotational symmetry. 3 of those 9 have 4-fold symmetry (all sides identical); the other 6 have only 2-fold symmetry.

Now, let's stop specifying orientation, so that we won't distinguish RCRR from RRRC. Each tile with no rotational symmetry can be oriented in 4 distinct ways, so the 72 such oriented tiles correspond to 72/4=18 oriented tiles. (Rationale for division: when we first counted oriented tiles, we counted each unoriented tile 4 times, so we got 4 times the number we want.)

Tiles with 2-fold symmetry can each be oriented in 2 distinct ways: 6/2=3.
Tiles with 4-fold symmetry can only be oriented in 1 way: 3/1=3.
Altogether: 18+3+3=24, confirming Hypersmurf's count.

 

[blargney the second]

I just found a place the other day where you can play Carcassonne online.

 

[MerricB]

I use www.brettspielwelt.de

Cheers!

 

[meomwt]

I think there is a file on BoardGameGeek which lists all the tiles (and numbers thereof) for the main set and all the expansions.

I just don't have time to look for it right now.

 

[Doug Sundseth]

While I'd not thought of it before, this is similar to cis-trans isomerism problems in organic chemistry, but with roads, cities, and meadows instead of OH, CH3, and NH2 radicals.

This doesn't especially help to answer the OPs question, but I found it interesting, nonetheless.