Solution: Design Tic-Tac-Toe

Statement

Suppose that two players are playing a tic-tac-toe game on an $n \times n$ board. They’re following specific rules to play and win the game:

• A move is guaranteed to be valid if a mark is placed on an empty block.
• No more moves are allowed once a winning condition is reached.
• A player who succeeds in placing $n$ of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement a TicTacToe class, which will be used by two players to play the game and win fairly.

Keep in mind the following functionalities that need to be implemented:

• Constructor, the constructor, which initializes an object of TicTacToe, allowing the players to play on a board of size $n \times n$.
• Move(row, col, player) indicates that the player with the ID, player, places their mark on the cell (row, col). The move is guaranteed to be a valid move. At each move, this function returns the player ID if the current player wins and returns $0$ if no one wins.

Constraints:

• $2 \leq n \leq 9$

• player should be either 1 or 2.

• $0 \leq$ row, col $< n$

• Every call to Move() will be with a unique row, col combination.

• The Move() function will be called at most $n^2$ times.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach to this problem is to check, after every move, whether the current player has won the game. Either player can win the game if the following conditions are met:

• They are able to mark an entire row.
• They are able to mark an entire column.
• They are able to mark all the cells of one of the two diagonals.

We mark the cell identified by the given row and column indexes with the current player’s marker. Then, we check the following conditions to determine whether the current player wins:

1. Check the current row to see whether the rest of the cells in the row are also occupied by the current player.
2. Check the current column to see whether the rest of the cells in the column are also occupied by the current player.
3. In case the current cell is on one of the diagonals, check to see whether the rest of the cells in that diagonal are also occupied by the current player.

After every move, we iterated up to four times over $n$ cells to check for each condition, row, column, diagonal (top-left to bottom-right corner), and anti-diagonal (top-right to bottom-left corner). Therefore, the time complexity is $O(n)$. The space complexity of this naive approach is $O(n^2)$, because we are using a board of size $n \times n$.

Let’s see if we can use the mark-counting technique to reduce the time and space complexity of our solution.

Optimized approach using mark counting

The following are the three kinds of win scenarios in tic-tac-toe:

• Player 1 wins
• Player 2 wins
• No player wins

A player can win by marking all the cells in a row or a column, or along the diagonal, or, along the anti-diagonal. To identify whether either of the two players wins or if it’s a tie between the two players, we can efficiently count the marks made on the tic-tac-toe board.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The constructor creates two arrays, rows and cols, each of size $n$, and initializes both arrays with 0. These arrays are used to count marks placed in a particular row and column.