Grokking the Coding Interview Patterns in C#/

...

/

Solution: Design Tic-Tac-Toe

Solution: Design Tic-Tac-Toe

Let's solve the Design Tic-Tac-Toe problem using the Knowing What to Track pattern.

We'll cover the following...

Statement

Suppose that two players are playing a tic-tac-toe game on an n×nn \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 nn 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×nn \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 00 if no one wins.

Constraints:

  • 2≤n≤92 \leq n \leq 9

  • player should be either 1 or 2.

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

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

  • The Move() function will be called at most n2n^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
...
Access this course and 1400+ top-rated courses and projects.