# 348 Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on anxngrid.
You may assume the following rules:
1. 1.
A move is guaranteed to be valid and is placed on an empty block.
2. 2.
Once a winning condition is reached, no more moves is allowed.
3. 3.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up: Could you do better than O(n^2) per`move()`operation?
The Idea: The primary challenge about this problem is to achieve an O(n) move operation (as opposed to naively scanning through the matrix every time.) To achieve this, want we do is only validate the row, col and diagonal (if applicable) on the coordinate a move that the player made. This works because even previous move was a non-winning move and a winning move could only come from having made the current move.
Complexity: O(4n) move operation, and O(1) extra space
class TicTacToe:
def __init__(self, n):
"""
:type n: int
"""
self.board = [[0 for _ in range(n)] for _ in range(n)]
self.n = n
def validate_row(self, row, player):
for cell in self.board[row]:
if cell != player:
return False
return True
def validate_col(self, col, player):
for row in range(0, self.n):
if self.board[row][col] != player:
return False
return True
def is_diagonal(self, row, col):
return row == col or row + col == self.n - 1
def validate_diagonal(self, player):
y_neg_x = True
for d in range(0, self.n):
if self.board[d][d] != player:
y_neg_x = False
break
y_x = True
for i, j in zip(range(self.n - 1, -1, -1), range(0, self.n)):
if self.board[i][j] != player:
y_x = False
break
return y_x or y_neg_x
def move(self, row, col, player):
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
:type row: int
:type col: int
:type player: int
:rtype: int
"""
self.board[row][col] = player
if self.validate_row(row, player) or self.validate_col(col, player):
return player
elif self.is_diagonal(row, col) and self.validate_diagonal(player):
return player
else:
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
obj1 = TicTacToe(2)
print(obj1.move(0,1,1))
print(obj1.move(1,1,2))
print(obj1.move(1,0,1))
obj2 = TicTacToe(3)
print(obj2.move(0,0,1))
print(obj2.move(0,2,2))
print(obj2.move(2,2,1))
print(obj2.move(1,1,2))
print(obj2.move(2,0,1))
print(obj2.move(1,0,2))
print(obj2.move(2,1,1))