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.

Alan Xiang's Blog

LeetCode 794. Valid Tic-Tac-Toe State

Description:

Note:

Example:

Solution: