Consider what I call the Sudoku game, recently introduced in the MathOverflow question Who wins two-player Sudoku? posted by Christopher King (user PyRulez). Two players take turns placing numbers on a Sudoku board, obeying the rule that they must never explicitly violate the Sudoku condition: the numbers on any row, column or sub-board square must never repeat. The first player who cannot continue legal play loses. Who wins the game? What is the winning strategy?
The game is not about building a global Sudoku solution, since a move can be legal in this game even when it is not part of any global Sudoku solution, provided only that it doesn’t yet explicitly violate the Sudoku condition. Rather, the Sudoku game is about trying to trap your opponent in a maximal such position, a position which does not yet explicitly violate the Sudoku condition but which cannot be further extended.
In my answer to the question on MathOverflow, I followed an idea suggested to me by my daughter Hypatia, namely that on even-sized boards
This argument works on even-sized boards precisely because the reflection of every row, column and sub-board square is a totally different row, column and sub-board square, and so any new violation of the Sudoku conditions would reflect to a violation that was already there. The mirror strategy definitely does not work on the odd-sized boards, including the main
After posting that answer, Orson Peters (user orlp) pointed out that one can modify it to form a winning strategy for the first player on odd-sized boards, including the main
This idea is fully general for odd-sized Sudoku boards
Conclusion.
- On even-sized Sudoku boards, the second player wins the Sudoku game by the mirror copying strategy.
- On odd-sized Sudoku boards, the first players wins the Sudoku game by the complement-mirror copying strategy.
Note that on the even boards, the second player could also play complement mirror copying just as successfully.
What I really want to tell you about, however, is the infinite Sudoku game (following a suggestion of Sam Hopkins). Suppose that we try to play the Sudoku game on a board whose subboard squares are
One thing to notice is that on an infinite board, it is no longer possible to get trapped at a finite stage of play, since every finite position can be extended simply by playing a totally new label from the set of labels; such a move would never lead to a new violation of the explicit Sudoku condition.
For this reason, I should like to introduce the Sudoku Solver-Spoiler game variation as follows. There are two players: the Sudoku Solver and the Sudoku Spoiler. The Solver is trying to build a global Sudoku solution on the board, while the Spoiler is trying to prevent this. Both players must obey the Sudoku condition that labels are never to be explicitly repeated in any row, column or sub-board square. On an infinite board, the game proceeds transfinitely, until the board is filled or there are no legal moves. The Solver wins a play of the game, if she successfully builds a global Sudoku solution, which means not only that every location has a label and there are no repetitions in any row, column or sub-board square, but also that every label in fact appears in every row, column and sub-board square. That is, to count as a solution, the labels on any row, column and sub-board square must be a bijection with the set of labels. (On infinite boards, this is a stronger requirement than merely insisting on no repetitions.)
The Solver-Spoiler game makes sense in complete generality on any set
Upon reflection, one realizes that what matters about
What I claim is that the Solver has a winning strategy in the all the infinite Sudoku Solver-Spoiler games, in a very general and robust manner.
Theorem. For every infinite cardinal
- The strategy will win in
many moves, producing a full Sudoku solution. - The Solver can win whether she goes first or second, starting from any legal position of size less than
. - The Solver can win even when the Spoiler is allowed to play finitely many labels at once on each turn, or fewer than
many moves (if is regular), even if the Solver is only allowed one move each turn. - In the countably infinite Sudoku game, the Solver can win even if the Spoiler is allowed to make infinitely many moves at once, provided only that the resulting position can in principle be extended to a full solution.
Proof. Consider first the countably infinite Sudoku game, and assume the initial position is finite and that the Spoiler will make finitely many moves on each turn. Consider what it means for the Solver to win at the limit. It means, first of all, that there are no explicit repetitions in any row, column or sub-board. This requirement will be ensured since it is part of the rules for legal play not to violate it. Next, the Solver wants to ensure that every square has a label on it and that every label appears at least once in every row, every column and every sub-board. If we think of these as individual specific requirements, we have countably many requirements in all, and I claim that we can arrange that the Solver will simply satisfy the
The argument works equally well no matter who goes first or if the Spoiler makes arbitrary finite play, or indeed even infinite play, provided that the play is part of some global solution (perhaps a different one each time), since on each move the Solve can simply meet the requirement by using that solution at that stage.
An essentially similar argument works when
I find it interesting to draw out the following aspect of the argument:
Observation. Every finite labeling of an infinite Sudoku board that does not yet explicitly violate the Sudoku condition can be extended to a global solution.
Similarly, any size less than
What about asymmetric boards? It has come to my attention that people sometimes look at asymmetric Sudoku boards, whose sub-boards are not square, such as in the six-by-six Sudoku case. In general, one could take Sudoku boards to consist of a
In the finite
In the case
Finally, let’s consider the Sudoku Solver-Spoiler game in the purely finite case, which actually is a very natural game, perhaps more natural than what I called the Sudoku game above. It seems to me that the Spoiler should be able to win the Solver-Spoiler game on any nontrivial finite board. But I don’t yet have an argument proving this. I asked a question on MathOverflow: The Sudoku game: Solver-Spoiler variation.
Does the Solver need to fill every cell, or do they need to simply put every element in every box, row, and column (potentially leaving cells empty)?
Oh, nvm, you accounted for that.
Yes, that’s right; it’s one of the requirements to fill in every square. A global Sudoku solution has a label in every square, and the labels in every row, column and sub-board square are a bijection to the set of labels.
May I ask whether you might be user PyRulez? (Your name appears in the email of his user profile.) If so, I’d like to use your real name in my post, unless you would prefer I didn’t.
Oh sure, that’s fine. PyRulez is just an old pseudonym that I haven’t gotten around to changing. My full name is Christopher King.
OK good, I used your full regular name.
Does the infinite sudoku result extend to Jigsaw Sudoku puzzles? (https://krazydad.com/jigsawsudoku/) The proof doesn’t seem to generalize, because a row could be covered by a finite number of boxes (regions), and you put a 1 in each box (but not on that row), thereby making it impossible to put a 1 in that row (showing that the observation is false for jigsaw sudoku).
Yes, I think you’re right, and I think I also need to change my thinking about the asymmetric case , to which your objection also applies. Indeed, the rectangle case is just a particularly simply kind of jigsaw case. So I’m not sure what happens, and I think I expect the spoiler to win this case.
Pingback: Infinite Sudoku and the Sudoku game – Nevin Manimala’s Blog
The Mbrane game app is an implementation of a partisan Sudoku game [M]. (We’re calling them m,n,p-games, where m is the matrix base, n the number of dimensions, and p the positional probabilities, in the latter case to reinforce the economic context.) I would love to know your thoughts!
We make the distinction between games and puzzles as: “in the Sudoku puzzle, each region, row and column *must* contain a single instance of a given element; in the Sudoku game, each region, row and column *may* contain only a single instance of a given element.” (One of the barriers I’ve found in trying to talk to mathematicians is unawareness of the legality of a non global solution.)
Your solution for even-order Sudoku definitely extends to this game in n dimensions, partisan nature notwithstanding, except that the result is always a perfect tie if second player mirrors starting player’s positions. (I was trying to learn how to prove that, but it’s clear you already have;) This opens up some interesting questions about symmetry breaking, in the sense that, where the game is non-trivial (game tree is intractable), player two will only mirror player one if they *perceive* player one’s position to be optimal.
This can be extended to three player [M] where the option to break the symmetry cycles between players for any (m²)² Sudoku where m is even:
turn(1): Player 1
turn(2): Player 2
turn(3): Player 3
turn(4): Player 1
turn(5): Player 2
turn(6): Player 3
turn(7): Player 1
turn(8): Player 2
turn order as a modulo function;)
This should extend to (mⁿ)ⁿ where m is even.
PS
The website in my link connects to a non-commercial app that is free, ad free and collects no data. Check it out if you want to see the the pattern breaking in action. Features automata vs. automata so you can just watch the robots play if partisan games are not your thing. We’d especially like to know Hypatia’s thoughts–I’m not at all surprised she was the one to see the even Sudoku solution. (Kids seem to be the most enthusiastic players–my 7 year old niece can consistently beat the random and rando-max AI, who she now laughs at as “silly”;) The solution can be demonstrated on (2²)² Sudoku, which has a surprisingly great gametree, but is nonetheless trivial. We don’t have the (2²)² out for the public yet because we weren’t sure it was fun, but we will be including that grid and many others in our next major update.
Formatting error. On the turn order, players can break symmetry on turns 2,4,6,8–any even numbered turn up until the last turn if there is a global solution.
Daniel Allcock made the following observation about the finite game. Suppose you want to win but not have it be obvious that you’re following a symmetric strategy. Use the fact that there are lots of permutations which preserve sudoku solutions: you can switch two columns within the same block, or you can switch two columns of blocks, etc. So fix a weird permutation that preserves solutions and follow the symmetric strategy on the permuted board.
Another point is that the -complement can be replaced by any involution (even case) or any involution with exactly one fixed point (odd case).