Combination/Permutation Question: Unique Tsuro Tiles

General Questions
#1

Tusro is a board game that involves square tiles with two exits on each side, and paths connecting the exits. It’s easiest to explain with images:

How many possible unique tiles could you make for Tsuro, keeping in mind the following rules:

-Each exit to a tile needs to be connected to another exit.
-Any exit can be connected to any other exit, paths are perfectly allowed to cross, as you can see in the image.
-Tiles can be rotated freely.

The game comes with 35 tiles, so first I thought that might be it, but trying to solve the problem by drawing out every possibly tile in a systematic way gave me a far, far lower answer.

I’m not sure how to start with the math for this, as I was never any good at permutation / combination questions.

#2

First (probably wrong) attempt:

There are four paths per tile. Each path “consumes” two endpoints, so there are two fewer endpoints for the remaining ones. So the paths can be picked in:

[ul]
[li]Path 1: 87 = 56 ways[/li][li]Path 2: 65 = 30 ways[/li][li]Path 3: 43 = 12 ways[/li][li]Path 4: 21 = 2 ways[/li][/ul]

So this gives 8! = 40230 possibilities BUT:

A bunch of these possibilities look the same. In particular, since the paths are undirected, swapping the start and end of each path gives the same result. Since the ends of each path can be swapped independently, this reduces the result by a factor of 2^4 = 16.

Also since we can swap the order of the paths, that’s another 4! degeneracy there.

That reduces the number of possibilities down to 8!/(2^4 * 4!) = 105, but doesn’t yet take into account that a rotated version of a tile is still the same tile. I wonder why the result isn’t a multiple of 4 to account for that – probably because some configurations are symmetric under those transformations.

#3

There are 8 exits to the tile. Start from the first exit, and you have 7 choices of where to connect that one to. Then go clockwise around to the next unused exit: You have 5 choices for that one. Continue to the next unused exit, and you have 3 choices. Finally, you’re left with 1 choice for the last connection. So the naive total is 753*1.

Except that that’s probably an overestimate, since tiles can probably be rotated, and rotating a tile will give you another valid tile. So we would divide that number by 4.

Except that that can’t be right, since that’s not an integer. The problem is that sometimes when we rotate a tile, we get the same tile back again, not a different tile. So dividing by 4 is an underestimate.

So the answer is certainly something less than 105 and more than 27, and probably closer to the lower end. Which leads me to suspect that the 35 that come with the game is probably correct.

#4

I’ve finding it surprisingly hard to reason about the rotational degeneracy, but I count 5 tiles that are invariant under 90 degree rotations. Four that are invariant under 180 degree rotations (but not also 90 degree rotations).

The 105 would seem to count the first category once, the second category twice, and the remaining ones four times. So 105 = 5 + 2 *4 + 4 * 23, meaning the number of independent tiles is 5 + 4 + 23 = 32, which seems right-ish.

#5

A friend programmed up an answer, and claims the answer is in fact 35 .

#6

ignore this post

#7

If you use the right representation of the card, it’s easier to reason about rotational symmetry.

For example, one way to represent the card is as an 8-digit octal number, where each digit represents a path, and counts the number of spots away the endpoint of the path is. I will arbitrarily pick the left port on the top of the card as the first position and start with the least significant bits.

So the card where each incoming path goes right back out on the same side (each side has a little u-loop) is 71717171, and the card where every path goes directly across (looks like #), is 35353535.

It’s very easy to see that these cards are rotationally symmetric because they are the same when you take the two digits from the end, shift the rest of the number down, then put the two digits at the top (which is what you’d get if you rotated a card.

You can also easily tell whether a given number is a “valid” card by checking that the endpoints match. If they match, then for the each digit, you should be able to count that many spots in the number and the digit you end up at should be 8 - the number you started at.

I’m sure a math major could tell you something cool about the properties of the numbers here, but there are only 8^8 ~= 16 million numbers to check, so just code it.

It turns out that there are exactly 35 unique pieces:


13571357
13662257
13717157
14471447
14652437
14716427
15463247
15553337
15713717
16427147
16526327
16622717
17171717
22662266
22717166
24642464
24715463
25363265
25543364
25713662
26327165
26525363
26622662
33715553
35353535
35443544
35713571
36425543
42464246
43544354
43714652
44444444
44714471
53535353
71717171
#8

Yes, there are actually 10 tiles invariant under 180 degree rotations but not 90 degree rotations. Correcting leahcim’s methodology with this, we get the right answer: 35 tiles up to rotation.

#9

D’oh. That number did seem a bit low. :slight_smile: