Tic Tac Toe

Tic Tac Toe Valid Board State

Problem Statement

Given a Tic Tac Toe 3×3 board, validate that it represents a valid game state. A valid board must satisfy:

1. Valid cell values: Each cell is either empty (00), X (01), or O (10)
2. Balanced move count: Number of X's and O's are equal, or X's are exactly one more than O's (since X always goes first)
3. No winning state: Neither player has achieved three in a row (horizontally, vertically, or diagonally)

The board uses 2-bit encoding:

• 00 = empty
• 01 = X
• 10 = O
• 11 = invalid (should not appear)

Constraints

• Board size: 3×3 (9 cells)
• Cell values: 00 (empty), 01 (X), 10 (O)
• Win prevention: No three-in-a-row for X or O
• Cell encoding: 2 bits per cell

Examples

Example 1 (Valid Starting Position):

All cells empty (all 00)
Valid
Explanation: Valid initial board state

Example 2 (Valid Game In Progress):

X | O | X
---------
  | X | O
---------
  |   |

Encoded as: [01,10,01], [00,01,10], [00,00,00]
Valid
Explanation:
- X count = 3, O count = 2 (X count is one more) ✓
- No winning lines ✓

Example 3 (Invalid - X Won):

X | X | X
---------
O | O |
---------
  |   |

Invalid
Explanation: X has three in a row (top row)

Example 4 (Invalid - Move Count):

X | X | X
---------
X | O | O
---------
O |   |

Invalid
Explanation: X count = 4, O count = 3, but X should have at most one more move than O

Example 5 (Valid - Diagonal Not Win):

X |   | O
---------
  | X |
---------
O |   | X

Encoded: [01,00,10], [00,01,00], [10,00,01]
Valid
Explanation: X and O each have 3 cells, but X's marks don't form three-in-a-row