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.

11more comments