Reply
Thread Tools Display Modes
#1
Old 01-06-2014, 03:49 PM
Guest
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:

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; 01-06-2014 at 03:52 PM.
#2
Old 01-06-2014, 04:21 PM
Member
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.
#3
Old 01-06-2014, 04:25 PM
Charter Member
Moderator
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 73,145
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.
#4
Old 01-06-2014, 06:36 PM
Member
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.
#5
Old 01-06-2014, 07:42 PM
Guest
Join Date: Apr 2009
Posts: 525
A friend programmed up an answer, and claims the answer is in fact 35 .
#6
Old 01-06-2014, 07:49 PM
Guest
Join Date: Apr 2007
Posts: 10,519
*ignore this post*

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

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=; 01-06-2014 at 07:51 PM.
#8
Old 01-06-2014, 07:56 PM
Guest
Join Date: Apr 2007
Posts: 10,519
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
Old 01-07-2014, 08:27 AM
Member
Join Date: Dec 2010
Location: Boulder, CO
Posts: 3,484
Quote:
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.
Reply

Thread Tools
Display Modes

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 09:42 PM.

Copyright © 2017
Best Topics: milkshake song meaning lobster claw strength density of neutronium cat sprained leg drano for toilet polythene paint minivan nicknames prison coveralls whopper sandwich invert sugar syrup latuda recreational use lentil seasoning jinx origin pub trivia categories sub dividing penguin pushing amtrak coach seating crow permit disc scrubber boa safe pass interrogation lamp truffle flavor fallout 3 exploits roadie songs melting a penny ultimate magus 3.5 mexico massage parlor cherries blossom cheddar cheese pizza zzzquil ingredients alcohol match success befront definition borax boric acid when can i eat cereal after wisdom teeth center cut bacon vs regular bacon broad shoulders vs narrow shoulders men keyboard for roku tv how long to recover from donating blood by the same token definition 16 feet is how many inches do eardrums grow back mazda 3 key fob programming chinese food camels hump toyota brake service price why is spook racist ultra light cigarettes brands does water work when power is out leg numbness when standing does your signature have to be your full name how to fix a paper jam in hp printer 14 year old thongs who owns mr pibb girls are like apples yellow grids on telephone pole how to eat a giant jawbreaker pontiac vibe vs matrix will a magnet stick to aluminum what does a slow clap mean steam booster packs? how do barking collars work how to remove smoke smell from books white chocolate nestle crunch bar what wood is good for carving can you use ak cup twice how much time is a jiffy