Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.