Check Validity of Tic-Tac-Toe Board

Statement

Given a tic-tac-toe board as an array of strings. Return true if and only if it is possible to reach this board state during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array that consists of characters space ( ), X, and O where the space character represents an empty square.

Following are the rules of the game:

• Players take turns putting their characters in the blank squares ( ).
• The first player always places the X characters, while the second player always places the O characters.
• When either X or O occupies three consecutive places in any row, column, or diagonal, that player wins, and the game is over.
• The game also ends if all squares are non-empty.
• If the game is over, neither player can take any more moves.

Examples

Example 1

The following board is an example of a valid tic-tac-toe board:

Sample input

...