# Tic-Tac-Toe coding

Here is a mathematical problem
can anybody write code to it in C/C++/JAVA/PYTHON

In a game of Tic Tac Toe
we call equivalent boards which may be obtained from other board by
rotating or flipping
a) how many non-equivalent boards are there
b) in a) if 3βXβ and 3βOβ are there
c) in a) if we count regardless that one has won the game i.e. we have
to fill all boxes.
In part a) you have to consider that you cannot fill more boxes after the
the game has a winner

1 Like

Iβm assuming you know basic group theory, because your question is a basic application of group theory.

Consider a group G containing all reflections and rotations, and a set X containing all possible configurations of the table with not more than one row, column or diagonal having all elements the same. Then the number of configurations is the number of orbits in the board. We can calculate orbits using |O| = \frac{\sum_{g\in G} |X^g|}{|G|} where |X^g| is the number of fixed elements of g.

You can generate all 3^9 possible configurations and check if they satisfy the condition to be in set X. This will take ~3^{11} calculations. For each valid configuration, Make every group act on it to check whether itβs equal to itself. You will have 8 possibilities of rotations and reflections. Checking will take ~8\times 3^{11} more time, which you can do easily.

1 Like

can anyone please tell me why i am getting WA

#include
using namespace std;
int wins(char board[][3],char ch)
{
if(board[0][0]==ch&&board[0][0]==board[0][1]&&board[0][1]==board[0][2])
return 1;
else if(board[0][0]==ch&&board[0][0]==board[1][0]&&board[1][0]==board[2][0])
return 1;
else if(board[0][0]==ch&&board[0][0]==board[1][1]&&board[1][1]==board[2][2])
return 1;
else if(board[0][2]==ch&&board[0][2]==board[1][1]&&board[1][1]==board[2][0])
return 1;
else if(board[1][0]==ch&&board[1][0]==board[1][1]&&board[1][1]==board[1][2])
return 1;
else if(board[2][0]==ch&&board[2][0]==board[2][1]&&board[2][1]==board[2][2])
return 1;
else if(board[0][1]==ch&&board[0][1]==board[1][1]&&board[1][1]==board[2][1])
return 1;
else if(board[0][2]==ch&&board[0][2]==board[1][2]&&board[1][2]==board[2][2])
return 1;
else
return 0;
}
int main()
{
int t;
cin>>t;
while(tβ)
{
char mat[3][3];
int x=0,o=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cin>>mat[i][j];
if(mat[i][j]==βXβ)
x++;
else if(mat[i][j]==βOβ)
o++;
}
}
if(x==o||x==o+1)
{
int xx=wins(mat,βXβ);
int oo=wins(mat,βOβ);
if(xx&&oo)
{
cout<<β3β<<endl;
}
else if(xx)
{ if(x==o+1)
cout<<β1β<<endl;
else
cout<<β3β<<endl;
}
else if(oo)
{
if(x==o)
cout<<β1β<<endl;
else
cout<<β3β<<endl;
}
else
{ if(xx+oo==9)
cout<<β1β<<endl;
else
cout<<β2β<<endl;
}

    }
else
{
cout<<"3"<<endl;
}
}


}