# The Sudoku game: Solver-Spoiler variation

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.

• This is the variation I was considering when thinking about the symmetric strategy you proposed in another question. If the first player starts on an empty 4x4 board and the second player tries a symmetric strategy, the first player can spoil the solution by "breaking" a transversal. E.g. after both players play 1, then first player plays a three where a one would be expected. I imagine the Sudoku solution space is sparse enough that one can break any solution attempt. Gerhard "Goodness Knows I Have Frequently" Paseman, 2018.04.17. Apr 17, 2018 at 15:11
• Yes, I also expect the Spoiler to win on all the nontrivial finite boards. But can you make a general argument? We should not assume that the Solver is playing the symmetric strategy, since this is easy to defeat in this game variation. Apr 17, 2018 at 15:20
• A friend and I where playing a variation on this, and the problem seems to be that solver can spoil the spoilers attempts to create an invalid position. Therefore, the spoiler's strategy will need to involve spoiling multiple things at once. Apr 17, 2018 at 17:06
• Can you show (for kappa,lambda) that Solver has a win if played unopposed? Gerhard "Solution Space May Be Empty" Paseman, 2018.04.17. Apr 18, 2018 at 0:18
• Ah, now I can do it using a group $G\oplus H$, where $G$ has size $\lambda$ and $H$ has size $\kappa$. So all the asymmetric infinite boards in fact have solutions. Apr 18, 2018 at 18:21

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.

• I think you are assuming $n\geq 3$? Apr 23, 2018 at 14:15
• No, I am assuming $n \geq 2$. If $n=2$, Spoiler just has to play in the same row but different box than Solver to meet the above conditions. Apr 23, 2018 at 14:21
• But with $n=2$, what if Spoiler goes first and Solver plays in the same box? Then you can't have three empty squares in that box. Apr 23, 2018 at 14:25
• Ah, I was assuming that Solver goes first. If Spoiler goes first, I guess you need $n \geq 3$. Apr 23, 2018 at 14:27
• I think one might be able to argue that it must be to the advantage to go second, since all first moves are isomorphic. So going second is like getting two moves in a row at the start. Apr 23, 2018 at 14:30

I believe Spoiler has a win starting from an empty (or with 1 square filled) 4-by-4 board, and that is to take two moves to break a transversal. If only two ones are present, for example, there are (at most) four squares to accommodate the other two ones, and Spoiler will have two moves to play unchosen numbers in blocking spots. If a one and a two are present and the two is part of what would be a transversal for one, then play another one to attempt to have that two as a spoiling square. After two squares have been played, Spoiler should be able to achieve a win after Spoiler plays two more squares.

For an n by n board, I am not seeing a good defense (starting from an empty or almost empty board) against Spoiler trying to build a transversal which is spoiled by an earlier move (using a different glyph) of Solver. If Solver uses the same glyph, there are again four squares for Spoiler to control with two plays once most of the rest of the traversal has been played.

Gerhard "Success Is Transverse To Solving" Paseman, 2018.04.17.

# Note

I wrote this solution a week ago, but never got around to completing it. I am posting it as is because I think it adds some interesting points. Also note that the full dimension of the grid in my answer in $n$ by $n$ and not $n^2$ by $n^2$.

# Solution

Consider the following (partial) strategy for Spoiler in the $n\times n$ game (with any cover of $n$ blocks with size $n$): As long as no number appears at least $n-2$ times, fill a cell with the value filled most often in the grid. When possible, fill a cell in a block filled by Solver. A game can continue for at most $n-2$ turns, until Spoiler has to play when one of the values appears at least $n-2$ times. Due to symmetry, we can assume $1$ is the common value.

At this point, 1 appears in the grid $n-2$ times or $n-1$ times, depending on Solver's last move. In addition, at most $n-2$ cells are filled with other values. In particular, the pigeon-hole principle tells us that there is at least one value which does not appear in the grid at all, and one of the following holds:

Case 1: There are at least 3 values which do not appear in the grid.

Case 2: There are exactly 2 values which do not appear, at most one value appears twice, and the rest exactly once.

Case 3: There is 1 value which does not appear, and each other value appears exactly once.

In addition, depending on the set of cell blocks, there can be 0 or 1 or 2 candidate completions for the value 1. Finally, there is at most one value which is in a block with the candidate cells.

If there no candidate completions, Spoiler has already won. If there is a single available completion, Spoiler can win by spoiling it with the unused value.

Suppose there are 2 available completions. Consider the set of values which can be used to spoil a candidate completion. Solver can block a spoil in two ways.

a. placing a spoiling value by placing it in the same row/column.

b. placing the correct value in its intended target.

The first method, can only save one value. The second can only save one cell. Thus, if Spoiler can finish his turn while keeping two spoiling values over both cells of the remaining completion, he will win. This allows Spoiler to win in case 1, in case 2 if $n\ge 6$, and case 3 if $n\ge 5$.

# Small $n$

For $n=1$: Solver wins trivially.

For $n=2$: The second player wins by placing the appropriate value in the opposing diagonal.

For $n=3$: I think that with no blocks the first player wins and with (nontrivial) blocks Spoiler wins. I need to make an organized list to make sure I didn't miss any cases or moves.

For $n=4,n=5$: I didn't go through all the possibilities systematically, but it seems like Spoiler can win in all cases.

# Follow-up Questions

1. We see that Spoiler can win quickly in the sense that the board will eventually be blocked. How fast can Spoiler actually block the board?

2. How many values does Solver need to fill in order to prevent guarantee a win for all move sequences?

3. How many values does Solver need to fill in order to prevent guarantee a win with correct strategy?