Count Legal Tic-Tac-Toe Games from the Empty Board
Company: Decagon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Legal Tic-Tac-Toe Games from the Empty Board
Start with an empty 3-by-3 Tic-Tac-Toe board. `X` always moves first, and the players alternate placing a mark in an empty square. A game ends immediately when either player completes a row, column, or diagonal of three marks, or when the board becomes full.
Count the total number of legal game sequences. Different move orders count as different games even when they produce the same final board.
## Function Signature
```python
def count_tic_tac_toe_games() -> int:
```
## Input
The function takes no arguments. Every game begins from the empty board with `X` to move.
## Output
Return the total number of distinct legal move sequences from the empty board through immediate game termination.
## Constraints
- The board is fixed at 3 by 3.
- A move may choose any currently empty square.
- Turns alternate `X`, `O`, `X`, `O`, and so on.
- Do not continue a sequence after its first win or after the board is full.
- Derive the count from the legal game process rather than returning a hard-coded constant.
- The result is at most `9!`, so it is exactly representable in every supported language.
Quick Answer: Count every legal Tic-Tac-Toe game sequence from an empty board, treating different move orders as distinct and stopping immediately at the first win or a full board. Practice exhaustive state exploration, correct turn alternation, terminal-state detection, backtracking, and deriving the result rather than hard-coding it.