Valid Tic-Tac-Toe State Problem

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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline \colorbox{orange} O & & \\ \hline & & \\ \hline & & \\ \hline \end{array} $$

1
2
3

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

Example 2:

$$ \begin{array}{|c|c|c|} \hline \colorbox{lightblue} X & \colorbox{orange} O & \colorbox{lightblue} X \\ \hline & \colorbox{lightblue} X & \\ \hline & & \\ \hline \end{array} $$

1
2
3

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

Example 3:

$$ \begin{array}{|c|c|c|} \hline \colorbox{lightblue} X & \colorbox{orange} O & \colorbox{lightblue} X \\ \hline \colorbox{orange} O & & \colorbox{orange} O \\ \hline \colorbox{lightblue} X & \colorbox{orange} O & \colorbox{lightblue} X \\ \hline \end{array} $$

1
2

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

Solution

Method 1 - Simple Heuristics

Here are the key points:

1. Player Turn Rules:
   • Since player ‘X’ always starts, the count of ‘X’ should be greater than or equal to the count of ‘O’. Therefore, if o_count > x_count, the board is invalid.
   • Players alternate turns, so the difference between the count of ‘X’ and ‘O’ should not exceed one. Thus, if x_count - o_count > 1, the board is invalid.
2. Winning Conditions:
   • If player ‘O’ has a winning condition, ensure that player ‘X’ does not have a winning condition at the same time. This is because the game should stop as soon as a winning condition is met.
   • If player ‘O’ wins, then x_count should equal o_count since ‘O’ plays second and the counts must match up to this condition.
   • If player ‘X’ wins, then x_count should be exactly one more than o_count because ‘X’ starts first.
3. Algorithm:
   • Check initial conditions for count validity.
   • Evaluate the board to see if either player has a winning configuration.
   • Validate that the counts and winning conditions align correctly based on the rules of the game.

Here is a more detailed explanation:

1. Check Initial Count Validity:
   • If o_count > x_count, return False.
   • If x_count - o_count > 1, return False.
2. Check Winning Conditions:
   • If player ‘O’ wins:
     • Ensure player ‘X’ does not also win. If both win, return False.
     • Ensure x_count == o_count. If not, return False.
   • If player ‘X’ wins:
     • Ensure x_count == o_count + 1. If not, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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++;
                if (c == 'O') oCount++;
            }
        }
        
        // Initial count validity
        if (oCount > xCount) return false;
        if (xCount > oCount + 1) return false;
        
        boolean xWins = isWinner(board, 'X');
        boolean oWins = isWinner(board, 'O');
        
        // Checking winning conditions
        if (oWins) {
            if (xWins) return false;  // Both can't win simultaneously
            if (xCount != oCount) return false;  // 'O' wins so counts must be equal
        }
        
        if (xWins) {
            if (xCount != oCount + 1) return false;  // 'X' wins so must have one more count than 'O'
        }
        
        return true;
    }
    
    private boolean isWinner(String[] board, char p) {
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == p && board[i].charAt(1) == p && board[i].charAt(2) == p) return true;
            if (board[0].charAt(i) == p && board[1].charAt(i) == p && board[2].charAt(i) == p) return true;
        }
        if (board[0].charAt(0) == p && board[1].charAt(1) == p && board[2].charAt(2) == p) return true;
        if (board[0].charAt(2) == p && board[1].charAt(1) == p && board[2].charAt(0) == p) return true;
        
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        x_count = sum(row.count('X') for row in board)
        o_count = sum(row.count('O') for row in board)

        # Initial count validity
        if o_count > x_count:
            return False
        if x_count > o_count + 1:
            return False

        x_wins = self.is_winner(board, 'X')
        o_wins = self.is_winner(board, 'O')
        
        # Checking winning conditions
        if o_wins:
            if x_wins:
                return False  # Both can't win simultaneously
            if x_count != o_count:
                return False  # 'O' wins so counts must be equal
        
        if x_wins:
            if x_count != o_count + 1:
                return False  # 'X' wins so must have one more count than 'O'
        
        return True

    def is_winner(self, board: List[str], p: str) -> bool:
        for i in range(3):
            if board[i][0] == p and board[i][1] == p and board[i][2] == p:
                return True
            if board[0][i] == p and board[1][i] == p and board[2][i] == p:
                return True
        if board[0][0] == p and board[1][1] == p and board[2][2] == p:
            return True
        if board[0][2] == p and board[1][1] == p and board[2][0] == p:
            return True
        
        return False
`

Complexity

• ⏰ Time complexity: O(1), because the board size is fixed at 3 x 3. Checking each cell and verifying win conditions is constant.
• 🧺 Space complexity: O(1), as no additional space proportional to input size is required beyond a few counters and boolean flags.