"I want you write a computer program that plays tic-tac-toe legally and runs through ALL the possible combinations of the game, and finds out the total."

The students settle down to work..

An hour later, a student gets up and proclaims "I've got it! The number of possible combinations in a game is 344,242."

At which point another student quickly replies, "I haven't finished yet, but I'm sure Fred made a mistake in his program."

Why?

(Tic Tac Toe = Noughts and Crosses)

That (symmetry) was my first thought, too. And it's not just 4-way symmetry (rotation), but it's 8-way symmetry, because you can use reflection too.

However, consider a game that ends with X's at all 4 corners and the center, and O's on all 4 edges.
This game is invariant through rotation and reflection. It counts only once, not 8 times.

Posted by Jim Lyon on 2002-09-27 13:13:38