10363 - Tic Tac Toe

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by soyoja » Tue Sep 24, 2002 12:54 pm

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?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Tue Sep 24, 2002 1:09 pm

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

Post by .. » Tue Sep 24, 2002 3:55 pm

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.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Tue Sep 24, 2002 4:22 pm

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

Post by arc16 » Tue Sep 24, 2002 4:45 pm

.. 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 :)

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

Tic Tac Toe confusing

Post by Ghost77 dimen » Wed Sep 25, 2002 10:20 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 25, 2002 1:41 pm

"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

Post by mido » Wed Sep 25, 2002 4:24 pm

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.

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

Thanks.

Post by Ghost77 dimen » Wed Sep 25, 2002 4:57 pm

Tkanks for your helpful advise.mido.

I solve this problem during 0.00 second.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Wed Sep 25, 2002 5:05 pm

Thank you Mido.
You have given good hints. :D

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Wed Sep 25, 2002 5:13 pm

Thank you Mido.
You have given good hints. :D

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

Post by soyoja » Fri Sep 27, 2002 9:54 am

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

Post by mido » Fri Sep 27, 2002 2:30 pm

You're very welcom..:)

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Tue Dec 17, 2002 8:00 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
Location: Dhaka,Bangladesh
Contact:

Post by Rajputro » Sun Aug 10, 2003 9:22 pm

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

" Rajputro has spoken. "

Post Reply

Return to “Volume 103 (10300-10399)”