A Transversal Achievement Game on a Grid

Question

Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid. The first player (if any) to occupy some transversal (i.e., a set of n cells having no two cells in the same row or column) is the winner. What is the outcome of the game given best possible play by both players?

Answer 1

Every game like this, in which moving is always an advantage and the winning conditions are symmetric, is won or drawn by the first player. See strategy-stealing argument. In this case, although it is possible to get a draw (one player fills up one column and the other player fills up another column, for instance), it looks difficult enough to do so that I suspect the result is a first player win. Of course, this is not the same as finding an explicit winning strategy.

Answer 2

Unless my code is wrong (always a real possibility) the 4x4 case is a first player win.

Vincent Vatter suggested looking at the related game where X wins by building a permutation, and O wins otherwise (i.e. by blocking a permutation). Note that in this game, O does not win simply by forming a permutation, but only by blocking X from doing so.

The reason for looking at this game is that it's relatively easy to see that if X wins the modified game, both as first and second player in some size $k$, then she also does so in size $k+1$. The hope would then be to show that the outcomes of the two games are related somehow.

Answer 3

As Michael Albert mentioned, an interesting variant is when X wins by building a permutation, while O wins only by preventing X from building a permutation. (The standard term for such a game is maker-breaker.)

According to my coding (which should not be regarded as infallible), X wins this game on a $4\times 4$ grid both when X goes first and when O goes first. By a straight-forward inductive argument, this implies that X wins the maker-breaker game on an $n\times n$ grid for all $n\ge 4$.

The question remains of whether this has anything to do with the version of the game posed by Martin, where both X and O are trying to build permutations.

Answer 4

Unless I am missing something, the game will always end in a loss for both players. In the case n=2, the second player plays on the same diagonal as the first player. For larger n, the penultimate move of player 2 is to block the unique winning move determined by player 1's first (n-1) moves. Player 1's last move would then be to block player 2's winning move, if one exists.

This is based on my reading of the rules, which tells me that every configuration of n+1 marks of one player loses, that marks are not overwritten or replaced once made, and that each players places only one mark during their turn.

Gerhard "Ask Me About System Design" Paseman, 2010.06.26

Answer 5

This question can be phrased in terms of (0,1)-matrix permanents. Player 1 places copies of the number 1 and player 2 places copies of the number 0, and empty cells count as 0. Player 1 wants to achieve a non-zero permanent.

Permuting the rows and columns, or taking the matrix transpose gives an equivalent game.

EDIT: I was actually quite surprised at how easy it is for the o's to make a losing mistake! Consider the position on the left in the diagram below (after 4 o's have been placed and 3 x's have been placed, with x to move). An equivalent position seems like a very natural position to arise. Surprisingly, x can force the win from here! I put in yellow the forced moves by o (otherwise x goes in that square and o loses).

Consequently, o has made a mistake in allowing the first position above, and can win instead as illustrated in the following sketch, for example.