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)

I started by looking for the number of winning games at the fith move.

There are 8 way to win. 3 vertical, 3 horizontal and 2 diaganal.

There are 6 ways to place 3 objexts in a row. 123, 132, 213, 231, 312, 321

6*8=48 combonations for the first player.

The second player placed 2 objects in 6 possible locations for 6*5=30 combotaions.

Total winnig combos after 5 moves is 48*30=1440.

This by the way is the same as the actual count by Jim Lyon. I'm guessing he coded correctly.

By removing just these winning combos you get a number less than 344242.

(9*8*7*6*5-1440)*4*3*2+1440=329760

*Edited on ***January 15, 2004, 4:52 am**
*Edited on ***January 15, 2004, 5:11 am**