| Bytes | Lang | Time | Link |
|---|---|---|---|
| 332 | Python3 | 240717T013651Z | Ajax1234 |
| 082 | JavaScript ES6 | 210614T222205Z | Arnauld |
| 197 | JavaScript Node.js | 210615T093935Z | user1006 |
| 056 | Charcoal | 210614T231651Z | Neil |
| 027 | Jelly | 210614T181423Z | Nick Ken |
| 071 | J | 210614T220123Z | Jonah |
| 027 | 05AB1E | 210614T213614Z | ovs |
| 033 | Jelly | 210614T173405Z | hyper-ne |
Python3, 332 bytes
Longer than it could be, but crunches all the test cases in less than a tenth of a second.
R=range
def f(s,p):
b=[0 for _ in R(9)];b[p-1]=s
q=[(b,0,{*R(1,10)}-{s})]
while q:
q=sorted(q,key=lambda x:x[1],reverse=1)
b,c,s=q.pop(0)
if c==9:return b
if b[c]:q+=[(b,c+1,s)];continue
for j in s:
B=[*b];B[c]=j;T=[B[i:i+3]for i in R(0,9,3)]
if all(sum(j%2 for j in t)<3 for t in T+[*zip(*T)]):q+=[(B,c+1,s-{j})]
JavaScript (ES6), 85 82 bytes
Expects (square)(turn) and returns a flat array of 9 values. Everything is 0-indexed.
s=>n=>[...a=2135+[s-6?408:804]+67].map(x=>s--?((x+=q=n-v&1)%9-n?x:v+q)%9:n,v=a[s])
How?
We are given a target square \$s\$ and a turn \$n\$, both 0-indexed.
We use the following template by default:
$$\begin{pmatrix}2&1&3\\5&4&0\\8&6&7\end{pmatrix}$$
whose flattened representation is \$[2,1,3,5,4,0,8,6,7]\$.
But if \$s=6\$, we use this one instead where the \$8\$ and the \$4\$ are swapped:
$$\begin{pmatrix}2&1&3\\5&\color{red}8&0\\\color{red}4&6&7\end{pmatrix}$$
Both templates encode the same mark configuration. Assuming \$\text{X}\$ play first, this gives:
$$\begin{pmatrix}\text{X}&\text{O}&\text{O}\\\text{O}&\text{X}&\text{X}\\\text{X}&\text{X}&\text{O}\end{pmatrix}$$
Let \$v\$ be the original value stored on the target square.
If \$n-v\$ is odd, we increment all squares modulo \$9\$ [1]. This means that all parities are inverted, except \$8\$ which is turned into \$0\$ and remains even. That's why we need a slightly different board if the target square is the bottom left one.
Below are the mark configurations after the parity transformation for the default template (left) and the alternate template (right):
$$\begin{pmatrix}\text{O}&\text{X}&\text{X}\\\text{X}&\text{O}&\text{O}\\\text{X}&\text{O}&\text{X}\end{pmatrix} \begin{pmatrix}\text{O}&\text{X}&\text{X}\\\text{X}&\text{X}&\text{O}\\\text{O}&\text{O}&\text{X}\end{pmatrix} $$
At this point, it is guaranteed that:
- the board is valid (i.e. there are five \$\text{X}\$ and four \$\text{O}\$ and the game is a draw)
- the target square has the correct parity
We can now swap the values of the target square and the square holding \$n\$.
[1]: Because the board is described as an array of digit characters, the code (x += q = n - v & 1) % 9 is actually concatenating either \$0\$ or \$1\$ to x and reduces the result modulo \$9\$. This gives the expected result because \$(x \times 10 + k) \bmod 9\$ = \$(x + k) \bmod 9\$ (with \$k=0\$ or \$k=1\$).
Example
For \$s=1\$ and \$n=6\$:
- we have \$s\neq 6\$, so we use the default template
- we have \$v=1\$ and \$n-v=5\$, so the squares are incremented modulo \$9\$
- the square at index \$3\$ holds \$n\$ after the transformation, so that's the one that is exchanged with the target square
$$\begin{pmatrix}2&1&3\\5&4&0\\8&6&7\end{pmatrix} \rightarrow \begin{pmatrix}3&2&4\\6&5&1\\0&7&8\end{pmatrix} \rightarrow \begin{pmatrix}3&\color{red}6&4\\\color{red}2&5&1\\0&7&8\end{pmatrix} $$
JavaScript (Node.js), 197 bytes
s=>t=>(g=n=>n[1]?n.flatMap(e=>g(n.filter(h=>h!=e)).map(l=>[e,...l])):n)([...'123456789']).filter(e=>e[s-1]==t&'012A345A678A048A246A036A147A258'.split`A`.every(T=>[...T].some(j=>e[j]%2!=e[T[0]]%2)))
Outputs all valid boards. Although, on TIO, I have only console.logged the first 100 boards in a human-readable format. I have also, of course, displayed the number of valid boards using .length, 4608 in the case of the sample input.
Feels too long.
How?
The helper g outputs all permutations of a list. Initial call is with the list [...'123456789'] which spreads the string out. What g does is self-explanatory: if n has a second element, map each element of n to that element plus a recursive call to g with the remaining elements, and otherwise return n.
Then filters based on whether the input move is at the right spot and if, for every three-character string in the split string, no three odds or evens are in a row.
Charcoal, 56 bytes
NθNη⪪⁺1234⁺§⪪657576³θ98³W﹪⁻§KAηθ²⟲W⁻§KAηθUMKAI⎇‹κ3⁻χκ⁻κ²
Try it online! Link is to verbose version of code. Takes the square number as 0-indexed but the turn number as 1-indexed (could readily be made 0-indexed though). Explanation: Excluding rotations and reflections, and assuming X goes first, there are only three final positions:
XOX XOX XXO
OXX OOX OOX
OXO XXO XXO
It just remains to number and/or rotate and/or reflect one of these positions in such a way that the desired play appears on the desired turn.
NθNη
Input the 0-indexed square and the 1-indexed turn.
⪪⁺1234⁺§⪪657576³θ98³
If the turn number is even then build up the string 123465798 (corresponding to the first pattern) otherwise build up the string 123457698 (corresponding to the second pattern; I don't use the third pattern). Split it into a 3×3 square.
W﹪⁻§KAηθ²⟲
Rotate the square until the number under the desired square has the same parity as the desired turn.
W⁻§KAηθ
Repeat until the number under the desired square is the desired turn...
UMKAI⎇‹κ3⁻χκ⁻κ²
... cyclically shuffle X's turns and (separately) O's turns.
Jelly, 30 27 bytes
,UŒDḢ€;;ZḂE€Ẹ
9Œ!aƑ@Ƈs€3ÇÐḟ
A pair of links that takes a mask for the answer and returns all possible solutions matching the mask as a list of lists of lists of integers.
Explanation
Helper link
Takes a 3x3 grid and checks if any row, column or diagonal has all odd or all even numbers
,U | Pair with copy of grid with each row reversed
ŒDḢ€ | Main diagonal of each
; | Concatenate to rows
;Z | Concatenate to columns
Ḃ | Mod 2
E€ | Check if each is all equal
Ẹ | Any
Main link
9Œ! | Permutations of 1..9
aƑ@Ƈ | Keep those where the mask AND the permutation equals the mask
s€3 | Split each into lists length 3
ÇÐḟ | Keep those where the helper link is false
J, 71 bytes
[:(([:*/3>1#.2|],|:,#:@273 84#,)"2#])a 3 3&$"1@#~]=[{"1 a=:(i.@!A.i.)@9
Method is straightforward and similar to other answers: Generate all 9! boards, then filter by those that have the move in the required position, then filter by cats games.
05AB1E, 27 bytes
Takes the 0-based index as the first input and the number to place as the second input.
9Lœʒ¹èQ}3δôʒyø«y‚€Å\«É€Ëà≠
9Lœ # all permutations of [1 .. 9]
ʒ¹èQ} # keep a if a[¹] == ²
3δô # split each permutation in groups of 3
ʒ # keep grids where:
yø« # concatencate the transpose to the grid
y‚ # pair the grid and its reverse
ہ\ # for each: take the main diagonal; this is the main and anti-diagonal
« # concatenate the diagonals to rows and columns
É # each integer modulo 2
€Ë # for each sublist: are all values equal
à # take the maximum / is any 1?
≠ # boolean negate (!= 1)
Jelly, 33 bytes
;s3ZFƊ;92149ṃ$s3EƇ
9Œ!ḂÇ$Ðḟ³ị=⁴ƲƇ
Outputs all valid boards. This is really slow - I can't guarantee it'll complete on TIO; it seems to depend on how lucky I get with CPU allocation. I am also pretty confident this is solvable in like half the bytes.
;s3ZFƊ;92149ṃ$s3EƇ Helper Link; determine if a board is not tied (given a flat list of 0s and 1s)
; Append:
----Ɗ - The list,
s3 - Sliced into sublists of size 3,
Z - Transposed,
F - Flattened
; Append:
92149ṃ$ 92149, base decompressed into the list (index 1, 5, 0, 3, 5, 7 - where 0 is the last element)
s3 Slice into sublists of size 3 (this now has each row, column, and diagonal)
EƇ Filter to keep sublists that are all equal (and thus indicate a win)
9Œ!ḂÇ$Ðḟ³ị=⁴ƲƇ Main Link (dyad); accept x (index) and y (turn)
9Œ! All permutations of 9 (implicit range)
$Ðḟ Filter; remove all boards where
Ḃ % 2 (convert turn numbers to X/O)
Ç Call helper link (remove boards that aren't ties)
ƲƇ Filter to keep boards where
³ị The element at index (x)
=⁴ Equals (y)