Taking turns adding a number 1,2,3 to a 3x3 matrix without repeating numbers in the rows or columns: does the first player always win?

Question

Alice and Bob are playing a game on an initially empty 3x3 matrix. They take turns, and each turn:

• They add a number in {1,2,3} to an empty cell.
• They are not allowed to repeat a number in a row or a column (like a partial Latin square).
• The last person to move wins.

Alice goes first. A game might proceed as follows:

      A    B    A    B    A    B    A
...  1..  1..  1..  1..  1..  13.  13.
...  ...  ..3  ..3  ..3  .23  .23  .23
...  ...  ...  .1.  .12  .12  .12  312

In this example, Bob can't make a move, so Alice wins.

Question: Does Alice always win?

I'm just curious about this game because it relates to my research (partial Latin squares). I haven't actually sat down and written out a proof, but I believe there is a more intelligent answer than "I computed all possibilities".

Answer 1

Alice wins. Strategy:

1. Choose a diagonal
2. Place a number on the diagonal
3. Whenever Bob puts a number outside the diagonal, put the same number mirrored at the diagonal
4. If Bob puts a number on the diagonal, also put a number on the diagonal (this is possible because the row and column intersecting at the diagonal element Alice needs to fill have the same entries because of (3))

Answer 2

Without regard for strategy, considering cases:

If there is exactly one empty cell, the game is not over. I will say a cell "sees" another cell if they share a row or column. There are four cells that see the empty cell and four that don't. By the pigeonhole principle, two of the cells that don't see the empty cell contain the same number. Because these share neither a row or column, they see all four cells that see the empty cell, so those four cells don't contain this number. Thus, this number can be placed in the empty cell.

If there are exactly three empty cells, the game is not over. WLOG, the number of times $1$, $2$, and $3$ appear (respectively) can only be $(3, 3, 0)$, $(3, 2, 1)$, or $(2, 2, 2)$. In the case of $(3, 3, 0)$, $3$ can be placed in any of the empty cells. In the case of $(3, 2, 1)$, $1$ appears once in every row and once in every column. Thus, it appears twice in cells that see the cell with $3$: (once in the same row and once in the same column). So, there is an empty cell that doesn't see the cell with $3$ where another copy of $3$ can be placed. In the case of $(2, 2, 2)$, there is a unique cell that sees neither copy of $1$. Suppose, no move is possible. WLOG, $2$ occupies this cell. Then in the four cells that don't see this cell, there are two copies of $1$ and another copy of the $2$. If the fourth of these cells was empty, $2$ could be placed there, so it must be occupied by $3$. But, there are two other cells that could simultaneously contain additional copies of $3$. (This configuration is depicted below up to permutation of rows and columns and symmetry on the diagonal.) This is a contradiction, so some move must be possible.

12.
31.
..2

If there are between five and eight empty cells, the game is not over. Some number appears only once. There are four cells that don't see the cell with this number, and at most three are filled, so a second copy of that number can be placed in one of those cells.