Is the aim of this Tic-Tac-Toe puzzle possible to achieve?
Solution 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
- Turn the upper right corner clockwise
- Then the lower left corner clockwise
- Turn the upper right corner counterclockwise
- 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:
- Lower left clockwise
- Lower right counterclockwise
- Lower left counterclockwise
- 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.
Solution 2:
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}.$
Solution 3:
$$ \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.