python compute all of them
emulate a game starting from empty board, \n\n1. at each round, put an x where we can (or a o if its o\'s turn)\n2. avoid cycle and keep track of where we have 
emulate a game starting from empty board, \n\n1. at each round, put an x where we can (or a o if its o\'s turn)\n2. avoid cycle and keep track of where we have been in a hashset **vis**\n3. hash the board a list of string into the unique string concatenated ```[\'oxo\' , \'   \', \' ox\']``` is represented by ```\'oxo\' +\'   \'+ \' ox\'```\n4. stop recursing (dfsing) if someone won\n5. final answer : original board in vis\n7. upper bound is a **3 ^ 9 == 19683** (3 options for each of the 9 cells)\n6. compute the hashset once and do a lookup once its been computed\n\npseudo code\n```\nvis = set([])\n\ndfs(u, b):\n\tb is a bool that tells me whos turn it is\n\tif won(u):\n\t\tif someone won return\n\tfor v in adj[u]:\n\t\tif v not in vis:\n\t\t\tvis.add(v)\n\t\t\tdfs(v, not(b))\n```\ncode\n\nvis is global to be reused accross test cases\n\n```\nvis = set([])\nclass Solution(object):\n    def validTicTacToe(self, board):\n        if not(vis):\n            vis.add(\' \'* 9)\n            self.dfs(\' \' * 9, True)\n        return reduce(lambda x,y: x+y, board) in vis\n    \n    def dfs(self, u, b):\n        if self.won(u, (\'O\' if b else \'X\')): \n            return\n        for v in [u[:i] + (\'X\' if b else \'O\') + u[i+1:] for i in range(len(u)) if u[i] == \' \']:\n            if v not in vis:\n                vis.add(v)\n                self.dfs(v, not(b))\n    \n    def won(self, s, letter):\n        if s[0] + s[1] + s[2] == letter * 3: return True\n        if s[3] + s[4] + s[5] == letter * 3: return True\n        if s[6] + s[7] + s[8] == letter * 3: return True\n        \n        if s[2] + s[5] + s[8] == letter * 3: return True\n        if s[1] + s[4] + s[7] == letter * 3: return True\n        if s[0] + s[3] + s[6] == letter * 3: return True\n        \n        if s[0] + s[4] + s[8] == letter * 3: return True\n        if s[2] + s[4] + s[6] == letter * 3: return True\n        return False\n        \n```\n\n1. 5478 different boards out of 3 ^ 9 (about 1/4)\n1. once computed its the cost of a lookup in a (small) hashset: O(1) amortized\n1. or even a the cost of binary searching a  sorted list if I sort the possible boards within a list: ( log(5000) wihich is about 13)\n\n\nkind of a fun way (relatively fun but not as fun as the masked singer damn the last episode was so good with vic oladipo, what a singer)\n\n\nother wise, count the x\'s , count the o\'s \nand consider all cases \n1. either x won \n1. either draw\n1. either o won \n\n```\nclass Solution(object):\n    def validTicTacToe(self, board):\n        cc = collections.Counter([e for l in board for e in l])        \n        if cc[\'O\'] not in set([cc[\'X\'],cc[\'X\']-1]): return False\n        state= (self.f(board,\'X\'), self.f(board,\'O\'))\n        if state[0] > state[1]: return cc[\'X\'] == cc[\'O\'] + 1\n        elif state[0] == state[1]: return state == (0,0)\n        elif state[0] < state[1]: return cc[\'X\'] == cc[\'O\']\n            \n    def f(self, board, letter):\n        target = [letter] * 3\n        count = 0\n        for l in board:\n            l = list(l)\n            if l == target: count += 1\n        for c in range(3):\n            l = [board[i][c] for i in range(3)]\n            if l == target: count += 1\n                \n        l = [board[0][0], board[1][1], board[2][2]]\n        if l == target: count += 1\n        l = [board[0][2], board[1][1], board[2][0]]\n        if l == target: count += 1\n        return count\n```
[]