19
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Put differently---do the rotations $A,B,C,D$ generate all permutations $S_9$ of the board? This is interesting (and not obvious to me at a glance.) $\endgroup$ – user7530 Jul 6 '18 at 7:00
  • 4
    $\begingroup$ @user7530 Not necessarily. We don't care whether the $X$'s are permuted, or the $O$'s. So there might be a subgroup of $S_9$ which can freely move the $X$'s to any positions but without control over which $X$ goes where. $\endgroup$ – Arthur Jul 6 '18 at 7:07
  • 1
    $\begingroup$ It's possible. A lot of moves though $\endgroup$ – Exodd Jul 6 '18 at 8:10
  • 3
    $\begingroup$ Similar question on puzzling SE puzzling.stackexchange.com/questions/47124/… $\endgroup$ – Kruga Jul 6 '18 at 10:19
  • 1
    $\begingroup$ As the guy who asked (and answered) that similar question, I've recently managed to completely generalize the puzzle for the $n \times n$ board with $b \times b$ rotating blocks, with $n \geq b$. The algorithm is technical enough that I'm writing a paper on this to submit it to some research competitions and pray I make it through a round or two. $\endgroup$ – greenturtle3141 Aug 18 '18 at 23:25
25
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ For a particularly fiendish version of the puzzle, write the digits 1 to 9 on the tiles, such that 9 is a rotated 6. Then they can still be distinguished because 6 is sideways in an "X" position and 9 is sideways in an "Y" position. On the other hand, you might be able to flip the orientation of 1 and 8 together without a visible difference. $\endgroup$ – Henning Makholm Jul 6 '18 at 16:30
  • 4
    $\begingroup$ +1. Checked in GAP: Size(Group((7,8,5,4),(8,9,6,5),(4,5,2,1),(5,6,3,2))); returns 362880, i.e. 9!, i.e. the quarter-turns of 2x2 blocks do indeed generate the whole of $S_9$. $\endgroup$ – Rosie F Jul 7 '18 at 5:50
  • $\begingroup$ Congratulations! It was a beautiful answer! $$(+1) \ \ \color{green}{\checkmark}$$ $\endgroup$ – user477343 Jul 13 '18 at 13:05
12
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Notice that if you initialize 'answer' as 'answer = np.zeros(126)', you obtain the adjacency matrix of the graph $A$, so the diameter of the graph is the minimum $n$ such that $(I+A)^n$ is a full matrix $\endgroup$ – Exodd Jul 6 '18 at 10:57
  • 1
    $\begingroup$ @Exodd Yes, that's right, and it's how I checked that the diameter wasn't $3$. Floyd-Warshall is more efficient in theory, but now that I think of it, repeated matrix multiplication might better in python, since it would use compiled C code. $\endgroup$ – saulspatz Jul 6 '18 at 18:10
11
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ I have a proof for this particular case. Now I'm trying to prove it in general, since I think there are not so many possible configurations.. $\endgroup$ – Exodd Jul 6 '18 at 8:21
  • 12
    $\begingroup$ Ehm.. I just realized that there are a total of 126 positions possible, and they won't ever fit in the margin of the paper I'm writing on $\endgroup$ – Exodd Jul 6 '18 at 8:31
  • 2
    $\begingroup$ I'm working on a script to check this. If I'm not mistaken, the conjecture about 3 moves isn't right. I'm going to remove that restriction and see what I get. $\endgroup$ – saulspatz Jul 6 '18 at 9:18
  • 2
    $\begingroup$ @saulspatz ok. Thank you for that. Users on this site are so kind, sometimes $\stackrel{\bullet\,\bullet}{\smile}$ $\endgroup$ – user477343 Jul 6 '18 at 9:22
  • 1
    $\begingroup$ @user477343 (+1) for great question... I never knew \smile existed in $\LaTeX$! I suppose programs do have feelings :) $\endgroup$ – TheSimpliFire Jul 11 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.