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.

  • 1
    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. – Gerhard Paseman Apr 17 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. – Joel David Hamkins Apr 17 at 15:20
  • 1
    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. – PyRulez Apr 17 at 17:06
  • 1
    Can you show (for kappa,lambda) that Solver has a win if played unopposed? Gerhard "Solution Space May Be Empty" Paseman, 2018.04.17. – Gerhard Paseman Apr 18 at 0:18
  • 1
    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. – Joel David Hamkins Apr 18 at 18:21

Here is a simple winning strategy for Spoiler on the $n^2 \times n^2$ board, with Solver going first, that requires at most $n^2$ moves to win. It can also 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 assume that Solver always plays a previously played number, or $i+1$, where $i$ is the maximum number played so far.

Spoiler now follows the following strategy. On turn $i$, Spoiler plays $i+1$ in $r_1$. 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. If Solver plays $n^2-1$ in $r_1$, then Spoiler spoils by playing $n^2$ in $c \setminus r_1$, where $c$ is the unique column with an unfilled cell of $r_1$. This is possible, since Solver has made at most $n^2-4$ moves outside of $r_1$ and Spoiler has never played in $c$.

Recall that by renaming, this implies Solver also does not play $n^2$ on her $(n^2-2)$-th move. 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 now play in $c$; otherwise, Spoiler can play $n^2$ in $c \setminus r_1$ on her next move.

But now Spoiler can spoil 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$? – Joel David Hamkins Apr 23 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. – Tony Huynh Apr 23 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. – Joel David Hamkins Apr 23 at 14:25
  • Ah, I was assuming that Solver goes first. If Spoiler goes first, I guess you need $n \geq 3$. – Tony Huynh Apr 23 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. – Joel David Hamkins Apr 23 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?

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.