Count Legal Tic-Tac-Toe Games from the Empty Board

Problem Statement

In standard Tic-Tac-Toe, two players ('X' and 'O') alternate turns marking an empty cell on a 3x3 grid. Player 'X' always plays first.

A game sequence is an ordered list of moves: [move_1, move_2, ..., move_k]. A game sequence terminates immediately when:

1. A player gets three of their marks in a row (horizontally, vertically, or diagonally), resulting in a win for that player.
2. All 9 cells are filled without any player winning, resulting in a draw.

Two game sequences are considered distinct if the sequence of moves differs at any turn, even if they result in the identical final board configuration. No moves may be made after a game terminates.

Write a function count_tic_tac_toe_games(board: list[list[str]] | None = None, turn: str = 'X') -> dict[str, int] that computes the total number of distinct completed game sequences from the given board state, broken down by outcome.

If board is None, start from an empty 3x3 board where 'X' moves first.

Your function should return a dictionary with the following keys:

• 'X': Total number of distinct game paths won by 'X'
• 'O': Total number of distinct game paths won by 'O'
• 'Draw': Total number of distinct game paths ending in a draw
• 'Total': The sum of all completed game paths ('X' + 'O' + 'Draw')

Note: Your solution must algorithmically compute the values via traversal; hardcoded values will not be accepted.

Function Signature

def count_tic_tac_toe_games(
    board: list[list[str]] | None = None,
    turn: str = "X"
) -> dict[str, int]:
    pass

Inputs

• board: A 3x3 grid represented as a list of lists containing 'X', 'O', or '.' (representing an empty cell). If None, defaults to a 3x3 grid of '.'. It is guaranteed that the provided board represents a valid, non-terminal state.
• turn: A string ('X' or 'O') indicating which player moves next. Defaults to 'X'.

Output

• A dictionary with keys 'X', 'O', 'Draw', and 'Total', each mapped to an integer count.

Examples

Example 1

result = count_tic_tac_toe_games()
print(result)
# Output:
# {
#     'X': 131184,
#     'O': 77904,
#     'Draw': 46080,
#     'Total': 255168
# }

Example 2

partial_board = [
    ['X', 'O', 'X'],
    ['X', 'O', 'O'],
    ['.', '.', '.']
]
# It is X's turn, with empty cells at (2,0), (2,1), (2,2)
result = count_tic_tac_toe_games(board=partial_board, turn='X')
print(result)
# Output:
# {
#     'X': 4,
#     'O': 1,
#     'Draw': 1,
#     'Total': 6
# }

Explanation for Example 2:

• If X plays (2, 0), X wins immediately (left column X, X, X). (1 game for X)
• If X plays (2, 2), X wins immediately (diagonal (0,0), (1,1), (2,2) is X, O, . - wait, checking columns: col 2 is X, O, X? No win. Let's trace all remaining 3! = 6 permutations: X gets 4 wins, O gets 1, and 1 ends in a draw. Total = 6 games.

Constraints

• The board is always 3x3.
• The function must execute within 2.0 seconds for the empty board.