13
$\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$
  • $\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$ – frodoskywalker Nov 8 '14 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 '14 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$ – frodoskywalker Nov 8 '14 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 '14 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 '14 at 5:43
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$
  • $\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 '14 at 16:59
  • $\begingroup$ Do both the rows and the columns signify the draw games? $\endgroup$ – Rohinb97 Nov 10 '14 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 '14 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 '15 at 23:34
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$
  • $\begingroup$ Explain the downvote? I explicitly said this was incomplete. It wasn't intended as an answer, but the work here is correct. $\endgroup$ – 6005 Nov 10 '14 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 '14 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$ – 6005 Nov 10 '14 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$ – 6005 Nov 10 '14 at 20:36

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.