Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt to trap each other in a position that cannot be extended without explicitly violating the Sudoku condition.
In this game variation, we have two players, the Solver and the Spoiler, who place numbers on a Sudoku board, obeying the rule that they must never explicitly violate the Sudoku condition: that is, the numbers must never occur twice in any row, column or sub-board square.
The Solver aims to build a global Sudoku solution on the board, and the Spoiler aims to prevent this.
Question. Who wins the Sudoku Solver-Spoiler game? What is the winning strategy? Does it matter who goes first?
Of course, the Solver wins the trivial $1^2\times 1^2$ board. And in my recent blog post, Infinite Sudoku and the Sudoku game, I considered the Solver-Spoiler game on the infinite Sudoku boards $\kappa^2\times\kappa^2$ and proved that the Solver can always win in the infinite case, even when the Spoiler is allowed to go first and to make many moves at once on every turn.
On (nontrivial) finite boards, however, the advantage seems to lie with the Spoiler, since in practice it seems easy to spoil a solution on such a board. Can someone describe an explicit winning strategy for the Spoiler? It seems that one will want to almost-but-not-quite complete a row, for example, and then play the missing number in the corresponding column or subsquare to spoil the solution. But things get complicated if there are two missing squares in the almost-completed row, and I haven't managed to push the argument through.
If indeed the Spoiler has a winning strategy on the $n^2\times n^2$ board, for $n\geq 2$, how quickly can she win?
Update. It has come to my attention that people sometimes consider asymmetric Sudoku boards, of size $(nm)\times(mn)$, an $m\times n$ array of rectangular sub-boards of size $n\times m$. I wanted to mention that the argument on my blog does not work in the infinite asymmetric case $(\kappa\times\lambda)\times(\lambda\times\kappa)$, since as Christopher King pointed out, with only $\lambda$ many moves in suitable rectangles, one can rule out a particular symbol for a given row, and so it is no longer true that every position of size less than the number of labels can be extended to a full solution.
Question. Who wins the infinite asymmetric Sudoku Solver-Spoiler game?
It seems likely to me that if $\lambda<\kappa$ and $\kappa$ is infinite, then the Spoiler can win the $(\kappa\times\lambda)\times(\lambda\times\kappa)$ game.
Best Answer
For all $n \geq 2$, here is a simple winning strategy for Spoiler on the $n^2 \times n^2$ board, that requires at most $n^2-1$ moves to win. I assume that Solver plays first, but the strategy can easily be adapted if Spoiler goes first.
By symmetry, we may assume that Solver first plays a $1$ in the first row, $r_1$. By renaming numbers, we may also assume that Solver always plays a previously played number, or $i+1$, where $i$ is the maximum number played so far.
Spoiler follows the following strategy. For each $i \in [n^2-3]$, Spoiler attempts to play $i+1$ in $r_1$ on her $i$th turn. If $i+1$ has already been played in $r_1$, then Spoiler plays in the set of columns containing a filled entry of $r_1$ (with the smallest number possible).
Observe that after $n^2-3$ moves, neither player has played $n^2$ nor $n^2-1$, and these are the only entries missing from $r_1$.
We claim that Solver cannot play in $r_1$ on her $(n^2-2)$-th move. Suppose not. Recall that by renaming, this implies that Solver plays $n^2-1$ in $r_1$. Therefore, Spoiler spoils by playing $n^2$ in $c \setminus r_1$, where $c$ is the unique column with an unfilled cell of $r_1$.
Thus, after Solver's $(n^2-2)$-th move, $n^2$ and $n^2-1$ still have not been played in $r_1$. Spoiler now plays $n^2-1$ in $c \setminus r_1$, where $c$ is a column containing an unfilled cell of $r_1$. Note that after this move, there is still an unfilled cell in $c \setminus r_1$, since Solver has made at most $n^2-3$ moves outside of $r_1$ and Spoiler had previously never played in $c$.
Therefore, Solver must play in $c$ on her $(n^2-1)$-th move; otherwise, Spoiler can play $n^2$ in $c \setminus r_1$ on her next move. But now Spoiler can spoil on her $(n^2-1)$-th move by playing $n^2-1$ in $c' \setminus r_1$, where $c'$ is the other column containing an unfilled cell of $r_1$.
This is joint work with Tillmann Miltzow.