Design Tic-Tac-Toe
Understand and solve the interview question "Design Tic-Tac-Toe."
We'll cover the following...
Description
Suppose that two players are playing a game of tic-tac-toe on an n x n board. They are 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
nof their marks in a horizontal, vertical, or diagonal row wins the game.
Your task is to implement a TicTacToe class, which will be used by two players to play the game and win fairly.
Given the 2D array containing the inputs for the TicTacToe object and the move function, you have to implement the TicTacToe class.
Assume that you have the following input array:
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Here, the first index of the 2D array is the input for the TicTacToe object and the rest of the indexes will be used as input for the move function.
Let’s look at the illustration of how the TicTacToe class will use the inputs given below.
Keep in mind the following functionalities that need to be implemented:
TicTacToe, which declares an object to create the board.- Constructor, which initializes the object of
TicTacToeto create the board of sizen. move(row: Int, col: Int, player: Int), which indicates that the player with IDplayerplays at the cell(row, col)of the board. The move is guaranteed to be a valid move.
Constraints:
-
2 <=
n<= 100 -
The
playershould be either1or2. -
0 <=
row,col<n -
Every call to
move()will be with a uniquerow,colcombination. -
The
movefunction will be called at most times.
Coding exercise
class TicTacToe(val n: Int){// Write code heredef move(row: Int, col: Int, player: Int): Int = -1}
Solution
While playing tic-tac-toe, we must find if the player has won. A player can win by marking an entire row, column, diagonal, or anti-diagonal cells. We can solve this problem in a constant time.
Let’s break the problem into two parts.
-
First, if there are
nrows andncolumns on a board, at each move, we must check if the player has already marked all of the cells in a row or column, that is, the certain row or column is markedntimes. -
Second, we must check if the player marked all the cells on the diagonal or anti-diagonal on every move. There can only be one diagonal and one anti-diagonal, no matter what the size of the board is.
From the ...