{x}
blog image

Valid Tic-Tac-Toe State

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:

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

Example 2:

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

Example 3:

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

 

Constraints:

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

Solution Explanation

This problem asks to determine if a given Tic-Tac-Toe board represents a valid state reachable during a game. The solution leverages several key observations about the game's rules to efficiently check validity.

Key Observations:

  1. X always goes first: The number of 'X's can be at most one more than the number of 'O's.

  2. Winning condition: If either 'X' or 'O' has won, the game is over. A player can only win if they have made at least three moves.

  3. Impossible states: If 'O' has won and the number of 'O's equals the number of 'X's, the board is invalid. Similarly, if 'X' has won and the number of 'X's is equal to the number of 'O's, or there's one less 'X' than 'O's, the board is invalid.

Algorithm:

  1. Count X's and O's: Count the number of 'X' and 'O' characters on the board.

  2. Check for win conditions: A helper function win(player) checks if the given player ('X' or 'O') has three in a row (horizontally, vertically, or diagonally).

  3. Validate the counts: The code then checks if the counts of 'X' and 'O' satisfy the rule that the number of 'X's is either equal to or one greater than the number of 'O's.

  4. Check impossible winning scenarios: It then checks if a winning condition exists for 'X' or 'O' and if that winning condition is consistent with the number of X's and O's on the board. This eliminates impossible winning scenarios like 'O' winning when the number of 'O's is less than the number of 'X's or vice-versa.

Time Complexity: O(1) - The algorithm iterates through a fixed-size 3x3 board, so the time taken remains constant regardless of input size.

Space Complexity: O(1) - The algorithm uses a constant amount of extra space to store the counts of 'X' and 'O' and other variables.

Code Explanation (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)

The Python code directly implements the algorithm described above. The win function efficiently checks for winning conditions. The main part of the code counts 'X' and 'O', then performs the validity checks based on the rules.

The other languages (Java, C++, Go, JavaScript) follow a similar logic and structure, adapting the syntax and data structures specific to each language. The core algorithm remains unchanged across all implementations.