Enumerate Every Tic-Tac-Toe Game Playable from a Given Board
Company: Ivo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Two players play tic-tac-toe on a 3 x 3 board: player 1 places `X` and always moves first, and player 2 places `O`. Given a board position, return every possible game that can be played from it to the end. Games that end with a win and games that end with no winner both count. Each game is reported as the sequence of cells played.
### Function Signature
```python
def list_all_games(board: list[str]) -> list[list[int]]:
```
### Rules
- `board` has 3 strings of 3 characters. `board[r][c]` is `'X'`, `'O'` or `'.'` (empty). Cell `(r, c)` is numbered `3 * r + c`, so the cells are `0` to `8` in row-major order.
- The player to move is `X` if the board holds equally many `X` and `O` marks, and `O` otherwise. Players then alternate, and each move places the mover's mark in an empty cell.
- A game ends immediately when the player who just moved has three of their marks in one row, one column or one of the two diagonals (a win), or when no empty cell remains. No move is made after the end.
- A game is the list of cells played from the given position until the game ends. Two games are different whenever their move lists differ, even if they end on the same final board.
- If the given board has already ended (a player has three in a row, or no empty cell remains), return `[[]]`: exactly one game, with no moves.
- Return the games in ascending lexicographic order of their move lists: compare the first cells, then the second cells, and so on. No game is a prefix of another, so this order is unique.
### Constraints
- `len(board) == 3` and `len(board[r]) == 3` for every row `r`.
- Every character is `'X'`, `'O'` or `'.'`.
- The board is reachable from the empty board by alternating moves starting with `X`, with no move made after a player has won. In particular, the number of `X` marks minus the number of `O` marks is `0` or `1`.
- The board may be empty. That input produces the largest output: 255,168 games.
- Every cell index in the output is between `0` and `8`, and every game has at most 9 moves.
### Examples
**Example 1**
```text
Input: board = ["XOX", "OOX", "X.."]
Output: [[7], [8, 7]]
```
`X` has one more mark, so `O` moves. Playing cell `7` completes the middle column for `O` and ends the game at once. Playing cell `8` leaves only cell `7`, which `X` takes, filling the board with no winner.
**Example 2**
```text
Input: board = ["XXO", "OOX", "..."]
Output: [[6, 7, 8], [6, 8, 7], [7, 6], [7, 8, 6], [8, 6], [8, 7, 6]]
```
The counts are equal, so `X` moves. In `[7, 6]` and `[8, 6]`, `O` takes cell `6` and completes the diagonal through cells `2`, `4` and `6`, which ends the game after two moves. The other four games fill the board with no winner.
**Example 3**
```text
Input: board = ["XXX", "OO.", "..."]
Output: [[]]
```
`X` already has the top row, so the game is over and the only game from this position has no moves.
Overview: Given a 3 x 3 tic-tac-toe position, return every complete game that can still be played from it, as move sequences in lexicographic order, counting both wins and draws. It tests turn and win detection, stopping a game at the first three in a row, and exhaustive enumeration of a game tree.
Two players play tic-tac-toe on a 3 x 3 board: player 1 places `X` and always moves first, and player 2 places `O`. Given a board position, return every possible game that can be played from it to the end. Games that end with a win and games that end with no winner both count. Each game is reported as the sequence of cells played.
Implement `list_all_games(board)`. It returns a list of games, and each game is a list of cell indices.
### Rules
- `board` has 3 strings of 3 characters. `board[r][c]` is `'X'`, `'O'` or `'.'` (empty). Cell `(r, c)` is numbered `3 * r + c`, so the cells are `0` to `8` in row-major order.
- The player to move is `X` if the board holds equally many `X` and `O` marks, and `O` otherwise. Players then alternate, and each move places the mover's mark in an empty cell.
- A game ends immediately when the player who just moved has three of their marks in one row, one column or one of the two diagonals (a win), or when no empty cell remains. No move is made after the end.
- A game is the list of cells played from the given position until the game ends. Two games are different whenever their move lists differ, even if they end on the same final board.
- If the given board has already ended (a player has three in a row, or no empty cell remains), return `[[]]`: exactly one game, with no moves.
- Return the games in ascending lexicographic order of their move lists: compare the first cells, then the second cells, and so on. No game is a prefix of another, so this order is unique.
### Constraints
- `len(board) == 3` and `len(board[r]) == 3` for every row `r`.
- Every character is `'X'`, `'O'` or `'.'`.
- The board is reachable from the empty board by alternating moves starting with `X`, with no move made after a player has won. In particular, the number of `X` marks minus the number of `O` marks is `0` or `1`.
- The board may be empty. That input produces the largest output: 255,168 games.
- Every cell index in the output is between `0` and `8`, and every game has at most 9 moves.
- No value exceeds 2^31 - 1, so 32-bit integers are enough in every language.
### Example 1
```text
Input: board = ["XOX", "OOX", "X.."]
Output: [[7], [8, 7]]
```
`X` has one more mark, so `O` moves. Playing cell `7` completes the middle column for `O` and ends the game at once. Playing cell `8` leaves only cell `7`, which `X` takes, filling the board with no winner.
### Example 2
```text
Input: board = ["XXO", "OOX", "..."]
Output: [[6, 7, 8], [6, 8, 7], [7, 6], [7, 8, 6], [8, 6], [8, 7, 6]]
```
The counts are equal, so `X` moves. In `[7, 6]` and `[8, 6]`, `O` takes cell `6` and completes the diagonal through cells `2`, `4` and `6`, which ends the game after two moves. The other four games fill the board with no winner.
Constraints
- len(board) == 3 and len(board[r]) == 3 for every row r.
- Every character is 'X', 'O' or '.'.
- The board is reachable from the empty board by alternating moves starting with X, with no move made after a player has won. In particular, the number of X marks minus the number of O marks is 0 or 1.
- The board may be empty. That input produces the largest output: 255,168 games.
- Every cell index in the output is between 0 and 8, and every game has at most 9 moves.
- No value exceeds 2^31 - 1, so 32-bit integers are enough in every language.
Examples
Input: (['XOX', 'OOX', 'X..'],)
Expected Output: [[7], [8, 7]]
Explanation: Source example 1: O to move; cell 7 wins the middle column at once, cell 8 leaves cell 7 for X and a draw. Regression: [7] sorts before the longer [8, 7].
Input: (['XXO', 'OOX', '...'],)
Expected Output: [[6, 7, 8], [6, 8, 7], [7, 6], [7, 8, 6], [8, 6], [8, 7, 6]]
Explanation: Source example 2: X to move; O wins the anti-diagonal 2-4-6 in [7, 6] and [8, 6]; [6, 7, 8] and [8, 7, 6] reach the same final board but are separate games.
Hints
- Before making any move, decide whether the given board has already ended, and work out whose turn it is from the counts of X and O marks.
- After a move, only the row, the column and any diagonal through the cell just played can have become complete, and only for the player who just moved.
- Two games are ordered by the first position at which their move lists differ; because no game is a prefix of another, that position always exists.