14
$\begingroup$

The task is to construct a sudoku whose rows (or columns) are the moves for a game in tic tac toe where the game ends in a draw.

Here are some clarifications and constraints which should limit towards a solution.

Consider the $3*3$ grid of a regular tic tac toe with an embedded number pad, like the top left cell as 1, top centre cell as 2.... all the way down to the down right cell as 9.

The first number the series makes is of X, and the next number by O, and so on, until the game ends.

For example, the game shown by this notation is a good draw (the end result game is shown in the picture, and the order accordingly) : $6-5-3-9-1-2-8-7-4$.

enter image description here

So basically, construct a grid consisting of numbers 1 to 9, with no digits repeating in the rows and the columns, i.e. construct a Sudoku where the numbers in the rows/columns indicate a game of tic tac toe where the game ends in a draw.

I'm really curious if the grid with the exact sudoku conditions exists or not. I've been thinking about this puzzle all day and I haven't even got near to an answer. I thought it is a nice question and thought why not share it with you all. Hoping to see some great answers.

$\endgroup$
6
  • $\begingroup$ Is it permitted for the tic tac toe game to have been played sub-optimally? That is, can a player have had a chance to win and still drawn? $\endgroup$ Nov 8, 2014 at 19:14
  • $\begingroup$ @frodoskywalker I have assumed "yes". And I have assumed that a won game continues to fill the squares $\endgroup$
    – d'alar'cop
    Nov 8, 2014 at 21:16
  • $\begingroup$ But the question called for a sudoku whose rows (or columns) are the moves for a game in tic tac toe where the game ends in a draw. $\endgroup$ Nov 8, 2014 at 22:15
  • $\begingroup$ @frodoskywalker ah yes, indeed despite my interpretation I would still exclude those games which were not a draw. so it makes no difference that I assume that a won game continues till all squares are full $\endgroup$
    – d'alar'cop
    Nov 9, 2014 at 4:58
  • $\begingroup$ I have shown an example above which does show a possible row of the desired sudoku. It's not about the probability of winning. The row is a game which ends in a draw. $\endgroup$
    – Rohinb97
    Nov 9, 2014 at 5:43

2 Answers 2

11
+500
$\begingroup$

Solution:

enter image description here

Explanation:

  • I noticed that there are only ${9\choose5 }= 126$ ways for the $X$ to play a game.
  • I noticed that only $28$ of these would not represent a win for $X$
  • I then noticed that of the $28$ some may be a win for $O$. It turns out that after removing those which would be a win for $O$ there are $16$ left. i.e. $(\mbox{all games for X}) \setminus ((\mbox{X wins}) \cup (\mbox{O wins})) = draws \land |draws| = 16$

So far, this means that are $16$ ways where (disregarding move order) we have a draw. Since with a draw, and, in particular, in our case, we don't care about move order we are doing OK. Call the moves $x_1 \cdots x_5$ and put all $16$ in a set called $S$.

Given a row or column $p$ whose elements are $p_1 \cdots p_9$, we just want for $\{p_1,p_3,p_5,p_7,p_9\}\in S$.

I used a powerful SAT/SMT Solver within which I had built a Sudoku solver and added the above additional constraint to every row and column and it produced the above sample solution. I suspect there are many (I can count them if you really want - that would surely take much time).


Notes:

I had some mathematical definition for a draw in tic-tac-toe. I'm sure it's suboptimal, and it did not end up helping to produce the solution. But, I put it here just as a record.

A row/column $L$ is an array of elements $(p_1 \cdots p_9)$ where $\forall i \not= j.p_k \in \{1,\cdots,9\} \land p_i \not= p_j$. Let player 1 be known as $pX$. $pX$'s moves are $X = \{ p_1,p_3,p_5,p_7,p_9\}$. Let player 2 be known as $pO$. $pO$'s moves are $O = \{ p_2,p_4,p_6,p_8\}$.

Let $pr^n$ be the $n^{th}$ prime number.

No wins across diagonals: $$f1 = \lnot(\exists x \in \{45,105\}. x | \prod X \lor x | \prod O)$$

No wins across rows: $$f2 = \lnot(\exists x \in \mathbb{N}.(x^3 | (\prod\limits^{|X|}_{i=0} pr^{\lfloor (X_i-1) / 3 \rfloor}) \lor x^3 | (\prod\limits^{|O|}_{i=0} pr^{\lfloor (O_i-1) / 3 \rfloor})))$$

No wins across columns: $$f3 = \lnot(\exists x \in \mathbb{N}.(x^3 | (\prod\limits^{|X|}_{i=0} pr^{X_i \mod 3}) \lor x^3 | (\prod\limits^{|O|}_{i=0} pr^{O_i \mod 3})))$$

A mapping of values to $L$ is a draw if $f1 \land f2 \land f3$.

$\endgroup$
5
  • $\begingroup$ That is impressive..couldn't have thought that way. Effort appreciated. But I have to admit I lost you after you said prime number thing. $\endgroup$
    – Rohinb97
    Nov 10, 2014 at 16:59
  • $\begingroup$ Do both the rows and the columns signify the draw games? $\endgroup$
    – Rohinb97
    Nov 10, 2014 at 17:02
  • $\begingroup$ @Rohinb97 Yes, both rows and columns are drawn games. I suppose we could look for the boxes to be drawn games too! glad you liked it :) $\endgroup$
    – d'alar'cop
    Nov 10, 2014 at 17:09
  • 1
    $\begingroup$ Gotta say, one reason I love this site is that puzzles like this make me improve my SAT-solver interface. Thanks to puzzling.SE, it's now user-friendly enough that I can encode the Sudoku constraints in a few minutes. The tic-tac-toe constraints are harder, maybe 15 minutes, but way less than if I tried to work with bare SAT booleans. $\endgroup$
    – Lopsy
    May 2, 2015 at 23:34
  • $\begingroup$ "So far, this means that are 16 ways where (disregarding move order) we have a draw. " After reading this line, I felt that one way to solve this is to try all 16^9 possibilities. This will, of course, involve a computer. I couldn't understand much after that but I have two questions . Were you able to find a solution to this question which didn't need to look at all the 16^9 possibilities in the worst case ? Secondly, does your method need the help of a computer to find the solution ? $\endgroup$ Jul 3, 2021 at 19:59
2
$\begingroup$

Answer incomplete. This should probably be finished by a computer search, but I don't know how to do it efficiently enough. The ideas here may help some with efficiency.


There are three possible tic-tac-toe draw configurations, up to rotation and reflection:

  A         B         C
o x x     x o x     x o x
x x o     o o x     x o x
o o x     x x o     o x o

Let $a,b,c$ be the number of rows of type A, B, and C respectively.

Notice that the first, third, fifth, seventh, and ninth columns represent moves of X, and the second, fourth, sixth, and eigth columns represent moves of O. Call these columns "X columns" and "O columns" respectively.

The total number of 1s, 3s, 7s, and 9s in the X columns must be 20 (4 for each of 5 columns), while the total number of 1s, 3s, 7s, and 9s in the O columns must be 16 (4 for each of 4 columns). The 1s, 3s, 7s, and 9s in A and C are made up of two Xs and two Os, and in B they are made up of three Xs and one O (1, 3, 7, 9 are the four corner squares in tic-tac-toe). So we get that the total number in the X columns is $2a + 2c + 3b = 20$, and the total number in the O columns is $2a + 2c + 1b = 16$.

Likewise, the total number of 2s, 4s, 6s, and 8s in the X columns must be 20, while the total number of 2s, 4s, 6s, and 8s in the O columns must be 16. The 2s, 4s, 6s, and 8s in A and B are made up of of two Xs and two Os, and in C they are made up of three Xs and one O (2, 4, 6, 8 are the four side squares in tic-tac-toe). So we get that the total number in the X columns is $2a + 2b + 3c = 20$, and the total number in the O columns is $2a + 2b + 1c = 16$.

Therefore, we have \begin{align} 2a + 2c + 3b &= 20 \tag{1} \\ 2a + 2c + b &= 16 \tag{2} \\ 2a + 2b + 3c &= 20 \tag{3} \\ 2a + 2b + c &= 16 \tag{4} \end{align} Subtracting (3) from (1), $b - c = 0$. Subtracting (2) from (1), $2b = 4$. So $b = 2$, $c = 2$, and $a = 5$...

$\endgroup$
4
  • $\begingroup$ Explain the downvote? I explicitly said this was incomplete. It wasn't intended as an answer, but the work here is correct. $\endgroup$ Nov 10, 2014 at 0:18
  • $\begingroup$ It's a nice effort, but I'm not sure whether that will help so much to get to a solution. $\endgroup$
    – Rohinb97
    Nov 10, 2014 at 16:54
  • $\begingroup$ @Rohinb97 It does restrict the number of possibilities for the sudoku board considerably; if one is able to write an algorithm to solve the board that incorporates the fact that there are 2, 2, and 5 rows of each type it would be significantly faster than not incorporating that. But obviously it is not feasible to continue this way by hand. $\endgroup$ Nov 10, 2014 at 20:33
  • 1
    $\begingroup$ @Rohinb97 I don't mean to claim this answer is useful as is in any way. I just thought I'd post it because I think it's nontrivial, and in case anyone else had any ideas to incorporate it in an algorithm or further work. In fact, I originally did this work attempting to disprove that a solution existed, because I thought the equations in $a,b,$ and $c$ might have no solution. $\endgroup$ Nov 10, 2014 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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