Thread Tools
Old 01-06-2014, 03:49 PM
Join Date: Apr 2009
Posts: 525
Combination/Permutation Question: Unique Tsuro Tiles

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.

Last edited by Karrius; 01-06-2014 at 03:52 PM.
Old 01-06-2014, 04:21 PM
Join Date: Dec 2010
Location: Boulder, CO
Posts: 3,484
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:
  • Path 1: 8*7 = 56 ways
  • Path 2: 6*5 = 30 ways
  • Path 3: 4*3 = 12 ways
  • Path 4: 2*1 = 2 ways

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.
Old 01-06-2014, 04:25 PM
Charter Member
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 73,606
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 7*5*3*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.
Old 01-06-2014, 06:36 PM
Join Date: Dec 2010
Location: Boulder, CO
Posts: 3,484
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.
Old 01-06-2014, 07:42 PM
Join Date: Apr 2009
Posts: 525
A friend programmed up an answer, and claims the answer is in fact 35 .
Old 01-06-2014, 07:49 PM
Join Date: Apr 2007
Posts: 10,520
*ignore this post*

Last edited by Indistinguishable; 01-06-2014 at 07:54 PM.
Old 01-06-2014, 07:50 PM
Join Date: Jul 2000
Location: Santa Barbara, CA
Posts: 10,652
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:


Last edited by iamthewalrus(:3=; 01-06-2014 at 07:51 PM.
Old 01-06-2014, 07:56 PM
Join Date: Apr 2007
Posts: 10,520
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.
Old 01-07-2014, 08:27 AM
Join Date: Dec 2010
Location: Boulder, CO
Posts: 3,484
Originally Posted by Indistinguishable View Post
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.
D'oh. That number did seem a bit low.
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

All times are GMT -5. The time now is 06:35 PM.

Copyright © 2017
Best Topics: cartman's mom porn swallowing live mouse flies water potatoes and milk value pak coupon removable adhesive tnt detonator dead reckoning chalk line body open ct scan cuchulain pronounced poontang definition barney name zyrtec walmart brand titrating oxygen affected accent car crash song mad scientist woman headstone engraving cost medium distance relationships malta goya review left justified mlna usps diarrhea song lyrics loni young popping car is safe zipcar or rental ear clicking balding buzzcut pooping euphemisms giving self head definition of goomba popcorn farts o vs 0 on license plate california get scratches out of eyeglasses black dragon chrono cross toyota prius reliability long term does zantac help with gas does drano unclog toilets create your own civilization game maui jim sunglasses sale ebay whos who of american high school students where does let's blow this popsicle stand come from how much does it cost to retune a piano after brushing teeth white film in mouth a tale of two sisters explained 20 foot tall swing set can a helicopter do a barrel roll how to make suicide look like a heart attack italicize font in illustrator wells fargo atm 10 dollar bills whale in japanese language should i play fallout 1 why mount a horse on the left finger circle punch game ethiopian people physical features the greatest swordsman who ever lived does pepper go bad what does printer in error state mean does a fielder's choice count as a hit rubber strips home depot can you take tylenol and advil together for pain where does a series of unfortunate events take place tylenol extra strength vs regular do dentists prescribe painkillers for root canals what does uf stand for in capacitors jesus saying i love you