# LeetCode 794. Valid Tic-Tac-Toe State

19 Aug 2018## 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.