# game combinations of tic-tac-toe

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

-
se16.info/hgb/tictactoe.htm –  Daryl Jan 2 '13 at 10:00
@Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer. –  Mark S. Nov 22 '13 at 3:42
@MarkS. Sure thing. –  Daryl Nov 22 '13 at 5:14

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.

-
Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72. –  Pieter Geerkens Nov 22 '13 at 5:32
As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$. –  Henry Jan 2 at 11:18