If I have board of size n x n in tic tac toe and I have used one field to put cross there like below
| | | |
--------
| | | |
--------
| | | |
--------
| | |X|
How many possible boards are in this game -> I mean to every possible end of this game.
For instance in next move there is 15 possible boards in the next move there is 14 but they derive from those 15 boards, so is it $n!$ possible boards where $n$ is number of empty fields?
Game ends where: boards is full or there is n same figures in one line.
Edit2: If it is to hard can we estimate the order of magnitude? Limit from below and above(small o big O notation)?
Edit3 Estimation from above would be calculating all game states if we end the game when the board is full.
Best Answer
There's a total of $n^2$ places to fill. If cross starts then the number of crosses is $\tfrac{1}{2}n^2$ if $n$ is even, or $\frac{1}{2}(n^2+1)$ if $n$ is odd. The rest are circles, so the number of filled boards is $$\frac{(n^2)!}{\left(\left(\tfrac{n^2}{2}\right)!\right)^2}\qquad\text{or}\qquad\frac{(n^2)!}{\left(\frac{n^2-1}{2}\right)!\left(\frac{n^2+1}{2}\right)!},$$ depending on whether $n$ is even or odd. This is not a very sharp upper bound.
On the other hand, for a game to finish, cross must make at least $n$ moves, and hence circle must make at least $n-1$ moves. The number of ways to do so is $$\frac{(n^2)!}{n!(n-1)!(n-1)^2!},$$ so there are at least this many distinct ways to end, and this is not a very sharp lower bound.