Game combinations of tic-tac-toe [closed]
How many combinations are possible in the game tic-tac-toe
(Noughts and crosses
)?
So for example a game which looked like: (with positions 1-9)
A1 -- B1
A2 -- B2
A3 -- --
[1][3][4][6][7] would be one combination
This information is taken from this website.
A naive estimate would be $9!=362\,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.
- Ending on the $5^\text{th}$ move: $1\,440$ possibilities
- Ending on the $6^\text{th}$ move: $5\,328$ possibilities
- Ending on the $7^\text{th}$ move: $47\,952$ possibilities
- Ending on the $8^\text{th}$ move: $72\,576$ possibilities
- Ending on the $9^\text{th}$ move: $127\,872$ possibilities
This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.
I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.
I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217
Cheers!