All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Tic Tac Toe (Posted on 2002-09-27)
A computer science teacher poses his students a problem.

"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)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 4 of 12 |
If the problem refers to in-play configurations, at any point of play a square may have one of three values: X, O, blank. Having 9 squares, the number of board configurations is then 3^9 = 19683 possible arrangements.

The actual number is significantly less than that, since the problem requires the configurations to be valid; eg. a configuration with X's in all 9 squares is invalid. So the answer must be much less than 344,242.

If the problem refers to end-game configurations, then there are fewer than 2^9 = 512 configurations. And with respect to friedlinguini's comment, this solution doesn't even address symmetry, which further reduces the number of unique valid combinations.
 Posted by Jacob Fugal on 2002-09-28 08:21:43

 Search: Search body:
Forums (0)