Is the aim of this Tic-Tac-Toe puzzle possible to achieve?

Question

I was playing Tic-Tac-Toe with my friend when I came up with a puzzle. I might have to put this on the Puzzling Stack Exchange, but I do not know if the aim of the puzzle can be achieved. I am aware that math(s) is incorporated, so that is why I am posting this here.

---

Puzzle:

You have a $3\times 3$ Tic-Tac-Toe board; i.e.,

$$\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|X| &\verb|O|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}$$

Now, you must swap the position of an $\verb|X|$ and an $\verb|O|$; e.g.,

$$\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|X| &\verb|O|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}\stackrel{\nwarrow}{\leftarrow}\rm swap \ position\implies\begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\verb|X| &\verb|X|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}$$

Now, the Tic-Tac-Toe board can be split into four sections $A, B, C$ and $D$ such that

$$\begin{align}\color{red}{A}&=\begin{array}{c|c|} \verb|X| &\verb|O|\\ \hline \verb|O| &\verb|X|\\ \hline \end{array} \qquad \begin{array}{r|c} \color{red}{\verb|X|} &\color{red}{\verb|O|} &\verb|O|\\ \hline \color{red}{\verb|O|} &\color{red}{\verb|X|} &\verb|X|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array} \\ \color{darkorange}{B}&=\begin{array}{|c|c} \verb|O| &\verb|O|\\ \hline \verb|X| &\verb|X|\\ \hline \end{array} \qquad \begin{array}{r|c} \verb|X| &\color{darkorange}{\verb|O|} &\color{darkorange}{\verb|O|}\\ \hline \verb|O| &\color{darkorange}{\verb|X|} &\color{darkorange}{\verb|X|}\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array} \\ \color{blue}{C}&=\begin{array}{c|c|} \hline \verb|O| &\verb|X|\\ \hline \verb|X| &\verb|O|\\ \end{array} \qquad \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \color{blue}{\verb|O|} &\color{blue}{\verb|X|} &\verb|X|\\ \hline \color{blue}{\verb|X|} &\color{blue}{\verb|O|} &\verb|X|\\ \end{array} \\ \color{green}{D}&=\begin{array}{|c|c} \hline \verb|X| &\verb|X|\\ \hline \verb|O| &\verb|X|\\ \end{array} \qquad \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\color{green}{\verb|X|} &\color{green}{\verb|X|}\\ \hline \verb|X| &\color{green}{\verb|O|} &\color{green}{\verb|X|}\\ \end{array}\end{align}$$

You can rotate these sections $k\cdot 90^\circ$ for some natural number $k$. Of course, the number of $\verb|X|$s and $\verb|O|$s in these sections will vary depending on which ones are rotated and which ones are not.

Aim: Try to make the board into what it is in the sandbox above.

---

Question:

Is this even possible? I do not think so... but I do not know how to prove it. I have a computer, but I cannot program these kinds of things. I have tried the puzzle myself plenty of times, but I have not solved it. It would be much appreciated if someone can find out whether or not it is possible.

Thank you in advance.

P.S. There are other related posts, but they are not quite what I am looking for.

Answer 1

One can do even better than that. In fact, you can color the squares in your board in 9 different colors and permute them any which way, and you can still get back to the original configuration by a sequence of rotations of the four $2\times 2$ corner squares.

To wit: This sequence of moves

1. Turn the upper right corner clockwise
2. Then the lower left corner clockwise
3. Turn the upper right corner counterclockwise
4. Then the lower left corner counterclockwise

(in group-theoretic language, this is a commutator) has the net effect of permuting only the middle row cyclically. It is easy to see that we can get any three squares we want into the middle row if we don't care what happens to the other six, so any 3-cycle of squares can be realized as a conjugate of this commutator.

Thus (since the 3-cycles generate the alternating group) we can make any even permutation of the squares.

However, a single quarter turn of one of the corners is an odd permutation, so if we need to solve from an odd state simply turn one of the corners and then solve the resulting even states.

QED. Therefore, answer to original question is yes, you can.

---

Extras

Extra: symbols with orientation

How much of a restriction is it if you use 9 symbols that have orientation such that you can tell if one of them is upside down?

If we place dots in two corners of each tile, like this:

    *   |   * | *
      * | *   |   *
    ----+-----+----
      * | *   |   *
    *   |   * | *
    ----+-----+----
    *   |   * | *
      * | *   |   *

then each move leaves the pattern of dots unchanged, so there are only two legal orientations of each tile in each position. Furthermore, each move is an even permutation of the dots (namely, two 4-cycles), so it is not possible to flip just a single tile upside down.

But we can flip any even number of tiles upside down. Repeating this sequence (known to Rubik aficionados as the Y-commutator) twice:

1. Lower left clockwise
2. Lower right counterclockwise
3. Lower left counterclockwise
4. Lower right clockwise

the net effect is to flip four tiles upside down. Do that again from the other side of the board, and you will flip three of them back, and a fifth one once, for a net effect of flipping two tiles. Conjugations of this will let you flip an even number of tiles.

Taking orientations into account, there are therefore $9!\cdot 2^8=92{,}897{,}280$ valid positions, because the orientation of the last tile is determined once we have chosen orientations for eight of them.

---

Extra: symbols with orientation plus upright constraint

Which configurations are possible if we require that the orientable symbols must all be upright at the end, even if the square is not in the right place?

The picture with dots above makes clear that we can't move a tile between an "X" position and an "O" position and keep its orientation. So the 5 "X" tiles must be permuted among themselves, as must the 4 "O" tiles. But are there any more restrictions? A priori it might be that some of the permutations that follow this rule can only be realized with an odd number of upside-down tiles.

Suppose in the initial position we place two dots diagonally on each tile as above, but now the "upper" dot is red and the "lower" dot is green. Each basic move changes the color of the "upper" dot for two of the tiles it moves. So once we have gotten everything into the right place, there's an even number of tiles that are upside down relative to their original orientation. And we know we can fix that!

So all $5!\cdot 4! = 2{,}880$ "upright" permutations of the "X" and "O" tiles separately are solvable, taking orientation into account.

Answer 2

$$ \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\verb|X| &\verb|X|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array} \to \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\verb|X| &\verb|X|\\ \hline \verb|X| &\verb|X| &\verb|O|\\ \end{array} \to \begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|O| &\verb|X|\\ \hline \verb|X| &\verb|X| &\verb|O|\\ \end{array} \to \begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|X| &\verb|O|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array} $$ It is possible to prove that 3 is the minimum number of moves needed in this case.

Answer 3

This is an elaboration of Exodd's answer. I wrote a python script to check if it is possible to get from any board with exactly $5$ X's to any other board with exactly $5$ X's as he had conjectured, and the answer is "yes." It turns out that you can't always do it in $3$ moves, however. Sometimes you need $4$.

The script below uses the Floyd-Warshall algorithm to find the length of the shortest path between every pair of boards. The distance between any two boards is initialized to $200,$ which is effectively $\infty$ since there are only $126$ boards; if you can get from one to another, you can certainly get there in $125$ moves or less.

from itertools import combinations
import numpy as np

def A(tic):
    tac = tic[:]
    tac[0]=tic[3]
    tac[1]=tic[0]
    tac[3]=tic[4]
    tac[4]=tic[1]
    return tac

def A2(tic):
    return A(A(tic))

def A3(tic):
    return A(A2(tic))

def B(tic):
    tac = tic[:]
    tac[1]=tic[4]
    tac[2]=tic[1]
    tac[4]=tic[5]
    tac[5]=tic[2]
    return tac

def B2(tic):
    return B(B(tic))

def B3(tic):
    return B(B2(tic))

def C(tic):
    tac = tic[:]
    tac[3]=tic[6]
    tac[4]=tic[3]
    tac[6]=tic[7]
    tac[7]=tic[4]
    return tac

def C2(tic):
    return C(C(tic))

def C3(tic):
    return C(C2(tic))

def D(tic):
    tac = tic[:]
    tac[4]=tic[7]
    tac[5]=tic[4]
    tac[7]=tic[8]
    tac[8]=tic[5]
    return tac

def D2(tic):
    return D(D(tic))

def D3(tic):
    return D(D2(tic))

def makeBoards():
    boards= []
    for c in combinations(range(9), 5):
        a=9*['0']
        for x in c:
            a[x]='1' 
        boards.append(a)
    return boards

def initialize():
    boards = makeBoards()
    answer = 200*np.ones((126,126), dtype = np.int)
    for n, brd in enumerate(boards):
        for F in (A,B,C,D,A2,B2,C2,D2,A3,B3,C3,D3):
            m=boards.index(F(brd))
            answer[n,m]=1
    for n in range(126):
        answer[n,n]=0
    return answer

def main():
    dist = initialize()
    vertices = range(126)
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i,j] > dist[i,k] + dist[k,j] :
                    dist[i,j] = dist[i,k] + dist[k,j] 
    for n in vertices:
        for m in range(n+1,126):
            if dist[n][m]==200:
                print("Can't get to ", m," from ", n)
    print(m, list(dist.flatten()).count(m))

if __name__=='__main__':
    main()

This produces the output:4 1382 meaning that the maximum distance was $4$ and that $1382$ pairs were found that required $4$ moves. Of course, if it takes $4$ moves to get from $X$ to $Y$ it also takes $4$ moves to get from $Y$ to $X,$ so there are really only $691$ such pairs. Not so many out of $\binom{126}{2}.$