FAQ 
Calendar 






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:
http://3.bp.blogspot.com/_XRdwidBnpw...suro+board.jpg http://serieborsen.se/images/ext...ire_all_35.jpg 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; 01062014 at 03:52 PM. 




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:
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. 




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. 




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 rightish. 






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





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 8digit 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 uloop) 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: Code:
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 Last edited by iamthewalrus(:3=; 01062014 at 07:51 PM. 




D'oh. That number did seem a bit low.
