34
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ So invalid as a game move is a proper subset of invalid as a Sudoku puzzle placement (toward a unique solution)? Gerhard "Wrong Can Mean Many Things" Paseman, 2018.04.14. $\endgroup$ – Gerhard Paseman Apr 14 '18 at 23:40
  • 3
    $\begingroup$ This is a finite game, and so one of the players must have a winning strategy by the fundamental theorem of finite games. Can we mount a strategy-stealing argument to show that it cannot be the second player? $\endgroup$ – Joel David Hamkins Apr 15 '18 at 0:18
  • 3
    $\begingroup$ I'm confused here. Sudoku, actual Sudoku that is trademarked by Nikoli publishing, both must be symmetrical in initial clues and also have only one solution. I'd assume either two players taking turns and timing it, or allow any player to make a move when they find one and then tallying up the number of moves as possible ways to "win" 2p Sudoku. If a player makes a move where the next player's move is invalid, then the current player's move is also invalid (as it creates an invalid board). Unless, as it appears, you're just filling up a board with numbers 1-9, why is this tagged Sudoku? $\endgroup$ – n_b Apr 15 '18 at 3:01
  • 6
    $\begingroup$ @n_b To my way of thinking, the essence of Sudoku consists of the requirements for a completed solution that every row and column and each of the main $3\times 3$ subsquares should contain all the numbers 1 through 9. (The other "rules" you mention seem less important.) This is a game based fundamentally on those requirements, and so it makes sense to call it the Sudoku game. $\endgroup$ – Joel David Hamkins Apr 15 '18 at 11:58
  • 2
    $\begingroup$ @GerhardPaseman It does not need to be a solvable position. $\endgroup$ – PyRulez Apr 15 '18 at 20:45
38
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ I believe you can apply this winning strategy for player 1 on the $9\times 9$ board by first playing $5$ in the center, and then mirroring any move $x$ by player 2 through the center, you playing $10-x$. $\endgroup$ – orlp Apr 15 '18 at 1:37
  • 2
    $\begingroup$ I interpret partially filled as meaning the starting configuration is not an empty board. You might want to make clear that this mirror strategy is starting from an empty or a symmetrically filled board. Gerhard "Make Board And Strategy Clear" Paseman, 2018.04.14. $\endgroup$ – Gerhard Paseman Apr 15 '18 at 1:43
  • 2
    $\begingroup$ @JoelDavidHamkins: and what happens when the rows and columns of the subsquare are indexed by $\mathbb{N}$? :P $\endgroup$ – Sam Hopkins Apr 15 '18 at 14:15
  • 2
    $\begingroup$ @SamHopkins Nice idea! In the $\mathbb{Z}\times\mathbb{Z}$ subsquare case, where the whole board is $\mathbb{Z}^2\times\mathbb{Z}^2$, then the first player can ensure not to lose on her turn: play $0$ in the center of the center board, and afterwards play the negation ($\mathbb{Z}$'s complement) at the mirror location, just as in the odd-size board case. This strategy, however, will not ensure that the final board is filled in, nor that every subsquare, row and column uses all the numbers. $\endgroup$ – Joel David Hamkins Apr 15 '18 at 14:21
  • 2
    $\begingroup$ I'm pretty sure that betting on your daughter's future success in life is a winning strategy you adopted. $\endgroup$ – Sylvain JULIEN Apr 22 '18 at 21:54
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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