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:

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

Function shape:

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

Examples

Example 1:

board = ["O  ", "   ", "   "]

This is invalid because O cannot move first.

The answer is:

False

Example 2:

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

Count the marks:

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

The answer is:

False

Example 3:

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

This board can be reached by alternating moves.

The answer is:

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:

Any other count relation is invalid.

Then handle winning boards:

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.

Implementation

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:

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

The helper checks whether a player has any winning line:

def wins(player: str) -> bool:

Rows and columns are checked together:

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:

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:

if o_count > x_count:
    return False

if x_count > o_count + 1:
    return False

If both players win, the board cannot be legal:

if x_wins and o_wins:
    return False

A winning board must match the player who just moved:

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

if o_wins and x_count != o_count:
    return False

Testing

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: