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.

Posted: **Wed Sep 25, 2002 5:13 pm**

by **henar2**

Thank you Mido.

You have given good hints.

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??

I've got w/a .

Does X always starts?

Need some critical inputs.

Thank you.