Complexity of Tsuro

Another of the games I got to play (and immediately bought) at GenCon was Tsuro. I had seen this game in the store before, but had bought Oshi instead, which is a great game itself. Tsuro, however, has the nice bonus feature that it easily scales from 2 players up to at most 8. The game is played by having each player follow a different string through a grid from the border. Players take turns placing tiles on the board which determine the directions of the strings. Your goal is to avoid having your string either head off the board or collide with another string.

Tsuro, happily, is the sort of game that doesn't seem to take much to generalize. There is a bit of randomness and hidden information, so a CGT redefining of the game would require some adjustment (players in the game choose from a small handful of tiles each turn, which are secret from the other players) but not a terrible amount.

Without doing any sort of analysis (or any research yet at all on this) it already seems like determining whether a winning strategy for this game exists is PSPACE-complete. Here's a little bit of my consideration for this:

1) It's definitely in PSPACE; once you place a tile on the grid, you cannot place another in that spot. Since a general description of the game requires describing the locations of any previously-placed tiles, there will be at most that many more moves, so a brute force algorithm can just use the game board to try all possible results.

2) We can rephrase it as a one-player puzzle, which seems a good candidate for an NP-complete problem: arrange all tiles on the board with one space missing so that all strings neither collide nor lead out of the board.

3) With the path-following nature of the game and the goal of remaining within the structure, some facet of this game may be equivalent to some fixed-point theorem, such as is true with Hex, a well-known PSPACE-complete game.

These are just my thoughts. Does anyone know anything certain about this game?

-Kyle

(Although I posted yesterday, I will likely not post on Sundays!)