A Cat’s Game to Claim

Question

Intro

You like cats. Naturally, you like cat’s games in tic-tac-toe. So, you’ve come up with a little party trick.

You ask someone what square on the board they want you to make a move in. And you ask someone else on which turn they want you to make that move. You also let that person decide whether you play Xs or Os. And with that, you’re off to the races.

You play your sidekick with the side they chose for you. And sure enough, when the turn they chose comes around, you move just in the spot they chose. And from there, you're able to secure a cat's game with your sidekick. (Your sidekick could take advantage of your forced move and beat you, or God forbid they could take the square first, but they're your trusty sidekick after all.) Et voila!

You’re convinced that you can end in a cat’s game no matter what they give you, but you want to make sure. Let’s give you a hand!

Challenge

Given a move on the tic-tac-toe board and a turn to make the move on, output a tied game where that move was played. A cat's game!

Any input/output to represent the given info and the resulting game is accepted. But here is the convention I’ll use in the examples:

There are 9 squares on a tic-tac-toe boards, and there are 9 turns in a drawn game, because every square must be filled. So my input examples will take a pair of integers 1-9. The first number will represent the turn number and the second number the square on the board to move in. Whether the turn number is even or odd tells you whether you’re playing X or O. My outputs will be the numbers 1-9 printed in a 3×3, representing the placement of the nth move. And the input is marked in parentheses, for easy reading.

Again, you may change the I/O scheme. Your output can, for example, flatten the grid and just return a simple list. This is what almost everyone has chosen, maybe you have another idea! Perhaps a list of numbers indicating the nth move made. And your input can switch the turn and move numbers, or do it entirely differently.

So with this particular I/O scheme, 3 5 represents moving in the 5th square, which is the center, on your 3rd turn. And your turn is odd, so you’re playing as X who is the first/odd player.

This is code-golf, so the shortest code in bytes wins.

Equivalently

One can frame the problem equivalently: Arrange the numbers 1-9 in a square such that you have no three evens or odds in a row. (With one number’s placement given by the input.) The fact that this can be solved by playing Tic Tac Toe means that this problem can be solved with a greedy algorithm!

Test Cases

>> 3 5

  8  5  7
  9 (3) 2
  6  4  1

>> 5 3

  9  8 (5)
  2  3  1
  4  7  6

>> 7 4

  5  4  1
 (7) 6  2
  8  9  3

>> 1 1

 (1) 2  4
  6  3  5
  7  9  8 

>> 9 9

  4  5  1
  7  6  2
  3  8 (9)

P.S. For those wondering about the title, I don’t know how widespread this is, but we always called a draw “a cat’s game”: Wiktionary & Etymology

Answer 1

Jelly, 33 bytes

;s3ZFƊ;92149ṃ$s3EƇ
9Œ!ḂÇ$Ðḟ³ị=⁴ƲƇ

Try it online!

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)

Answer 2

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

Try it online!

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

Answer 3

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‚€Å\«É€Ëà≠

Try it online!

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)

Answer 4

Jelly, 30 27 bytes

,UŒDḢ€;;ZḂE€Ẹ
9Œ!aƑ@Ƈs€3ÇÐḟ

Try it online!

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

Answer 5

Charcoal, 56 bytes

ＮθＮη⪪⁺1234⁺§⪪657576³θ98³Ｗ﹪⁻§ＫＡηθ²⟲Ｗ⁻§ＫＡηθＵＭＫＡＩ⎇‹κ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.

ＮθＮη

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.

Ｗ﹪⁻§ＫＡηθ²⟲

Rotate the square until the number under the desired square has the same parity as the desired turn.

Ｗ⁻§ＫＡηθ

Repeat until the number under the desired square is the desired turn...

ＵＭＫＡＩ⎇‹κ3⁻χκ⁻κ²

... cyclically shuffle X's turns and (separately) O's turns.

Answer 6

J, 71 bytes

[:(([:*/3>1#.2|],|:,#:@273 84#,)"2#])a 3 3&$"1@#~]=[{"1 a=:(i.@!A.i.)@9

Try it online!

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.

Answer 7

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

Try it online!

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.