Page 1 of 4

10363 - Tic Tac Toe

Posted: Tue Sep 24, 2002 12:54 pm
by soyoja
I don't know about this problem.

I think that I check only current tic-tac-toe status, and

if current status is correct ( i.e number of 'O' is equal or

one less than 'X' . if X is win then number of O is one less

than X, etc. ) then I print "yes".

But I receive "wrong answer". I'm really want to know about

solution. Anyone give me some hints?

Posted: Tue Sep 24, 2002 1:09 pm
by Ivan Golubev
Generate all possible states with BFS and compare with your current solution.

Posted: Tue Sep 24, 2002 3:55 pm
by ..
At first I try to use the condition to check, but failed.
But after reading your post, I find what condition I missed.

Here is the condition I check:
The numebr of X and O
no 2 people win same time
If anyone win at 2 different rows(columns) same time
If anyone win, check with the number of both sides.

Posted: Tue Sep 24, 2002 4:22 pm
by Yarin
An analytic solution can be made a bit simplier than that:

* Calc number of X, and O's and abort if invalid count
* If anyone has three-in-a-row, make sure it's possible to remove an X (or O, depending on who made the last move), so that there will no longer be any three-in-a-row on the board

Posted: Tue Sep 24, 2002 4:45 pm
by arc16
.. wrote: If anyone win at 2 different rows(columns) same time
i think we should not worry about that, at least my solution doesn't :)

Tic Tac Toe confusing

Posted: Wed Sep 25, 2002 10:20 am
by Ghost77 dimen
[color=red]
One line of the problem's context is as follows:
Whenever X or O plays we fill in an X or an O in the "appropriate" position.

What is the word,"appropriate",means?
Is unoccupied or best way to win?

In such situation,what should be printed in the follow input case?
XOX
OXO
XOX
[/color]

Posted: Wed Sep 25, 2002 1:41 pm
by Adrian Kuegel
"For each case print "yes" or "no" on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game."
I think that this means that not all moves has to be optimal, only each move has to be valid.
If you count the number of "X" and "O", it is sufficient to check if there is one winning position for "X" or for "O". It is only possible for "X" to have two winning positions like:
XXX
XOO
XOO
In these cases one can assume that the last "X" is placed at the position where the two rows/columns/diagonals intersect.

Posted: Wed Sep 25, 2002 4:24 pm
by mido
Semi-Spoiler:

What should be the status of the board if :

If x wins.
If o wins.
If neither win.
If both win???...can't happen..:)

Think and good luck.

Thanks.

Posted: Wed Sep 25, 2002 4:57 pm
by Ghost77 dimen
Tkanks for your helpful advise.mido.

I solve this problem during 0.00 second.

Posted: Wed Sep 25, 2002 5:05 pm
by henar2
Thank you Mido.
You have given good hints. :D

Posted: Wed Sep 25, 2002 5:13 pm
by henar2
Thank you Mido.
You have given good hints. :D

Posted: Fri Sep 27, 2002 9:54 am
by soyoja
Anyway, I finally know the solution.

In this problem, there are some obvious keys.

1) All of the input case is 3*3, consist of valid character.

2) So we should check whether current input status is valid or not.

3) Therefore, we count current number of O and X, and check

if O is win or X is win. ( As above article said that if current game

status is last one, then X can doubled in a row status. )

4) If current status is not last one, then O is equal or one less than

number of X.

So we should only
i)count X and O's number
ii) X is win or O is win.

It's sufficient to solve this poroblem.

Posted: Fri Sep 27, 2002 2:30 pm
by mido
You're very welcom..:)

Posted: Tue Dec 17, 2002 8:00 pm
by deddy one
What I do is just like this

1. count the number of valid O and X overall
2. count the number of valid O and X if O win
3. count the number of valid O and X if X win
4. count the number of valid O and X if neither win

and it's accepted, but PE, I'm confused , where should I put the extra
blank line in this problem??????

Posted: Sun Aug 10, 2003 9:22 pm
by Rajputro
What is valid O/X?

Can there be invalid inputs?? :o

I've got w/a . :( :(
Does X always starts?
Need some critical inputs.
Thank you.