# Valid Tic-Tac-Toe State
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/valid-tic-tac-toe-state)
Canonical: https://scaleengineer.com/dsa/problems/valid-tic-tac-toe-state
**Data structures:** Array, Matrix
---
## Problem
Given a Tic-Tac-Toe board as a string array `board`, return `true` if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a `3 x 3` array that consists of characters `' '`, `'X'`, and `'O'`. The `' '` character represents an empty square.

Here are the rules of Tic-Tac-Toe:

* Players take turns placing characters into empty squares `' '`.
* The first player always places `'X'` characters, while the second player always places `'O'` characters.
* `'X'` and `'O'` characters are always placed into empty squares, never filled ones.
* The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
* The game also ends if all squares are non-empty.
* No more moves can be played if the game is over.

**Example 1:**

![](https://assets.glich.co/dsa/valid-tic-tac-toe-state/image0.jpg) 

**Input:** board = ["O  ","   ","   "]
**Output:** false
**Explanation:** The first player always plays "X".

**Example 2:**

![](https://assets.glich.co/dsa/valid-tic-tac-toe-state/image1.jpg) 

**Input:** board = ["XOX"," X ","   "]
**Output:** false
**Explanation:** Players take turns making moves.

**Example 3:**

![](https://assets.glich.co/dsa/valid-tic-tac-toe-state/image2.jpg) 

**Input:** board = ["XOX","O O","XOX"]
**Output:** true

**Constraints:**

* `board.length == 3`
* `board[i].length == 3`
* `board[i][j]` is either `'X'`, `'O'`, or `' '`.

# Approaches
## State-Space Exploration (Brute Force)
This approach involves generating all possible valid Tic-Tac-Toe board states that can be reached during a game. We start from an empty board and recursively explore all valid moves for 'X' and 'O' in turns. All encountered board states are stored in a set. Finally, we check if the given input board exists in our set of generated valid states.
**Time:** O(1) with a large constant factor for pre-computation. The number of states in the game tree of Tic-Tac-Toe is fixed. The generation process explores this tree once. The number of legal states is 5,478. For each validation query, the time is O(1) on average for the hash set lookup. · **Space:** O(1) with a large constant factor. The number of legal Tic-Tac-Toe positions is 5,478. We need to store all of them. Since each board state can be represented by 9 characters, the space required is constant but substantial (approx. 5478 * 9 characters).
**Pros:** Conceptually simple as it directly models the game's progression.; After the initial, one-time generation of states, subsequent validations are extremely fast (O(1) average time).
**Cons:** High pre-computation time and memory usage are required to generate and store all possible states.; Significantly less efficient than a direct rule-based check for validating a single input board.; The implementation is more complex and prone to errors, especially in the recursion and backtracking logic.
### Explanation
This method simulates every possible game of Tic-Tac-Toe to build a comprehensive database of all legal board positions. We can use a recursive backtracking function to achieve this.

The function, say `generate(board, player, states)`, would take the current board, the current player, and a set to store valid states. The base case for the recursion is when a player wins or the board is full, at which point no further moves are possible from that state.

In each recursive step, we iterate through all empty cells. For each empty cell, we place the current player's mark, add the new board configuration to our set of states, and then make a recursive call for the next player. After the recursive call returns, we backtrack by resetting the cell to empty to explore other possibilities.

The process is initiated with an empty board and player 'X'. After the entire game tree is explored, the `states` set will contain every possible board position that can occur in a valid game. The final step is to convert the input `board` into a standardized format (e.g., a single string) and check for its presence in the `states` set.

```java
class Solution {
    // Using a static set to cache the results across multiple calls if the Solution object is reused.
    private static final Set<String> validStates = new HashSet<>();

    // Static initializer to generate all states once when the class is loaded.
    static {
        char[][] board = new char[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                board[i][j] = ' ';
            }
        }
        generate(board, 'X');
    }

    public boolean validTicTacToe(String[] board) {
        return validStates.contains(board[0] + board[1] + board[2]);
    }

    private static void generate(char[][] board, char player) {
        validStates.add(boardToString(board));

        if (hasWon(board, 'X') || hasWon(board, 'O') || isFull(board)) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == ' ') {
                    board[i][j] = player;
                    generate(board, player == 'X' ? 'O' : 'X');
                    board[i][j] = ' '; // Backtrack
                }
            }
        }
    }

    private static String boardToString(char[][] board) {
        return new String(board[0]) + new String(board[1]) + new String(board[2]);
    }

    private static boolean hasWon(char[][] board, char p) {
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == p && board[i][1] == p && board[i][2] == p) return true;
            if (board[0][i] == p && board[1][i] == p && board[2][i] == p) return true;
        }
        if (board[0][0] == p && board[1][1] == p && board[2][2] == p) return true;
        if (board[0][2] == p && board[1][1] == p && board[2][0] == p) return true;
        return false;
    }

    private static boolean isFull(char[][] board) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == ' ') return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Define a recursive function `generate(board, player)` to explore the game tree.
*   Use a `HashSet<String>` to store all reachable board states, using a string representation of the board as the key.
*   The `generate` function:
    a. Adds the current `board` state to the hash set.
    b. Checks if the game is over (a player has won or the board is full). If so, it returns, as no more moves can be played.
    c. Iterates over all empty squares on the `board`.
    d. For each empty square, it places the `player`'s mark.
    e. It makes a recursive call to `generate` with the new board and the other player.
    f. It backtracks by removing the mark to explore other moves.
*   Start the process by calling `generate` with an empty board and player 'X'.
*   To validate an input `board`, convert it to the same string format and check if it's in the hash set.

## Rule-Based Validation
This approach directly validates the given board state against the rules of Tic-Tac-Toe without simulating the game. We derive a set of necessary conditions that any valid board state must satisfy. These conditions relate to the number of 'X's and 'O's, and the winning status of each player.
**Time:** O(1). The board size is fixed at 3x3. We perform a constant number of operations: one pass to count characters (9 cells) and two calls to a `checkWin` function, which each check 8 lines of 3 cells. The total number of operations is constant. · **Space:** O(1). We only use a few variables to store counts and boolean flags. No extra space that scales with input size is needed.
**Pros:** Extremely efficient in both time and space as it performs a fixed number of checks.; The logic is straightforward and directly derived from the game's fundamental rules.; Easy to implement and debug.
**Cons:** Requires careful logical deduction to ensure all rules and edge cases are covered correctly.
### Explanation
A valid Tic-Tac-Toe board must satisfy several invariants. We can check these invariants directly on the input board to determine its validity.

1.  **Turn Count Invariant**: 'X' always plays first. Therefore, the number of 'X's (`xCount`) must either be equal to the number of 'O's (`oCount`) or one greater. Any other count difference (`oCount > xCount` or `xCount > oCount + 1`) is impossible.

2.  **Winning State Invariant**: The game ends as soon as a player wins. No more moves are allowed after a win.
    *   If 'X' has won, the move that resulted in the win must have been made by 'X'. This implies that `xCount` must be one more than `oCount` (`xCount == oCount + 1`). It's impossible for 'O' to have made a move after 'X' won.
    *   If 'O' has won, the winning move must have been made by 'O'. This implies that `xCount` must be equal to `oCount` (`xCount == oCount`). It's impossible for 'X' to have made a move after 'O' won.
    *   It is impossible for both players to have a winning line simultaneously.

The algorithm first counts the 'X's and 'O's. Then, it determines if 'X' or 'O' has won. Finally, it combines these pieces of information to check for contradictions based on the rules above.

```java
class Solution {
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') {
                    xCount++;
                } else if (c == 'O') {
                    oCount++;
                }
            }
        }

        // Rule 1: Turn count must be valid.
        // O cannot have more moves than X.
        // X cannot have more than one extra move over O.
        if (oCount > xCount || xCount > oCount + 1) {
            return false;
        }

        boolean xWins = checkWin(board, 'X');
        boolean oWins = checkWin(board, 'O');

        // Rule 2: If X wins, X must have made the last move.
        // So, xCount must be one more than oCount.
        if (xWins && xCount != oCount + 1) {
            return false;
        }

        // Rule 3: If O wins, O must have made the last move.
        // So, xCount must be equal to oCount.
        if (oWins && xCount != oCount) {
            return false;
        }
        
        // Note: The case where both xWins and oWins are true is implicitly handled.
        // If xWins is true, it requires xCount == oCount + 1.
        // If oWins is true, it requires xCount == oCount.
        // These two count conditions are mutually exclusive, so if both players appear to win,
        // one of the checks above will fail, correctly returning false.

        // If all rules are satisfied, the state is valid.
        return true;
    }

    private boolean checkWin(String[] board, char player) {
        // Check rows
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == player && board[i].charAt(1) == player && board[i].charAt(2) == player) {
                return true;
            }
        }

        // Check columns
        for (int j = 0; j < 3; j++) {
            if (board[0].charAt(j) == player && board[1].charAt(j) == player && board[2].charAt(j) == player) {
                return true;
            }
        }

        // Check diagonals
        if (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player) {
            return true;
        }
        if (board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
*   Count the number of 'X's (`xCount`) and 'O's (`oCount`) on the board.
*   Check the turn rule: if `oCount > xCount` or `xCount > oCount + 1`, the state is invalid. Return `false`.
*   Create a helper function `checkWin(board, player)` to determine if a player has won. This function checks all 8 possible winning lines (3 rows, 3 columns, 2 diagonals).
*   Call `checkWin` to find out if 'X' has won (`xWins`) and if 'O' has won (`oWins`).
*   Check the winning conditions:
    a. If `xWins` is true, it must be that `xCount == oCount + 1`. If not, return `false`.
    b. If `oWins` is true, it must be that `xCount == oCount`. If not, return `false`.
*   Note that the case where both players win is implicitly handled by the above two checks. If both `xWins` and `oWins` were true, one of the conditions on counts must fail.
*   If none of the invalid conditions are met, the board state is reachable. Return `true`.

# Solutions
### Java

```java
class Solution {
private
  String[] board;
public
  boolean validTicTacToe(String[] board) {
    this.board = board;
    int x = count('X'), o = count('O');
    if (x != o && x - 1 != o) {
      return false;
    }
    if (win('X') && x - 1 != o) {
      return false;
    }
    return !(win('O') && x != o);
  }
private
  boolean win(char x) {
    for (int i = 0; i < 3; ++i) {
      if (board[i].charAt(0) == x && board[i].charAt(1) == x &&
          board[i].charAt(2) == x) {
        return true;
      }
      if (board[0].charAt(i) == x && board[1].charAt(i) == x &&
          board[2].charAt(i) == x) {
        return true;
      }
    }
    if (board[0].charAt(0) == x && board[1].charAt(1) == x &&
        board[2].charAt(2) == x) {
      return true;
    }
    return board[0].charAt(2) == x && board[1].charAt(1) == x &&
           board[2].charAt(0) == x;
  }
private
  int count(char x) {
    int cnt = 0;
    for (var row : board) {
      for (var c : row.toCharArray()) {
        if (c == x) {
          ++cnt;
        }
      }
    }
    return cnt;
  }
}

```

### JavaScript

```javascript
/** * @param {string[]} board * @return {boolean} */ var validTicTacToe = function ( board ) { function count ( x ) { let cnt = 0 ; for ( const row of board ) { for ( const c of row ) { cnt += c == x ; } } return cnt ; } function win ( x ) { for ( let i = 0 ; i < 3 ; ++ i ) { if ( board [ i ][ 0 ] == x && board [ i ][ 1 ] == x && board [ i ][ 2 ] == x ) { return true ; } if ( board [ 0 ][ i ] == x && board [ 1 ][ i ] == x && board [ 2 ][ i ] == x ) { return true ; } } if ( board [ 0 ][ 0 ] == x && board [ 1 ][ 1 ] == x && board [ 2 ][ 2 ] == x ) { return true ; } return board [ 0 ][ 2 ] == x && board [ 1 ][ 1 ] == x && board [ 2 ][ 0 ] == x ; } const [ x , o ] = [ count ( ' X ' ), count ( ' O ' )]; if ( x != o && x - 1 != o ) { return false ; } if ( win ( ' X ' ) && x - 1 != o ) { return false ; } return ! ( win ( ' O ' ) && x != o ); };
```

### CPP

```cpp
class Solution {
public:
  bool validTicTacToe(vector<string> &board) {
    auto count = [&](char x) {
      int ans = 0;
      for (auto &row : board)
        for (auto &c : row)
          ans += c == x;
      return ans;
    };
    auto win = [&](char x) {
      for (int i = 0; i < 3; ++i) {
        if (board[i][0] == x && board[i][1] == x && board[i][2] == x)
          return true;
        if (board[0][i] == x && board[1][i] == x && board[2][i] == x)
          return true;
      }
      if (board[0][0] == x && board[1][1] == x && board[2][2] == x)
        return true;
      return board[0][2] == x && board[1][1] == x && board[2][0] == x;
    };
    int x = count('X'), o = count('O');
    if (x != o && x - 1 != o)
      return false;
    if (win('X') && x - 1 != o)
      return false;
    return !(win('O') && x != o);
  }
};

```

### Python

```python
class Solution:
    def validTicTacToe(self, board: List[str]) -> bool: def win(x): for i in range(3): if all(board[i][j] == x for j in range(3)): return True if all(board[j][i] == x for j in range(3)): return True if all(board[i][i] == x for i in range(3)): return True return all(board[i][2 - i] == x for i in range(3)) x = sum(board[i][j] == 'X' for i in range(3) for j in range(3)) o = sum(board[i][j] == 'O' for i in range(3) for j in range(3)) if x != o and x - 1 != o: return False if win('X') and x - 1 != o: return False return not (win('O') and x != o)

```