Tic-Tac-Toe Puzzle – How to Achieve the Aim

permutationspuzzletic tac toe

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.

Best Answer

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.

Related Question