## 10363 - Tic Tac Toe

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10363 - Tic Tac Toe

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".

solution. Anyone give me some hints?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Generate all possible states with BFS and compare with your current solution.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
At first I try to use the condition to check, but failed.

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.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
.. 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

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### Tic Tac Toe confusing

[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]

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
"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.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
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.

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### Thanks.

I solve this problem during 0.00 second.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Thank you Mido.
You have given good hints.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Thank you Mido.
You have given good hints.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
You're very welcom..

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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??????

Rajputro
New poster
Posts: 6
Joined: Fri Jan 10, 2003 4:19 pm