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.)
 another method | Comment 11 of 12 |
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
 Posted by Dan Porter on 2004-01-15 04:45:03

 Search: Search body:
Forums (0)