# LeetCode 794. Valid Tic-Tac-Toe State

## Description:

A Tic-Tac-Toe board is given 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 3x3 array, and 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 3 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.

## Note:

• board is a length-3 array of strings, where each string board[i] has length 3.
• Each board[i][j] is a character in the set {“ “, “X”, “O”}.

## Example:

input:

[“XOX”, ” X “, ” “]

output:

false

explanation:

Players take turns making moves.

input:

[“XXX”, ” “, “OOO”]

output:

false

input:

[“XOX”, “O O”, “XOX”]

output:

true

## Solution:

def Identity(pos):
return pos

def Transpose(pos):
return pos[1], pos[0]

def Cross(pos):
return 2-pos[0], pos[1]

def CountBoard(board):
count_X = 0
count_O = 0
for i in range(3):
for j in range(3):
if board[i][j] == 'X':
count_X += 1
elif board[i][j] == 'O':
count_O += 1
return count_X, count_O

def FindWinner(board):
lineTrans = [Identity, Transpose]
diagTrans = [Identity, Cross]
winStrings = ['X', 'O']
# find out if X wins at first

for winStr in winStrings:
for mId in range(2):
# horizontal and vertical check
for i in range(3):
found = True
for j in range(3):
pos = lineTrans[mId]((i,j))
if board[pos[0]][pos[1]] != winStr:
found = False
break
if found:
return winStr

# diagonal check
found = True
for i in range(3):
pos = diagTrans[mId]((i,i))
if board[pos[0]][pos[1]] != winStr:
found = False
break
if found:
return winStr

return None

class Solution:

def validTicTacToe(self, board):
"""
:type board: List[str]
:rtype: bool
"""

count_X, count_O = CountBoard(board)
winner = FindWinner(board)
print(winner)

# if there is a winner
if winner is None:
return count_X == count_O + 1 or count_X == count_O
elif winner == 'X':
return count_X == count_O + 1
elif winner == 'O':
return count_X == count_O


The logic of Tic-Tac-Toe is simple. We use $$\lvert X\rvert$$ and $$\lvert O\rvert$$ to denote the number of $$X$$‘s and number of $$O$$‘s on the board , respectively. If X wins, then $$\lvert X\rvert = \lvert O\rvert + 1$$ should hold, because $$X$$ plays first. If $$O$$ wins, then $$\lvert X\rvert = \lvert O\rvert$$ should hold. If no one is winning, then either $$\lvert X\rvert = \lvert O\rvert + 1$$ or $$\lvert X\rvert = \lvert O\rvert$$ should hold.

P.S. This is the first LeetCode post after I arrived at Syracuse. Today is truly a day that is worth memorizing.