Implement Ultimate Tic-Tac-Toe

Problem Statement

Design a system to represent and play "Ultimate Tic-Tac-Toe." The board consists of a 3x3 grid of standard 3x3 Tic-Tac-Toe boards (a total of 9 boards, with 81 cells).

Rules:

1. Players take turns placing their mark (X or O) in an empty cell.
2. A move in a cell of a local 3x3 board determines which local board the next player must play in (e.g., if you play in the top-right cell of any local board, the next player must play somewhere in the top-right local board of the overall 9x9 grid).
3. If the target local board is already full or won, the next player can move in any available cell in any incomplete board.
4. A local board is won by getting three in a row (horizontally, vertically, or diagonally). Once a local board is won, it is treated as a single cell for the overall game grid.
5. The overall game is won by winning three local boards in a row (horizontally, vertically, or diagonally) on the 3x3 meta-grid.

Implement a class UltimateTicTacToe that supports the following interface:

class UltimateTicTacToe:
    def __init__(self):
        # Initialize board state

    def make_move(self, board_idx, cell_idx):
        """
        board_idx: 0-8 (representing the 3x3 grid of local boards)
        cell_idx: 0-8 (representing the 3x3 grid within a local board)
        Returns: True if move was valid, False otherwise.
        """
        pass

    def check_winner(self):
        """
        Returns: 'X', 'O', 'Draw', or None if the game is ongoing.
        """
        pass

Constraints

• board_idx and cell_idx are integers 0-8.
• The game must handle invalid moves (e.g., playing in the wrong board, playing in an occupied cell).

Example

• If player X moves in board_idx=0, cell_idx=4 (center of top-left board), the next move must be in board_idx=4 (the center local board).
• If the center board is already won, the player can choose any board.