More Tsuro Combinatorics

I keep coming back to the game Tsuro, which I've mentioned in this blog several times.

Let me describe the rules quickly. The game consists of a 6 x 6 grid of empty squares. The border of this grid has two white lines leading in to each side of a square (12 per side, so 48 lines total along the border). Players begin by putting their marker on one of these lines.

There are 35 tiles in the set, of the size of the empty squares on the board. Each side of each tile has two path ends that line up to the two white lines on the border (see the picture at the end for an example of some tiles). Each tile has four path pieces, each with two ends at different places on the boundary of the tile. These paths can cross, and there is a tile for each combination of paths (more on this later). Players keep hands of three tiles, drawing a new one every time they play one.

Each turn, the current player chooses a tile from their hand and lays it on the board in front of their marker. This new tile continues the path their piece was on, and they move their piece to follow that path until its end (it may link to other already-played tiles, so it could go longer than just one tile). The player also moves any other pieces that had their paths extended by this tile, again as far as they can until they reach their path's end.

For all those pieces that moved, if the path either leads them off the board or collides with another marker, then they have lost and are out of the game. The winner is the last one standing (or tie if multiple people lose on the last turn). Since there are only 35 tiles and 36 squares, it is possible all tiles can be played without anyone losing. In fact, the game comes with enough markers for 8 players. Can they all complete the game? Can they all complete it if they all have access to all tiles from the beginning (instead of having separate hands)?

While showing Tsuro to my aide this week, we raised this question. Ernie quickly became interested in trying out the combinations to see if he could get a working solution. This is an excellent challenge; I would guess the problem is NP-complete for general sets of tiles.

The question also came up of whether there are only 35 possible tiles, or whether the game is missing some possible combinations. I'm terrible at counting, but Ernie had some good insight and we worked it out. Here's a sketch of our logic:

Consider a single tile and count the possible configurations of paths in that tile. Choose one of the incoming path locations. There are 7 places that path could connect to. Now go clockwise around the tile to the next not-yet-connected path end. From here there are now 5 possible places this could connect to. After that, there are 3 more for the last one. In total that gives us 105 possible total configurations.

The game doesn't have this many, so there must be some symmetry that is not being considered. Since 35 = 105 / 3, it seems likely that rotational symmetric positions are not being used (which is the case). Now can we find cases where other symmetry is used? Yup!


Each right piece is symmetric with the corresponding left piece! I think the game uses all pieces. It's excellent that this works out to exactly 35 pieces, leaving that extra final open square. Very elegant!