How many unique race tracks in Flamme Rouge? A combinatorial study of a modular board game

When playing your favorite board game, having the option to set a different initial setup every time is a good way to keep things fresh.

In Flamme Rouge, a study of game variability, I examined all sorts of mechanism that games use to avoid blandly repeating themselves from one game to another.

However, I left you hanging with a crucial and very specific question about board game modularity, namely: How many unique races can be build from the tracks provided in the Flamme Rouge game ?

Today, we are going to find that out !

In case, you are not familiar with the game, and you would like to know more, you may want to start at the beginning with my actual review and rules explanation in:

Analyzing Flamme Rouge, a game of professional cycling

The total number of unique Flamme Rouge race tracks

In the box, Flamme Rouge provides 6 initial race plans for players to try out. But since you can arrange the tracks any way you want, this evidently only offers a limited sample.

Knowing that a racetrack is composed of all available pieces, and that the box contains 21 of them… double-sided,  it can make for quite a bit of possibilities! Finding an exact number however is not exactly a walk in the park…

The upper limit of combinations

Since part of my goal is to make this understandable for the greatest number, and allow for criticism of my approach, I’ll try to describe the full process.

So let’s start with defining an upper limit on how many race tracks we can build with the given game content.

Combinatorial track building

Considering only the shape of the pieces, we have the following:

• 1 x Start piece
• 1 x Finish piece
• 7 x Straight lines
• 6 x 45-degree turns
• 6 x 90-degrees turns

Assuming that we use all 21 pieces to build the track, how many unique track can be built ?

The start and finish pieces will always be at the same place. This mean we can ignore those in our initial count. For the rest, if we build the race one piece at a time, starting after the starting line, we have the choice of:

19 pieces for the 1st segment.

18 remaining pieces for the second

17 remaining pieces for the third.

16 for the fourth

And so forth….

So in total we have 19 x 18 x 17 x 16 x 15 x … all the way down to one.

A simple factorial usually noted as: 19!

This gives us:

121 645 100 408 832 000 different ordering!

122 Quadrillions !!!

If you were to play one game every second, this would take 3.59 billions years!

But this is not the whole story.

Since all the 21 track pieces are reversible, one side being flat racing ground, and the other usually having some form of upward or downward slope, we need to count 2 possibilities for each track pieces, or rather all the possible combination of choosing side-A or side-B for each piece.

For a fixed 3 pieces ordering, by just selecting side A, or side B you have choices for a total of 8 different tracks. For example:

AAA-AAB-ABA-BAA-ABB-BAB-BBA-BBB

Which mean that for each of the previous 19! ways of ordering the pieces, we have ways of actually setting them. And i say 21 because the starting and finish pieces can also be flipped, so we need to include them this time.

This leaves us with ways of setting the race track.

121645100408832000 * 2097152 = 255 108 265 612 582 846 464 000

Or roughly

combinations.

This however is only an upper limit…

• First because, some pieces looks the same, at least on one of their side.
• Second, because the track is not a straight line, there are some ways to set the pieces that would end up crossing each other, and create tracks that are impossible to build on a flat surface!

So while this number is astronomical, it does not represent the real amount of possible ways of setting the track. And since I do not shy away from a challenge, I decided to get a better approximation of the real number of tracks we can build.

A small note about racetrack shape: While the most important aspect of a race track is its elevation profile (where the up and own slopes are), having different race track shape is also interesting because when you play, it feels different. Also, I will come back to elevation profile in a moment.

So let’s have a look at how we can improve our estimate on the number of track shape!

Counting the number of possible shapes

From a track shape perspective, we do not really have to consider 19 individual pieces, but only have to consider three types of pieces:

• Straight lines
• 45-degree turns
• 90-degrees turn.

And to simplify thing even more, only the 45-degrees and 90-degrees pieces will change the overall track shape when flipped. A flipped straight line, is still a straight line after all.

This two simplification drastically reduce the number of possible unique track shapes that can be built!

To calculate our new number of meaningful ordering, we take the original count, and divide it by the count of interchangeable ways we can order the identical pieces without affecting its shape.

So the ordering count becomes:

And for the flipping portion of the problem, we now have only 12 turning pieces that can be flipped to change the track shape. Which is instead of .

So it gives us:

46558512 x 4096 = 190,703,665,152

You do not need to be a wizard to see that 190 billions is a much more manageable number than 255 108 265 612 582 846 464 000 !

Approximately 1 000 000 000 000 times more manageable… We still don’t know how many of those shapes are non-intersecting and thus playable, but this is a good start!

Computable horizon

At this scale, would the modern wonder of computers makes it possible to visit each individual racetrack and check if it offers a valid non-intersecting shape? It certainly does!

So why not write a simple program that will visit each of those shapes?

Warning: Checking if a track self-intersect is not as simple as it may seem.

1. First because you have to try to represent the track as a series of lines, close to the real thing. And check if they intersect.
2. The real pieces have some slack, so you end up with tracks that would be slightly overlapping in theory, but that are perfectly playable in reality.

So I made an executive decision. I simplified a bit the track representation to make it easy to compute. Using points along the turn pieces exterior instead of curves, and I decided to ignore the slack issue, only evaluating a track as valid if it would not be intersecting using rigid pieces.

Since I’m a half a perfectionist, I worked really hard to make it an honest representation of the real thing, but the exact number of correct track may vary by a few millions, depending on what you accept or not as overlapping.

Far from perfect, but likely the closest you’ll ever get to real answer to this unlikely question…

How many valid track shapes

Now that we have a tractable number of possible track shape, (about 190 billions), how many of them are non-intersecting ?

For the curious, here are some optimizations I made to reduce a bit the number of actual number of track examined:

• I only examined track where the first turn is a left turn. I assumed here that all those track have a mirror equivalent track where the first turn is to the right, and I double counted them. I only did this for the first turn, because for subsequent turns it gets too complicated to determine if the mirror image of the remaining track would intersect with previously laid tracks without actually checking. This divide the actual count to check by about half.
• I built the track exploration in a depth-first search pattern, killing a branch of my search tree as soon as I encountered an invalid track crossing, thus limiting the total number of final track to consider.

For the curious, here what a depth-first search looks like in our case (You can see that we go as far as we can, then backtrack as little as possible to explore the whole in ordered manner).

I’ll save you the details about the actual implementation, and visualization that took me quite a bit longer than I expected, but, I finally made it and…

The actual number of unique valid track shape is:

86 728 760 224

or approximately 45.48% of the 190 billions track tested!

Just to be clear, this number is manageable, but it still took my computer almost 3 days to complete the computation, so not that trivial a task either!

What about track permutations ?

When playing Flamme Rouge, the only concern for a competitive player is  the race track elevation profile, the upward and downward slopes that offer the most strategic plays.

Here is a crude way of representing the elevation profile of a race track:

My representation is a bit simplistic for the moment, but since I’m not providing info graphic for anyone beside our own entertainment, it will have to do. However, doing a quick search I found this fun article showing that I’m not doing that bad of a job: how bad elevation profiles abound in the cyclist world.

So, forgetting the race shape and it’s validity for a moment, I decided to see how many unique elevation profiles we can get for a fixed ordering of the track pieces. This is a bit of a detour, but this gave me enough understanding of the problem to allow me to really answer the big question of how many unique races are possible. So bear with me!

How many unique elevation profiles can be obtained from a fixed track ordering?

Flamme Rouge track pieces all have a letter assigned to them. One side is a lowercase, and the other side is uppercase, allowing race tracks to be identified by a single string such as:

AebQRNHPcgikDFsLojmtu

Or as presented in the game itself:

So let’s say we take a particular ordering of the track pieces. Keeping all the letters in the same order, but allowing flipping side, between lower and uppercase. How many elevation profile can we obtain this way? (Forgetting track overlapping and validity for the moment).

There is 21 track pieces in total, each track pieces having two sides. If we allow all combinations of on which side we put them, it gives us unique combinations.

2 097 152 potentially different profiles.

But since several pieces have the same elevation profile on both of their side, this is, once again, only an upper limit…

To be sure, I decided to write a little program to really know how many unique elevation profiles can be obtained by simply flipping pieces, while keeping the pieces ordering fixed.

Since images speak more than words, have a look:

What I learned here surprised me a bit !

For a given ordering, of the 2 097 152 possible combinations, I obtained the following number of unique profile:

131 072

And more surprising, this was the exact same number, no matter what the track pieces ordering I looked at. For each of them, I found 16 repetitions of each possible elevation profile. (And 16 * 131 072 =  2 097 152, the math checks out!).

Once the initial surprise passed, I realized the reason for this was simple, 4 of the pieces have the same (flat) elevation profile on both side, so for (16) combinations, the elevation profile will be the same with these pieces on one side, or the other!

Only the pieces that have differentiable sides will affect the overall elevation profile when turned over!!!

Elevation profile repetition between orderings

In order to see if we would see repeating elevation profile between different pieces ordering, I decided to generate random tracks, and check if I found any.

Once you remove the 16 completely flat profile available for all the pieces ordering, is there overlap? The answer is… not many!

When you look at the non-flat side of pieces, not many pieces can be interchanged to get the same elevation. There is three straight pieces that offer an elevation profile that can be replaced by 3 turn pieces of length 2, if put in the correct order.

Some turn pieces can be interchanged, because they have the same non-flat profile of 2-down or 2-up.

But aside from those cases, only the orderings which have a piece at the exact same place will produce tracks with equivalent profiles, and only when mostly all of their other track pieces are on the side showing flat ground.

Testing 1000s of randomly generated ordering for repetition among all their permutations offered at most a few hundreds similar elevation profile when adding a new race.

I’ll be sorry to disappoint, but I did not reach a final conclusion on how unique elevation profile there was in total. Maybe I’ll revisit one day, but for the moment, I refused to be side-tracked!

However, doing all this gave me a good enough understanding of the problem to provide a final answer to our original question:

How many unique races can we get if we consider shape AND elevation profile?

Converging toward a complete solution

Playing with track flipping, trying to reconcile them with the validity of non-crossing shape, I realized the following:

If you take a fixed valid track shape, you can rearrange and flip pieces sides without changing the shape. And if you can calculate unique elevation profile per unique shape, you would end up with the sum of unique races!

Some races in that count will have the same shape. Some races in that count will have the same elevation profile. But no two race track in those will have both the same shape and the same profile, giving us the real count of unique races!

So let’s calculate how many possible permutation and flipping is possible for each fixed and valid track shape…

Counting elevation profile for fixed race tracks

For this, we can consider each type of track pieces independently, and multiply them together to get our final number.

Starting and finishing pieces

We have one starting piece and one finishing piece. Their place is fixed, but they can be both flipped and show different profile. For a total of 2 times 2 different positions. So:

4

Straigth track pieces

Note: This paragraph was edited since I realized years later, after making a small presentation about my bloh, that I made a mistake in my approach. Always humbling to find those!

For the 7 straight pieces, they all have a one side of flat ground, and the other side with different elevation changes. So we can reorder them in 7! different ways, without changing the track shape. Each can be flipped as desired as well, which would provide a count of for the elevation profiles.

However, flat-sided track are interchangeable. So we need a way to account for this.

Since all elevation changing sides are unique, we need to find all the ways we can select group of betwen 0 and 7 tracks that will show their elevation side, and for each of those group, determine how many ways they can be ordered.

How many ways to find a group of N tracks in a group is called: n-choose-k

And for each number of selected cards, which will show an elevation profile, others showing an identical flat side, we will determine how many different profile can be made.

Which is simply: 7! / (number of flat side piece)!

Profile side count	Ways of selecting	Ways of ordering
0	1	1
1	7	7
2	21	42
3	35	210
4	35	840
5	21	2520
6	7	5040
7	1	5040

So we only have to multiply the two last column, and add their number to arrive at the final count:

130 922

45 degree turn pieces

For the 45-degree pieces, things get interesting. Since we are at the moment only considering a fixed race track shape, there is no real choice of which side the turn pieces are set.  The permutation of the pieces in the track implicitly determine on which side they end up. So we only have to consider at most 6! (or 720) different elevation profiles…

However, because there is always a complication, there are 2 pieces with flat ground on both side, and a couple with identical elevation profile on their second side. And because the flat side is sometime on the 45-turn as a right turn, and sometimes as a left turn, the actual count of elevation profile depends on how many right turns and left turns there are in the shape !

As in everything mildly complicated, a quick program will solve that for us.

So instead of 6! which would give us 720 unique elevation profiles, we end up, depending on the direction of the turns, with the following counts for the different combination of the 6 turns:

Nmb of Turns	Unique Elevation Profile Count
0 right, 6 left turns	30
1 right, 5 left turns	50
2 right, 4 left turns	73
3 right, 3 left turns	82
4 right, 2 left turns	63
5 right, 1 left turns	35
6 right, 0 left turns	15

So between 15 and 82 different elevation profile, which is surprinsingly far less than the possible 720…

90 degree turn pieces

For the 90 degrees turns… in a mind bending twist, which this time is in our favor, they turn out to have the exact elevation profiles distribution than the 45-degrees turns.

So we don’t have to repeat this, and can simply re-use the same numbers from the last table!

Let’s put it all together

So we end up with calculating the total number of possible unique elevation profile for a fixed shape as:

4 different ways to put the starting and end piece.

640 081 ways to put the straight pieces.

Between 15 and 82 ways to put the 45 degrees turns.

And again between 15 and 82 ways to put the 90 degrees turn.

So between

4 * 130 922 * 15 * 15 = 117 829 800

And

4 * 130 922 * 82 * 82 = 3 521 278 112

Limits that we must not forget to multiply each by 86 728 760 224, the total number of unique shape we found earlier…

But Wait !!!

If I just re-ran my exploration program, I would be able to know exactly how many valid shapes there are for each of the possible combination count for the 90 degrees and 45 degrees turns, and thus calculate the exact number of possible racetracks, without those pesky limits approximation!

The following table contains the counts of valid racetrack, for each possible combination of 45 and 90 degrees turns.

To be clear the column titled 1 – 90 means One 90-degree left turn in the track (And therefore five 90 degrees right turns). And the row are similarly labeled, indicating how many left 45-degrees turns.

	0 – 90	1 – 90	2 – 90	3 – 90	4 – 90	5 – 90	6 – 90
0  45	14	343915	34208405	299601532	462307847	181470428	14705451
1  45	24808	19367217	643397651	2869340579	2950399964	852054383	44027145
2  45	1071116	209749466	3285054438	9024372573	6747526090	1313502684	36719935
3  45	11826371	857306838	7044612087	12922778350	7044612087	857306838	11826371
4  45	36719935	1313502684	6747526090	9024372573	3285054438	209749466	1071116
5  45	44027145	852054383	2950399964	2869340579	643397651	19367217	24808
6  45	14705451	181470428	462307847	299601532	34208405	343915	14

Note that because all tracks have a corresponding mirror image track, the table itself is mirrored.

Not surprisingly, we can see that tracks with all their turns being left (or right) are quite rarer than more balanced track!

Here is a few examples:

Finally, to make good use of the above table, I built a similar table, using the results of the previous section, this time showing the 45-degrees and 90-degrees unique elevation profiles counts.

Remember that the 45 and 90 degrees turn offered the same unique elevation profile counts. So once again the table is mirrored, but in the opposite direction.

Here is the table showing the unique elevation profile count for different amount of left turns:

	0 – 90	1 – 90	2 – 90	3 – 90	4 – 90	5 – 90	6 – 90
0 – 45	225	525	945	1230	1095	750	450
1 – 45	525	1225	2205	2870	2555	1750	1050
2 – 45	945	2205	3969	5166	4599	3150	1890
3 – 45	1230	2870	5166	6724	5986	4100	2460
4 – 45	1095	2555	4599	5986	5329	3650	2190
5 – 45	750	1750	3150	4100	3650	2500	1500
6 – 45	450	1050	1890	2460	2190	1500	900

So all we have to do is to multiply the two tables together, element wise (Each cell multiplying the corresponding cell of the other table), to obtain the number of variation obtained through flipping the pieces for each fixed track shape, and sum all the values together. Giving us:

420 221 311 798 054

All that is missing is to multiply by the number of straight track recombination (130 922), and the number of start and end pieces combinations (4).

For a grand total of:

220 064 858 332 899 303 152

0r 2.20 * 10 exp 20

Unique valid race tracks to play.

Voila!

Conclusion

As I mentioned earlier, this is still an evaluation since there is some uncertainty when validating a race track shape. And I reserve the right to update the numbers if I find some errors. But I stand by the methodology! Feel free to try to come up to a more precise number!

One legitimate question you may ask is the following:

What was the point of doing this?

Well, there are two ways of looking at this…

First, there is the idea that since this has no practical use, this is useless. I would counter that solving a problem is interesting by itself. It forces you to consider things you would normally brush aside. As such, I’m often annoyed when learning something, and only being shown only the simplest and easiest cases.

Once you try to solve a real life situation with a bit more complexity, you are on your own. You almost always encounter issues and limitations that were not mentioned, and limit greatly the possible applications.

Second, while doing this I also got plenty of time to think about the problem, I personally learned things doing this, about all kind of stuff. I cannot count the times when a difficult problem arose in my professional programmer life, and where I ended up having a serious head start because the new problem had some aspects resembling earlier problems I solved.

I also had plenty of interesting ideas along the way!

What I did not tell you is that, while doing this, I decided to re-run my program, but this time, saving some additional information about the tracks generated.

Inevitably, this led to me working on a new post about interesting tracks, and practical track shapes to use when playing in a space challenged environment!

In the meantime,  have fun and let me know if you learned anything useful, if you enjoyed some parts more than others, or if you think I missed anything!