@VIctor.. It does not matter that we have final state or not we need to check with every input from users..and probably the check function gonna check on 8 places ...

I just got this question and it occurs to me this is a simple iteration of flood fill. X being one color, O being another. Visit each node, get its neighbors, put them on the neighbor stack. Go DFS and arbitrarily id go left to right...each time throwing neighbors into a stack. Put each node with its resultant x or o as data in a visited array. Go to the stack and pop off the first, get its data and check for neighbors, if they aren't on the stack put them on the stack. This will operate roughly Log(n) run time, as you won't iterate through the entire stack to find a win condition..

Tic-Tac-Toe is game like soduku or checkers that is represented as having columns and rows which translates as a 2 Dimensional array. In this case a 3x3 array. Represented as [0][0] [1][0] [2][0] You would therefore permutate each possibility. .... ..... ...... ...... ..... ..... [2][2]

It's all about state. You can only win on the placement of a token so check the possible ways to win from this position. So say the user places a value in the bottom left corner. Then you need only check the vertical, horizontal and the diagonal from this position. From the center position you will need to check 4 different positions (+ and x). This retains a O(1) solution but then again this only works if you can keep count of how many moves have already occurred.