[Python] When in doubt - play it out
This solution uses a Tic-Tac-Toe game class to simulate the game play.\nA recursive helper function is used to test all possible play scenarios for the given \'
This solution uses a Tic-Tac-Toe game class to simulate the game play.\nA recursive helper function is used to test all possible play scenarios for the given \'X\' and \'O\' plays.  \n\nIf we can play all \'X\' and \'O\' without \'X\' or \'O\' winning before the last move, then board is a valid input.  \n\nObviously simulation is not the most efficient approach to this problem, but it is a fun challenge.  \nIf you also solved this using simulation, share your solution in the comments below.  \n\n```python\nclass Tic_Tac_Toe(object):\n    def __init__(self, rows = None, cols = None, diag = None, total_plays = None):\n        \'\'\'\n        if no input is given: initiate the game as an empty board\n        if an input is given: initiate the game according to the input\n        \'\'\'\n        self.rows = [[] for _ in range(3)] if rows is None else rows\n        self.cols = [[] for _ in range(3)] if cols is None else cols\n        self.diag = [[] for _ in range(2)] if diag is None else diag\n        self.total_plays = 0 if total_plays is None else total_plays\n    \n    def play(self, val, i, j):\n        \'\'\'place val (\'X\' or \'O\') at location (i, j)\'\'\'\n        self.rows[i].append(val)\n        self.cols[j].append(val)\n        \n        if i == j == 1:\n            self.diag[0].append(val)\n            self.diag[1].append(val)\n        elif (i,j) in [(0, 0), (2, 2)]:\n            self.diag[0].append(val)\n        elif (i,j) in [(2, 0), (0, 2)]:\n            self.diag[1].append(val)\n            \n        self.total_plays += 1\n    \n    def has_won(self):\n        \'\'\'returns true if \'X\' or \'O\' has won\'\'\'\n        return any((len(line) == 3) and (len(set(line)) == 1) for line in self.rows + self.cols + self.diag)\n    \n    def __repr__(self):\n        \'\'\'return a dictionary of the current game-state so that a deep copy of the game can be made\'\'\'\n        return {\'rows\': [r.copy() for r in self.rows], \n                \'cols\': [c.copy() for c in self.cols],\n                \'diag\': [d.copy() for d in self.diag],\n                \'total_plays\': self.total_plays}\n    \n    def print_game(self):\n        for row in self.rows: print(row)\n            \nclass Solution:\n    def validTicTacToe(self, board: List[str]) -> bool:\n        \n        x_plays = [(i,j) for i in range(3) for j in range(3) if board[i][j] == \'X\']\n        o_plays = [(i,j) for i in range(3) for j in range(3) if board[i][j] == \'O\']\n        \n        # 1. Check if X or O played too many times\n        x_count, o_count = len(x_plays), len(o_plays)\n        if x_count > o_count + 1 or o_count > x_count:\n            return False\n        \n        # 2. Simulate all possible games\n        def helper(game, turn, x_plays, o_plays):\n            nonlocal x_count, o_count, res\n\n            # All plays have been made: solution found!\n            if game.total_plays == x_count + o_count: res = True\n            \n            # \'X\' or \'O\' won but not all plays were made, solution not found\n            if game.has_won(): return None\n            \n            # A solution has already been found, exit the recursive function\n            if res: return None\n            \n            # Try all possible remaining moves\n            if turn == \'X\':\n                for i,(row,col) in enumerate(x_plays):\n                    g = Tic_Tac_Toe(**game.__repr__())\n                    g.play(\'X\', row, col)\n                    helper(g, \'O\', x_plays[:i] + x_plays[i+1:], o_plays)\n            else:\n                for i,(row,col) in enumerate(o_plays):\n                    g = Tic_Tac_Toe(**game.__repr__())\n                    g.play(\'O\', row, col)\n                    helper(g, \'X\', x_plays, o_plays[:i] + o_plays[i+1:])\n        \n        res = False\n        helper(Tic_Tac_Toe(), \'X\', x_plays, o_plays)\n        return res\n```
[]