Devising a sudoku where the rows are the moves for a draw in tic tac toe

Question

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

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.

Answer 1

Solution:

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

Answer 2

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