Design Tic-Tac-Toe Game - Google Low Level Design Interview Question

This is system design question asked in interview for low level design implementation of Tic-tac-toe.

Design a Tic-tac-toe game that is played between two players on a n x n grid.

A move is guaranteed to be valid, and a valid move is one placed on an empty block in the grid. A player who succeeds in placing n of their marks in a horizontal, diagonal, or vertical row wins the game. Once a winning condition is reached, the game ends and no more moves are allowed. Below is an example game which ends in a winning condition.

Form the design perspective it is very broad question. before we look at solution, first understand game conditions:

Given n = 3, assume that player 1 is "X" and player 2 is "O" 
board = TicTacToe(3);

board.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

board.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

board.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

board.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

board.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

board.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

board.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

I have covered coding part for design & it' not the best description for this problem but i try my best here so that it can be helpful to someone.

So basic solution is to :

Construct an n*n grid, and check whether the row/column/diagonal line of the chess pieces are connected to a line each time a chess is played. The condition of the check is to calculate whether the number of row/column/diagonal piece marks is equal to n.

class TicTacToe(object):
    def __init__(self, n):
        self.grid = [[' '] * n for i in range(n)]

    def move(self, row, col, player):
        # Player {player} makes a move at ({row}, {col}).
        if player == 1:
            mark = 'X'
        else:
            mark = 'O'

        self.grid[row][col] = mark
        # check winnign condition
        # check if row has the same mark
        n = len(self.grid)
        sumOfRow = sum([self.grid[row][c] == mark for c in range(n)])
        sumOfCol = sum([self.grid[r][col] == mark for r in range(n)])
        sumOfLeftDiagonal = sum([self.grid[i][i] == mark for i in range(n)])
        sumOfRightDiagonal = sum(
            [self.grid[i][n - 1 - i] == mark for i in range(n)])

        if sumOfCol == n or sumOfRow == n or sumOfRightDiagonal == n or sumOfLeftDiagonal == n:
            return player
        else:
            return 0

# Driver code

board = TicTacToe(3)        # Given n = 3
board.move(0, 0, 1)
board.move(0, 2, 2)
board.move(2, 2, 1)
board.move(1, 1, 2)
board.move(2, 0, 1)
board.move(1, 0, 2)
print(board.move(2, 1, 1))
# 1  Result 1 as a winner

Here we can improved over solution 1 given above without creating a grid.

No need to create a grid, just record the value of each row, column and two diagonals. For each chess game, the chess assignment for player 1 is 1, and the chess assignment for player 2 is -1. Then we only need to check whether the value of the current row/column/diagonal is equal to n or -n.

# Solution 2  (Without creating a grid):

class TicTacToe(object):
    def __init__(self, n):
        self.row = [0] * n
        self.col = [0] * n
        self.diag = 0
        self.xdiag = 0
        self.n = n

# function to check moves of player 1 & player 2
    def move(self, row, col, player):
        if player == 1:
            count = 1
        else:
            count = -1

# Record the value of each row, column and two diagonals.
        self.row[row] += count
        self.col[col] += count
        if row == col:
            self.diag += count
        if row + col == self.n - 1:
            self.xdiag += count

        if self.n in [self.row[row], self.col[col], self.diag, self.xdiag]:
            return 1
        if -self.n in [self.row[row], self.col[col], self.diag, self.xdiag]:
            return 2
        return 0

# Driver code

board = TicTacToe(3)        # Given n = 3
board.move(0, 0, 1)
board.move(0, 2, 2)
board.move(2, 2, 1)
board.move(1, 1, 2)
board.move(2, 0, 1)
board.move(1, 0, 2)
print(board.move(2, 1, 1))
# 1  Result 1 as a winner

If you like this article then please share this...