# LeetCode 794: Valid Tic-Tac-Toe State

## Problem Restatement

We are given a Tic-Tac-Toe board as a list of three strings.

Each cell contains one of:

| Character | Meaning |
|---|---|
| `"X"` | First player's mark |
| `"O"` | Second player's mark |
| `" "` | Empty square |

We need to return `True` if this board position could happen during a valid Tic-Tac-Toe game.

The rules are:

1. `X` always moves first.
2. Players alternate turns.
3. A move can only be placed in an empty square.
4. The game ends when a player gets three marks in a row, column, or diagonal.
5. No more moves can be played after the game ends.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `board`, a `3 x 3` string array |
| Output | `True` if the position is reachable, otherwise `False` |
| First player | `X` |
| Second player | `O` |
| Empty cell | Space character `" "` |

Function shape:

```python
class Solution:
    def validTicTacToe(self, board: list[str]) -> bool:
        ...
```

## Examples

Example 1:

```python
board = ["O  ", "   ", "   "]
```

This is invalid because `O` cannot move first.

The answer is:

```python
False
```

Example 2:

```python
board = ["XOX", " X ", "   "]
```

Count the marks:

| Mark | Count |
|---|---:|
| `X` | `3` |
| `O` | `1` |

`X` has moved two more times than `O`, which is impossible because players alternate turns.

The answer is:

```python
False
```

Example 3:

```python
board = ["XOX", "O O", "XOX"]
```

This board can be reached by alternating moves.

The answer is:

```python
True
```

## First Thought: Simulate All Games

One idea is to generate every possible Tic-Tac-Toe game from an empty board.

Then we check whether the given board appears among those states.

This is possible because the board is only `3 x 3`, but it is unnecessary.

A valid board can be checked using a few rules about move counts and winners.

## Key Insight

There are only two things that matter:

1. The number of `X` and `O` marks.
2. Whether `X` or `O` already has a winning line.

Since `X` starts first and players alternate:

| Valid count relation | Meaning |
|---|---|
| `x_count == o_count` | It is `X`'s turn next, or `O` just moved |
| `x_count == o_count + 1` | It is `O`'s turn next, or `X` just moved |

Any other count relation is invalid.

Then handle winning boards:

| Winner | Required count relation |
|---|---|
| `X` wins | `x_count == o_count + 1` |
| `O` wins | `x_count == o_count` |

Both players cannot win in a valid final state, because the game stops as soon as one player wins.

## Algorithm

1. Count how many `X` and `O` marks appear.
2. Check if `X` has a winning line.
3. Check if `O` has a winning line.
4. Validate the count relation:
   1. If `o_count > x_count`, return `False`.
   2. If `x_count > o_count + 1`, return `False`.
5. Validate winner rules:
   1. If `X` wins and `x_count != o_count + 1`, return `False`.
   2. If `O` wins and `x_count != o_count`, return `False`.
   3. If both win, return `False`.
6. Return `True`.

## Correctness

Since `X` always moves first and players alternate turns, at any reachable state `X` must have either the same number of moves as `O`, or exactly one more move. The algorithm rejects every board that violates this condition.

A player wins only immediately after making a move. Therefore, if `X` wins, the last move must have been made by `X`, so `X` must have exactly one more mark than `O`. If `O` wins, the last move must have been made by `O`, so the counts must be equal.

The algorithm checks every row, column, and diagonal for winning lines. If a winning line exists with an impossible move count, the board is rejected.

If both players are winners, the board is rejected. In a valid game, play stops when the first winner appears, so the other player cannot later create a winning line.

If none of these invalid conditions hold, then the mark counts and winner status are consistent with a legal sequence of moves. Therefore, the board is valid.

## Complexity

The board size is fixed at `3 x 3`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | We inspect a constant-size board |
| Space | `O(1)` | Only counters and booleans are stored |

## Implementation

```python
class Solution:
    def validTicTacToe(self, board: list[str]) -> bool:
        x_count = 0
        o_count = 0

        for row in board:
            x_count += row.count("X")
            o_count += row.count("O")

        def wins(player: str) -> bool:
            for i in range(3):
                if all(board[i][j] == player for j in range(3)):
                    return True

                if all(board[j][i] == player for j in range(3)):
                    return True

            if all(board[i][i] == player for i in range(3)):
                return True

            if all(board[i][2 - i] == player for i in range(3)):
                return True

            return False

        x_wins = wins("X")
        o_wins = wins("O")

        if o_count > x_count:
            return False

        if x_count > o_count + 1:
            return False

        if x_wins and o_wins:
            return False

        if x_wins and x_count != o_count + 1:
            return False

        if o_wins and x_count != o_count:
            return False

        return True
```

## Code Explanation

First, count both marks:

```python
x_count += row.count("X")
o_count += row.count("O")
```

The helper checks whether a player has any winning line:

```python
def wins(player: str) -> bool:
```

Rows and columns are checked together:

```python
for i in range(3):
    if all(board[i][j] == player for j in range(3)):
        return True

    if all(board[j][i] == player for j in range(3)):
        return True
```

Then the two diagonals are checked:

```python
if all(board[i][i] == player for i in range(3)):
    return True

if all(board[i][2 - i] == player for i in range(3)):
    return True
```

The move count must be consistent with alternating turns:

```python
if o_count > x_count:
    return False

if x_count > o_count + 1:
    return False
```

If both players win, the board cannot be legal:

```python
if x_wins and o_wins:
    return False
```

A winning board must match the player who just moved:

```python
if x_wins and x_count != o_count + 1:
    return False

if o_wins and x_count != o_count:
    return False
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.validTicTacToe(["O  ", "   ", "   "]) is False
    assert s.validTicTacToe(["XOX", " X ", "   "]) is False
    assert s.validTicTacToe(["XOX", "O O", "XOX"]) is True

    assert s.validTicTacToe(["   ", "   ", "   "]) is True
    assert s.validTicTacToe(["X  ", "   ", "   "]) is True
    assert s.validTicTacToe(["XX ", "OO ", "   "]) is True

    assert s.validTicTacToe(["XXX", "OO ", "   "]) is True
    assert s.validTicTacToe(["XXX", "O O", "OO "]) is False

    assert s.validTicTacToe(["OOO", "XX ", "XX "]) is True
    assert s.validTicTacToe(["OOO", "X  ", "XX "]) is False

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `O` moves first | Rejects invalid turn order |
| Too many `X` marks | Rejects invalid count relation |
| Valid full board | Accepts reachable draw-like state |
| Empty board | Valid initial state |
| Single `X` | Valid first move |
| `X` wins with correct count | Accepts valid win |
| `X` wins with extra moves | Rejects moves after game end |
| `O` wins with correct count | Accepts valid `O` win |
| `O` wins with wrong count | Rejects impossible winner count |