[Math] Who wins two player sudoku

combinatorial-game-theorypuzzlerecreational-mathematicssudokusurreal-numbers

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.)

Best Answer

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.