Tic-Tac-Toe Game

This is not a question, but my solution to the problem.
I see there are eight possible solutions that must be tested.
This means, during each round all eight must be tested for each player,
which is 16 test per round.
I thought about Allan Touring, he had an overwhelming number of solution to test, one day he realized it need not test every one.

So, I realized there are three possible symbols any square can have. The 'O', the 'X', or 'Empty.' I also realized, it takes three marks to be a winner, if there is no winner:
- there cannot be any loser.
- As long as one space remains, it is not possible to be a draw if that space could lead to a win.

Knowing this I decided, until the player had three turns there is no reason to test for a win - - it is not possible because of the fact it takes three in a row.

I also realized I can eliminate test from the eight by testing for "Empty" spaces. So I began ::
if space 0,0 is empty I eliminate three possibilities from the eight - leaving only five.
If space 1,1 is empty I eliminate two more - leaving only three that could lead to a win.
If space 2,2 is empty also then there is no possible win.


I could test the three squares of any diagonal to determine if a win is possible. This must be faster than testing eight possible wins.

Also, if any of the three is occupied then I would test the possibilities associated to that particular space.
But no test needs to be done until the player had placed three marks on the board.


Like I said, this is only my thoughts on how I am approaching this problem.

Comments & thoughts are welcome.
Last edited on
yes, you are thinking correctly.
except, empty should be "side being checked" … if you are checking X, then the test you want is if space 0,0 is not x. If checking O, same thing for O. Empty or other side's value both. Unless you are checking for any win both sides at once?

another way to do it efficiently is to 'remember' the board every time a player takes a turn. You can keep track of what changed leading to a list of where a win could be and keeping that list very short. I mean if play is upper left X, lower left O, lower right X (the only win possible next turn for X is center) … no need to check anything else for X... O plays middle to block and X can't win next turn, O can win on upper diagonal... still only 1 thing to watch...

Hey !! I love that idea ... I'm gonna use that too ...
Thanks a Bunch !!
Topic archived. No new replies allowed.