A game from fault lines in domino tilings

game theorypolyominotiling

It is known that, for any tiling of a $6\times6$ rectangle with dominoes, there must exist a fault line, or a line cutting the square without cutting any domino. (There is a nice elementary proof of this fact, which I don't wish to spoil here.)

This suggests a two-player game. Two players alternate placing dominoes on the $6\times6$ board until it is full. If any player places a domino in such a way that the tiling cannot be completed, that move is considered to be illegal. Player 1 wins if the fault line is horizontal; player 2 wins if the fault line is vertical. (If there is both a horizontal and a vertical fault line, it's a tie.) Does either player have a winning strategy? Which one? What about a winning-or-tying strategy?

Best Answer

Player 1 has a winning-or-tying strategy. Their first move is as follows (A2 and B2 in chess notation):

enter image description here

Observe that if another horizontal domino is placed in the same row (in any of the three available positions), this will force the existence of a horizontal fault. So Player 1 needs only to cause one more horizontal domino to occur in that row; since Player 2 can't block all three possible followup moves without placing a horizontal domino themselves at (D2, E2), the only way for this to fail is if no such placement extends to a valid tiling.

That is, the only way that Player 2's first move can hope to lead to a win is if all possible extensions of it have vertical dominos on each of C2, D2, E2, and F2. But it's pretty easy to just check by exhaustion that no move has this property. So Player 2 can't win.

(My guess is that the game results in a tie, by e.g. Player 2 doing something very similar along a vertical line someplace far away from wherever Player 1's first move was, but I haven't investigated the game tree enough to prove this.)

Related Question