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

Home > Games
Tic Tac Toe (Posted on 2002-09-27) Difficulty: 3 of 5
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)

See The Solution Submitted by Cheradenine    
Rating: 3.5455 (11 votes)

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information