Who wins two player sudoku?

Question

Let's say players take turns placing numbers 1-9 on a sudoku board. They must not create an invalid position (meaning that you can not have the same number in within a row, column, or box region). The first player who can't move loses, and the other player wins.

Given a partially filled sudoku board, what is a way to evaluate the winner (or even better, the nimber) of the position (besides brute force)?

Additionally, has this perhaps been analyzed before?

(A natural generalization is to allow certain players to only play certain digits, in which case each position can be assigned a CGT game value.)

Answer 1

Update. I made a blog post about Infinite Sudoku and the Sudoku game, following up on ideas in this post and the comments below.

---

I claim that the second player wins the even-sized empty Sudoku boards and the first player wins for odd-sized empty Sudoku boards, including the main $9\times 9$ case. (The odd-case solution uses a key idea of user orlp in the comments.)

Consider first the even-sized board case, which is a little easier. For example, perhaps we have a board of size $16\times 16$, divided into subsquares of size $4\times 4$.

The second player can win in this case by the mirror-play strategy. (This argument was pointed out to me by my daughter, 11 years old.) That is, given any move by the other player, let the second player play the mirror image of that move through the origin. The new play cannot violate the Sudoku condition if the previous play did not, since the new violation would reflect to an earlier violation. The point is that on an even-sized board, the reflection of any row, column or subsquare will be a totally different row, column or subsquare, and so by maintaining symmetry, the second player can ensure that any violation of the Sudoku conditions will arise with the first player.

This copying strategy breaks down on the odd-sized board, however, including the main $9\times 9$ case, since there is a central row and column and a central subsquare and copying a move there would immediately violate the Sudoku conditions.

Nevertheless, user orlp explained in the comments how to adapt the mirroring strategy to the odd case.

Namely, in the main $9\times 9$ case, let's have the first player play a $5$ in the center square, and thereafter play the ten's complement mirror image of the opponent's moves. That is, if opponent played $x$, the first player should play $10-x$ in the mirror location. In this way, the first player can ensure that after her moves, the board is ten's complement symmetric through the origin. This implies that any violation of the Sudoku requirement will reduce by reflection to an earlier violation in the reflected moves, and so it is a winning strategy.

More generally, in the general odd case $k^2\times k^2$ for $k^2=2n-1$, player one will play $n$ in the middle square, and then proceed to play the $2n$'s complement mirroring move of the opponent. In this way, the first player ensures that after her play, the board remains $2n$'s complement symmetric, and this implies that she will not be the first to violate the Sudoku conditions. So it is a winning strategy.

Notice that in the even case, the second player could also have won by playing the complement mirror strategy, rather than the mirror strategy, since again any violation of the Sudoku condition would reflect to an earlier but complementary violation.

Finally, see my blog post for the winning strategy in the case of the Infinite Sudoku game, which came up in the comments.

Answer 2

It depends on the form of the 2 player Sudoku game, and whether it's partisan or impartial.

You can read more about intrinsic partisan Sudoku (m,n,p-games) here.

The solutions pointed out by Dr. Hamkins hold for the impartial forms of Sudoku games, but break down in non-reduced partisan forms.

The main distinction of partisan Sudoku is that the elements have value. We call the form reduced in which the values are binary (think Go and m,n,k-games). Each element in the Sudoku, regardless of label is either [+1,-1], which corresponds to "two colors" ("U&I", if you'll forgive the pun on Ultraviolet and Infrared;)

The reduced form of partisan Sudoku is interesting because it reduces to impartial Sudoku--the game sum using binary values delivers the same result as outcomes under normal or misère play:

In the even Sudoku game, second player can always mirror and the result will always be a 0. In the even game, player one can use the complement to mirror, and the outcome will always be a 1.

In the basic forms of partisan Sudoku (non-reduced) the elements have value corresponding to their labels, which correspond to the ordinal values in any set comprising a row, column or region.

Using the complement to mirror in the odd game does not assure victory, because the game sum is rooted in values base-$m^n$, where $(m^n)^n$ describes the matrix. (See the link above for different types of outcomes in the basic partisan forms of Sudoku. A distinction of partisan Sudoku games is that the outcomes are ratios.)

Furthermore, in the even-Sudoku partisan game, although player two can always mirror, player two will only mirror if they perceive player one to have placed optimally in regard to the un-reduced value of the placed element.

This is, of course, only where the game tree is still intractable. Sudoku games are wildly intractable at the outset, but, like all natively finite games, collapse into a determined state. (This is similar to a Wave Function Collapse).

The solution to the impartial game is the first serious mathematical work on Sudoku games I am aware of. I have little doubt this is a subject that will be rigorously studied, not least because the Sudoku puzzle, and Latin squares in general, have proven to be so useful.

From the abstract to The Chaos Within Sudoku:

The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle's hardness that correlates well with human difficulty ratings. Accordingly, η = −log10 κ can be used to define a “Richter”-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.