Valid Tic-Tac-Toe State

medium math simulation case-analysis

Problem

Given a 3x3 board of 'X','O',' ', decide whether it could appear in a real tic-tac-toe game. Rules: X moves first, alternating, and the game ends as soon as someone wins.

Inputboard = ["O "," "," "]

Outputfalse

O cannot move first.

board

def validTicTacToe(board):
    xs = sum(row.count('X') for row in board)
    os = sum(row.count('O') for row in board)
    if os not in (xs, xs - 1):
        return False
    def wins(p):
        lines = list(board) + [''.join(r[c] for r in board) for c in range(3)]
        lines += [''.join(board[i][i] for i in range(3)), ''.join(board[i][2-i] for i in range(3))]
        return any(line == p * 3 for line in lines)
    if wins('X') and os == xs:
        return False
    if wins('O') and os != xs:
        return False
    return True

var validTicTacToe = function(board) {
    let xs = 0, os = 0;
    for (const r of board) for (const c of r) { if (c==='X') xs++; else if (c==='O') os++; }
    if (os !== xs && os !== xs - 1) return false;
    const wins = (p) => {
        for (let i = 0; i < 3; i++) {
            if (board[i] === p+p+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;
    };
    if (wins('X') && os === xs) return false;
    if (wins('O') && os !== xs) return false;
    return true;
};

class Solution {
    public boolean validTicTacToe(String[] board) {
        int xs = 0, os = 0;
        for (String r : board) for (char c : r.toCharArray()) { if (c=='X') xs++; else if (c=='O') os++; }
        if (os != xs && os != xs - 1) return false;
        if (wins(board, 'X') && os == xs) return false;
        if (wins(board, 'O') && os != xs) return false;
        return true;
    }
    private boolean wins(String[] b, char p) {
        for (int i = 0; i < 3; i++) {
            if (b[i].charAt(0)==p && b[i].charAt(1)==p && b[i].charAt(2)==p) return true;
            if (b[0].charAt(i)==p && b[1].charAt(i)==p && b[2].charAt(i)==p) return true;
        }
        if (b[0].charAt(0)==p && b[1].charAt(1)==p && b[2].charAt(2)==p) return true;
        if (b[0].charAt(2)==p && b[1].charAt(1)==p && b[2].charAt(0)==p) return true;
        return false;
    }
}

class Solution {
    bool wins(vector<string>& b, char p) {
        for (int i = 0; i < 3; i++) {
            if (b[i][0]==p && b[i][1]==p && b[i][2]==p) return true;
            if (b[0][i]==p && b[1][i]==p && b[2][i]==p) return true;
        }
        if (b[0][0]==p && b[1][1]==p && b[2][2]==p) return true;
        if (b[0][2]==p && b[1][1]==p && b[2][0]==p) return true;
        return false;
    }
public:
    bool validTicTacToe(vector<string>& board) {
        int xs = 0, os = 0;
        for (auto& r : board) for (char c : r) { if (c=='X') xs++; else if (c=='O') os++; }
        if (os != xs && os != xs - 1) return false;
        if (wins(board, 'X') && os == xs) return false;
        if (wins(board, 'O') && os != xs) return false;
        return true;
    }
};

Explanation

We do not replay the game; we just check a few logical rules that any reachable board must satisfy. The whole answer comes from comparing the counts of X and O and seeing who, if anyone, has a winning line.

Rule one is about counts. Since X moves first and players alternate, the number of Os must equal the number of Xs or be exactly one fewer: os == xs or os == xs - 1. Anything else is impossible.

Rule two is about winning. If X has three in a row, then X made the last move, so we need xs == os + 1; if xs == os while X wins, that is invalid. Symmetrically, if O wins, O made the last move, so we need os == xs; if os != xs while O wins, that is invalid. The wins(p) helper just checks all rows, columns, and the two diagonals.

Example: ["O ", " ", " "] has xs = 0 and os = 1. Here os is not equal to xs nor xs - 1 (it is greater), so O appears to have moved first, which is illegal → false.

If both count and win rules hold, the board is reachable and we return true.

Time: O(1) Space: O(1)