The Sudoku game: Solver-Spoiler variation

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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?