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