# Tic-Tac-Toe

Last updated: 8th Sept, 2020

#### Problem Statement

A Tic-Tac-Toe board is given after some moves are played. Find out if the given board is valid, i.e., is it possible to reach this board position after some moves or not.
Note that every arbitrary filled grid of 9 spaces isn’t valid e.g. a grid filled with 3 X and 6 O isn’t valid situation because each player needs to take alternate turns.
Note : The game starts with X
Example 1:
2
X X O O X O O O O
X X O O O X X O X
>> Invalid
>> Valid
Example 2:
1
O X X X O X O O X
>> Invalid
>> Valid

Approach:

In this problem we check the validity of the given inputs of a tic-tac-toe game. The game involves two players 'X' and 'O' who take turns marking the spaces in a 3×3 grid. There are 8 strategies in order to win this game.
Consider player 'X', if 'X' occupies one of the row or one of the column or occupies the diagonals of grid then 'X' wins. If 'X' wins then the game ends which also applies to 'O'.
CONDITIONS TO CHECK IF INPUTS ARE INVALID:

- If both player 'X' and 'O' wins
- When 'O' takes a chance after 'X' wins or vice versa
- When number of 'X' exceed number of 'O' by two or more
- When number of 'O's are greater than 'X'

CHECKING THE VALIDITY:

- Number of 'X' exceeds number of 'O' if 'X' wins.
- Number of 'X' and 'O' equal only if 'O' wins.
- Number of 'X' exceed number of 'O' by 1 not greater than that.

POSSIBILITIES OF WINNING A GAME:

- 'X' occupies one of the row or 'O' occupies one of the row.
- 'X' occupies one of the column or 'O' occupies one of the column.
- 'X' occupies one of the diagonals in the grid or 'O' occupies one of the diagonals in the grid.

Complexity Analysis :

- Time Complexity- O(n^2)
- Space Complexity- O(n)

Pseudocode :
PROGRAM ticTacToe
// Possibilities() is a function to represent possible ways of winnning
INPUT: Read T, a
SET countX = 0
SET countY = 0
FOR each element in a
IF element = 0 THEN
INCREMENT countX
ELSE
INCREMENT countO
END IF
IF countO > countX or countX > countO + 1 THEN
PRINT Invalid
ELSE IF Possibilities(a, 'X') and Possibilities(a, 'O') THEN
PRINT Invalid
ELSE IF Possibilities(a, 'O') THEN
IF countX == countO THEN
PRINT Valid
ELSE
PRINT Invalid.
ELSE IF countO + 1 == countX or self.Possibilities(a, 'X') THEN
PRINT Valid
ELSE
PRINT Invalid
END IF
END FOR
END

###### Python Code

    class ticTacToe:

        def Possibilities(self, a, b):

            return ((a[0] == b and a[1] == b and a[2] == a[0]) or
                (a[3] == b and a[4] == b and a[5] == b) or
                (a[6] == b and a[7] == b and a[8] == b) or
                (a[0] == b and a[3] == b and a[6] == b) or
                (a[1] == b and a[4] == b and a[7] == b) or
                (a[2] == b and a[5] == b and a[8] == b) or
                (a[0] == b and a[4] == b and a[8] == b) or
                (a[2] == b and a[4] == b and a[6] == b))

        def validity(self, T):
            if 1 <= T <= 100:
                for i in range(T):
                    countX = 0
                    countO = 0
                    a = input().split()
                    for t in a:
                        if t == 'X':
                            countX += 1
                        else:
                            countO += 1
                    if countO > (countX) or (countX > countO + 1) :
                        print("Invalid")
                    elif self.Possibilities(a, 'X') and self.Possibilities(a, 'O'):
                        print("Invalid")
                    elif self.Possibilities(a, 'O'):
                        if countX == countO:
                            print('Valid')
                        else:
                            print("Invalid")
                    elif countO + 1 == countX or self.Possibilities(a, 'X'):
                        print("Valid")
                    else:
                        print("Invalid")

    chec = ticTacToe()
    chec.validity(int(input()))