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:
Input:
board[] = {'X', 'X', 'O', 
           'O', 'O', 'X',
           'X', 'O', 'X'};
Output: Valid
Explanation: This is a valid board.
Example 2:
Input:
board[] = {'O', 'X', 'X', 
           'O', 'X', 'X',
           'O', 'O', 'X'};
Output: Invalid
Explanation: Both X and O cannot win.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isValid() which takes a character array of size 9 representing the board as input parameter and returns a boolean value denoting if it is valid or not.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
Every character on the board can either be 'X' or 'O'.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def isValid(self, board):

        # code here

Solutions:
class Solution:

	def isValid(self, board):
		if board[0] == board[1] and board[0] == board[2]:
			if board[0] == 'O':
				return False
		if board[3] == board[4] and board[3] == board[5]:
			if board[3] == 'O':
				return False
		if board[6] == board[7] and board[6] == board[8]:
			if board[6] == 'O':
				return False
		if board[0] == board[3] and board[0] == board[6]:
			if board[0] == 'O':
				return False
		if board[1] == board[4] and board[1] == board[7]:
			if board[1] == 'O':
				return False
		if board[2] == board[5] and board[2] == board[8]:
			if board[2] == 'O':
				return False
		if board[0] == board[4] and board[0] == board[8]:
			if board[0] == 'O':
				return False
		if board[2] == board[4] and board[2] == board[6]:
			if board[2] == 'O':
				return False
		count = board.count('X')
		return True if count == 5 else False


class Solution:

	def isValid(self, bb):
		board = [[0, 0, 0] for i in range(3)]
		j = 0
		board[0][0] = bb[0]
		board[0][1] = bb[1]
		board[0][2] = bb[2]
		board[1][0] = bb[3]
		board[1][1] = bb[4]
		board[1][2] = bb[5]
		board[2][0] = bb[6]
		board[2][1] = bb[7]
		board[2][2] = bb[8]
		c = [0, 0]
		for i in board:
			for j in i:
				if j == 'X':
					c[0] += 1
				else:
					c[1] += 1
		if c[0] != c[1] + 1 and c[0] != c[1]:
			return 0
		xwin = False
		owin = False
		for i in board:
			if i[0] == i[1] == i[2]:
				if i[0] == 'X':
					xwin = True
				else:
					owin = True
		for i in range(3):
			if board[0][i] == board[1][i] == board[2][i]:
				if board[0][i] == 'X':
					xwin = True
				else:
					owin = True
		if board[0][0] == board[1][1] == board[2][2]:
			if board[0][0] == 'X':
				xwin = True
			else:
				owin = True
		if board[0][2] == board[1][1] == board[2][0]:
			if board[1][1] == 'X':
				xwin = True
			else:
				owin = True
		if xwin and owin:
			return False
		if owin and c[0] != c[1]:
			return False
		if xwin and c[0] != c[1] + 1:
			return False
		return True


class Solution:

	def isValid(self, board):
		oo = False
		xx = True
		xcount = 0
		ycount = 0
		for i in range(9):
			if board[i] == 'X':
				xcount += 1
			if board[i] == 'O':
				ycount += 1
		if xcount - ycount != 1:
			return False
		win = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
		for i in range(8):
			if board[win[i][0]] == 'O' and board[win[i][1]] == 'O' and (board[win[i][2]] == 'O'):
				oo = True
			if board[win[i][0]] == 'X' and board[win[i][1]] == 'X' and (board[win[i][2]] == 'X'):
				xx = True
		if oo:
			return False
		return True


class Solution:

	def isValid(self, board):

		def _judge(a, b, c):
			nonlocal Xwin, Owin
			if a == b == c:
				if a == 'X':
					Xwin += 1
				else:
					Owin += 1
		(Xcnt, Ocnt, Xwin, Owin) = (0, 0, 0, 0)
		for c in board:
			if c == 'X':
				Xcnt += 1
			else:
				Ocnt += 1
		_judge(*board[0:3])
		_judge(*board[3:6])
		_judge(*board[6:9])
		_judge(*[board[i] for i in range(0, 9, 3)])
		_judge(*[board[i] for i in range(1, 9, 3)])
		_judge(*[board[i] for i in range(2, 9, 3)])
		_judge(*[board[0], board[4], board[8]])
		_judge(*[board[2], board[4], board[6]])
		if Xcnt != 5 or Ocnt != 4:
			return False
		if Owin > 0:
			return False
		return True


class Solution:

	def isValid(self, board):
		X = 0
		O = 0
		board1 = []
		board1.append(board[0:3])
		board1.append(board[3:6])
		board1.append(board[6:9])
		board = board1
		for i in range(0, 3):
			for j in range(0, 3):
				if board[i][j] == 'X':
					X += 1
				else:
					O += 1
		if X != O + 1:
			return 0
		flag_x = 0
		flag_o = 0
		for i in range(0, len(board)):
			count_x = 0
			count_o = 0
			for j in range(0, 3):
				(count_x, count_o) = self.count(board, i, j, count_x, count_o)
				if count_x > 0 and count_o > 0:
					break
			if count_x == 3:
				flag_x = 1
			if count_o == 3:
				flag_o = 1
			if flag_x == 1 and flag_o == 1:
				return 0
			count_x = 0
			count_o = 0
			for j in range(0, 3):
				(count_x, count_o) = self.count(board, j, i, count_x, count_o)
				if count_x > 0 and count_o > 0:
					break
			if count_x == 3:
				flag_x = 1
			if count_o == 3:
				flag_o = 1
			if flag_x == 1 and flag_o == 1:
				return 0
		if board[0][0] == 'X' and board[1][1] == 'X' and (board[2][2] == 'X') or (board[0][2] == 'X' and board[1][1] == 'X' and (board[2][0] == 'X')):
			flag_x = 1
		if board[0][0] == 'O' and board[1][1] == 'O' and (board[2][2] == 'O') or (board[0][2] == 'O' and board[1][1] == 'O' and (board[2][0] == 'O')):
			return 0
		return 1

	def count(self, arr, i, j, count_x, count_o):
		if arr[i][j] == 'X':
			count_x += 1
		if arr[i][j] == 'O':
			count_o += 1
		return (count_x, count_o)


class Solution:

	def isValid(self, board):

		def winCheck(mat, s):
			if mat[0][0] == s and mat[0][1] == s and (mat[0][2] == s):
				return True
			if mat[1][0] == s and mat[1][1] == s and (mat[1][2] == s):
				return True
			if mat[2][0] == s and mat[2][1] == s and (mat[2][2] == s):
				return True
			if mat[0][0] == s and mat[1][1] == s and (mat[2][2] == s):
				return True
			if mat[0][2] == s and mat[1][1] == s and (mat[2][0] == s):
				return True
			if mat[0][0] == s and mat[1][0] == s and (mat[2][0] == s):
				return True
			if mat[0][1] == s and mat[1][1] == s and (mat[2][1] == s):
				return True
			if mat[0][2] == s and mat[1][2] == s and (mat[2][2] == s):
				return True
			return False
		l = [[board[0], board[1], board[2]], [board[3], board[4], board[5]], [board[6], board[7], board[8]]]
		cO = 0
		cX = 0
		for i in range(len(l)):
			for j in range(len(l[i])):
				if l[i][j] == 'O':
					cO = cO + 1
				if l[i][j] == 'X':
					cX = cX + 1
		if cO >= cX:
			return False
		if winCheck(l, 'O') and winCheck(l, 'X') or abs(cX - cO) > 1:
			return False
		if winCheck(l, 'O') and cO != cX:
			return False
		return True


class Solution:

	def who_win(self, board, char):
		possible = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
		for i in range(8):
			if board[possible[i][0]] == char and board[possible[i][1]] == char and (board[possible[i][2]] == char):
				return True
		return False

	def isValid(self, board):
		countX = board.count('X')
		countO = board.count('O')
		if countX == countO or countX == countO + 1:
			if self.who_win(board, 'O'):
				if self.who_win(board, 'X'):
					return False
				if countX == countO:
					return True
			if self.who_win(board, 'X') and countX != countO + 1:
				return False
			if not self.who_win(board, 'O'):
				return True
		return False


class Solution:

	def isValid(self, board):
		co = 0
		cx = 0
		for i in range(9):
			if board[i] == 'X':
				cx += 1
			else:
				co += 1
		if cx - co != 1:
			return False
		if board[0] == board[1] and board[0] == board[2] and (board[0] == 'O'):
			return False
		if board[3] == board[4] and board[3] == board[5] and (board[3] == 'O'):
			return False
		if board[6] == board[7] and board[6] == board[8] and (board[6] == 'O'):
			return False
		if board[0] == board[3] and board[0] == board[6] and (board[0] == 'O'):
			return False
		if board[1] == board[4] and board[1] == board[7] and (board[1] == 'O'):
			return False
		if board[2] == board[5] and board[2] == board[8] and (board[2] == 'O'):
			return False
		if board[0] == board[4] and board[0] == board[8] and (board[0] == 'O'):
			return False
		if board[2] == board[4] and board[2] == board[6] and (board[2] == 'O'):
			return False
		return True


class Solution:

	def isValid(self, board):
		s = board
		board = [[0 for j in range(3)] for i in range(3)]
		k = 0
		for i in range(3):
			for j in range(3):
				board[i][j] = s[k]
				k += 1
		(co, cx) = (0, 0)
		owin = False
		xwin = False
		for row in board:
			t = row.count('O')
			if t == 0:
				xwin = True
			if t == 3:
				owin = True
			co += t
			cx += len(row) - t
		if co > cx:
			return False
		if cx > co + 1:
			return False
		for c in range(3):
			cnt = 0
			for r in range(3):
				cnt += 1 if board[r][c] == 'O' else 0
			if cnt == 0:
				xwin = True
			if cnt == 3:
				owin = True
		if board[0][0] == board[1][1] == board[2][2] == 'O' or board[0][2] == board[1][1] == board[2][0] == 'O':
			return False
		if owin:
			return False
		return True


class Solution:

	def isValid(self, board):
		s = board
		board = [[0 for j in range(3)] for i in range(3)]
		k = 0
		for i in range(3):
			for j in range(3):
				board[i][j] = s[k]
				k += 1
		(co, cx) = (0, 0)
		owin = False
		xwin = False
		for row in board:
			t = row.count('O')
			if t == 0:
				xwin = True
			if t == 3:
				owin = True
			co += t
			cx += len(row) - t
		if co > cx:
			return False
		if cx > co + 1:
			return False
		for c in range(3):
			cnt = 0
			for r in range(3):
				cnt += 1 if board[r][c] == 'O' else 0
			if cnt == 0:
				xwin = True
			if cnt == 3:
				owin = True
		if board[0][0] == board[1][1] == board[2][2] == 'O' or board[0][2] == board[1][1] == board[2][0] == 'O':
			return False
		if owin:
			return False
		return True
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		board = list(map(str, input().strip().split()))
		ob = Solution()
		ans = ob.isValid(board)
		if ans:
			print('Valid')
		else:
			print('Invalid')
		tc -= 1


class Solution:

	def isValid(self, board):
		board = [board[:3], board[3:6], board[6:]]

		def is_winner(player):
			for i in range(3):
				for j in range(3):
					if board[i][j] != player:
						break
				else:
					return True
			for i in range(3):
				for j in range(3):
					if board[j][i] != player:
						break
				else:
					return True
			for i in range(3):
				if board[i][2 - i] != player:
					break
			else:
				return True
			for i in range(3):
				if board[i][i] != player:
					break
			else:
				return True
			return False
		x_count = o_count = 0
		for i in range(3):
			for j in range(3):
				if board[i][j] == 'X':
					x_count += 1
				elif board[i][j] == 'O':
					o_count += 1
		if o_count > x_count or x_count - o_count > 1:
			return False
		x_win = is_winner('X')
		o_win = is_winner('O')
		if x_win and o_win:
			return False
		if o_win and x_count > o_count:
			return False
		return True
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		board = list(map(str, input().strip().split()))
		ob = Solution()
		ans = ob.isValid(board)
		if ans:
			print('Valid')
		else:
			print('Invalid')
		tc -= 1


class Solution:

	def isValid(self, box):

		def sea(a):
			for i in range(3):
				c = 0
				for j in range(3):
					if b[i][j] == a:
						c += 1
				if c == 3:
					return True
			for i in range(3):
				c = 0
				for j in range(3):
					if b[j][i] == a:
						c += 1
				if c == 3:
					return True
			(i, j) = (0, 2)
			c = 0
			while i < 3 and j > -1:
				if b[i][j] == a:
					c += 1
				i += 1
				j -= 1
			if c == 3:
				return True
			(i, j) = (0, 0)
			c = 0
			while i < 3 and j < 3:
				if b[i][j] == a:
					c += 1
				i += 1
				j += 1
			if c == 3:
				return True
			return False
		b = []
		q = 0
		for i in range(3):
			p = []
			for j in range(3):
				p.append(box[q])
				q += 1
			b.append(p)
		(o, x) = (0, 0)
		for i in b:
			for j in i:
				if j == 'X':
					x += 1
				else:
					o += 1
		if x != o and x != o + 1:
			return False
		k = sea('X')
		q = sea('O')
		if k and q:
			return False
		if k and x != o + 1:
			return False
		if q and o != x:
			return False
		return True


class Solution:

	def isValid(self, board):
		xc = board.count('X')
		oc = board.count('O')
		if xc - oc != 1:
			return False
		win = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
		ow = False
		xw = False
		for i in range(8):
			if board[win[i][0]] == 'O' and board[win[i][1]] == 'O' and (board[win[i][2]] == 'O'):
				ow = True
			if board[win[i][0]] == 'X' and board[win[i][1]] == 'X' and (board[win[i][2]] == 'X'):
				xw = True
		if ow:
			return False
		return True


class Solution:

	def winner(self, board, val):
		cd1 = 0
		cd2 = 0
		for i in range(3):
			cr = 0
			cc = 0
			for j in range(3):
				if board[i][j] == val:
					cr += 1
				if board[j][i] == val:
					cc += 1
				if i == j and board[i][j] == val:
					cd1 += 1
				if i + j == 2 and board[i][j] == val:
					cd2 += 1
			if cr == 3 or cc == 3 or cd1 == 3 or (cd2 == 3):
				return True
		return False

	def isValid(self, x):
		cx = 0
		co = 0
		board = []
		tot = []
		for i in range(9):
			if i > 0 and i % 3 == 0:
				board.append(tot)
				tot = []
			tot.append(x[i])
		board.append(tot)
		for i in range(3):
			for j in range(3):
				if board[i][j] == 'X':
					cx += 1
				elif board[i][j] == 'O':
					co += 1
		xwin = self.winner(board, 'X')
		owin = self.winner(board, 'O')
		if cx - co > 1 or co > cx:
			return False
		if owin:
			if not xwin and cx - co == 0:
				return True
			else:
				return False
		if xwin:
			if cx - co == 1:
				return True
			return False
		return True


win = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]

class Solution:

	def isValid(self, board):
		oo = False
		xx = True
		cnto = 0
		cntx = 0
		i = 0
		while i < 9:
			if board[i] == 'O':
				cnto += 1
			else:
				cntx += 1
			i += 1
		i = 0
		while i < 8:
			if board[win[i][0]] == 'O' and board[win[i][1]] == 'O' and (board[win[i][2]] == 'O'):
				oo = True
			if board[win[i][0]] == 'X' and board[win[i][1]] == 'X' and (board[win[i][2]] == 'X'):
				xx = True
			if oo == True or cntx - cnto != 1:
				return False
			i += 1
		return True


class Solution:

	def isValid(self, board):
		board = [[board[0], board[1], board[2]], [board[3], board[4], board[5]], [board[6], board[7], board[8]]]
		ocount = 0
		xcount = 0
		owon = 0
		xwon = 0
		mat = [[], [], []]
		for m in range(len(board)):
			if len(set(board[m])) == 1 and board[m][0] == 'X':
				xwon += 1
			elif len(set(board[m])) == 1 and board[m][0] == 'O':
				owon += 1
			arrthing = []
			for n in range(len(board)):
				if board[n][m] == 'X':
					xcount += 1
				else:
					ocount += 1
				arrthing.append(board[n][m])
			if len(set(arrthing)) == 1 and arrthing[0] == 'X':
				xwon += 1
			elif len(set(arrthing)) == 1 and arrthing[0] == 'O':
				owon += 1
		(arr1, arr2) = ([board[0][0], board[1][1], board[2][2]], [board[0][2], board[1][1], board[2][0]])
		if len(set(arr1)) == 1 and arr1[0] == 'X':
			xwon += 1
		elif len(set(arr1)) == 1 and arr1[0] == 'O':
			owon += 1
		if len(set(arr2)) == 1 and arr2[0] == 'X':
			xwon += 1
		elif len(set(arr2)) == 1 and arr2[0] == 'O':
			owon += 1
		if owon == 1 and (not xwon):
			if xcount - ocount == 0:
				return True
			else:
				return False
		if xcount - ocount == 0 or xcount - ocount == 1:
			if owon == 1 and (not xwon):
				return True
			elif owon == 2 and (not xwon):
				return True
			elif xwon == 1 and (not owon):
				return True
			elif xwon == 2 and (not owon):
				return True
			elif not xwon and (not owon):
				return True
			else:
				return False
		else:
			return False


class Solution:

	def isValid(self, mat):
		x = 0
		o = 0
		for i in range(9):
			if mat[i] == 'O':
				o += 1
			elif mat[i] == 'X':
				x += 1
		if x != o and x != o + 1:
			return False
		xx = True
		oo = False
		win = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
		for i in range(8):
			if board[win[i][0]] == 'O' and board[win[i][1]] == 'O' and (board[win[i][2]] == 'O'):
				oo = True
			if board[win[i][0]] == 'X' and board[win[i][1]] == 'X' and (board[win[i][2]] == 'X'):
				xx = True
		if oo:
			return False
		return True


class Solution:

	def isValid(self, board):
		Owin = False
		countx = 0
		counto = 0
		for i in range(len(board)):
			if board[i] == 'X':
				countx += 1
			if board[i] == 'O':
				counto += 1
		if counto + 1 != countx:
			return False
		wincount = 0
		if board[0] == board[1] and board[1] == board[2]:
			if board[0] == 'O':
				Owin = True
		if board[3] == board[4] and board[4] == board[5]:
			if board[3] == 'O':
				Owin = True
		if board[6] == board[7] and board[7] == board[8]:
			if board[6] == 'O':
				Owin = True
		if board[0] == board[3] and board[3] == board[6]:
			if board[0] == 'O':
				Owin = True
		if board[1] == board[4] and board[4] == board[7]:
			if board[1] == 'O':
				Owin = True
		if board[2] == board[5] and board[5] == board[8]:
			if board[2] == 'O':
				Owin = True
		if board[0] == board[4] and board[4] == board[8]:
			if board[0] == 'O':
				Owin = True
		if board[2] == board[4] and board[4] == board[6]:
			if board[2] == 'O':
				Owin = True
		if Owin:
			return False
		return True


class Solution:

	def isValid(self, board):
		i = 0
		cntX = 0
		cntO = 0
		for i in range(9):
			if board[i] == 'X':
				cntX += 1
			else:
				cntO += 1
		if cntO < 4 or cntX < 5:
			return False
		cntX = 0
		cntO = 0
		for i in range(3):
			if board[i] == board[i + 3] == board[i + 6] == 'X':
				cntX += 1
			elif board[i] == board[i + 3] == board[i + 6] == 'O':
				cntO += 1
		for i in range(0, 9, 3):
			if board[i] == board[i + 1] == board[i + 2] == 'X':
				cntX += 1
			elif board[i] == board[i + 1] == board[i + 2] == 'O':
				cntO += 1
		if board[0] == board[4] == board[8] == 'X' or board[2] == board[4] == board[6] == 'X':
			cntX += 1
		elif board[0] == board[4] == board[8] == 'O' or board[2] == board[4] == board[6] == 'O':
			cntO += 1
		if cntX != cntO and cntX > 0:
			return True
		elif cntX == cntO == 0:
			return True
		return False


class Solution:

	def isValid(self, board):
		from collections import Counter
		counter = Counter(board)
		if counter['X'] < 5 or abs(counter['X'] - counter['O']) > 1:
			return False
		x_win = o_win = False
		for i in range(3):
			if board[i] == board[i + 3] == board[i + 6]:
				if board[i] == 'X':
					x_win = True
				else:
					o_win = True
		for i in [0, 3, 6]:
			if board[i] == board[i + 1] == board[i + 2]:
				if board[i] == 'X':
					x_win = True
				else:
					o_win = True
		if board[0] == board[4] == board[8] or board[2] == board[4] == board[6]:
			if board[4] == 'X':
				x_win = True
			else:
				o_win = True
		if o_win and counter['X'] > counter['O']:
			return False
		if x_win and o_win:
			return False
		return True


class Solution:

	def win_check(self, arr, char):
		matches = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
		for i in range(8):
			if arr[matches[i][0]] == char and arr[matches[i][1]] == char and (arr[matches[i][2]] == char):
				return True
		return False

	def isValid(self, arr):
		xcount = 0
		ocount = 0
		for i in range(9):
			if arr[i] == 'X':
				xcount += 1
			if arr[i] == 'O':
				ocount += 1
		if abs(xcount - ocount) > 1:
			return False
		if xcount == ocount + 1 or xcount == ocount:
			if self.win_check(arr, 'O'):
				if self.win_check(arr, 'X'):
					return False
				if xcount == ocount:
					return True
			if self.win_check(arr, 'X') and xcount != ocount + 1:
				return False
			if not self.win_check(arr, 'O'):
				return True
		return False