Last Updated: 20 Mar, 2021
Design Tic-Tac-Toe
Moderate
Asked in companies
Ninja has to design a 2 players game Tic-Tac-Toe played on an ‘N’ * ‘N’ grid.
Ninja has to assume the following rules while playing the game:
This game is played between two people (Player 1 and Player 2). Player 1 chooses ‘X' and Player 2 chooses ‘O’ to mark their cells. A move is guaranteed to be valid and is placed on an empty block.
A player who successfully places 'N' of their marks in a horizontal, vertical, or diagonal row wins the game. Once a winning condition is reached, no more moves are allowed.
As Ninja is busy planning his strategy, he asks you for help. Your task is to complete the function ‘move(row, col, player)’ where ‘row’ and ‘col’ represent the current row and column of the grid ‘player’ P (either 1 or 2) chooses to place his sign.
The function must return an integer which is either 0, 1, and 2 representing:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
Example:
Let us assume if ‘N’ = 3 and player 1 places ‘X’ and player 2 places ‘O’ on the board.
Input Format
The first line of input contains an integer ‘T’ which denotes the number of test cases.
The first line of each test case contains an integer ‘N’ that represents the size of the ‘N’ * ‘N’ grid.
The next line of each test case contains an integer ‘Q’ that represents the number of queries.
The next ‘Q’ lines of each test case contain three single space-separated integers ‘ROW’, ‘COL’, and ‘PLAYER’ representing the current row and column of the grid and the current player (1 or 2).
Output Format :
For each test case, Ninja has to complete the function ‘move’ and return either 0, 1, and 2.
Print the output of each test case in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= ‘N’ <= 100
5 <= ‘Q’ <= ‘N*N’
0 <= ‘ROW’ , ‘COL’ < ‘N’
‘PLAYER’ = {1, 2}
Where ‘ROW’ and ‘COL’ represent the current row and column of the grid and ‘PLAYER’ represents the current player.
Time Limit: 1 sec
Approaches
In this approach first, we make a move or place an ‘X’ or ‘O’ with respect to the player on the ‘TIC_TAC_TOE’ grid and then check if the current player wins or not.
The steps are as follows:
- We declare an array/list ‘TIC_TAC_TOE’ of size ‘N’ * ‘N’ in which we store ‘X’ or ‘O’.
- We make a move:
- Fill ‘X’ or ‘O’ in the ‘TIC_TAC_TOE’ grid with respect to the player.
- Then we check if the current player has successfully placed 'N' of their marks in a horizontal, vertical, or diagonal row.
- He wins the game.
- Return ‘PLAYER’.
- Finally, return 0.
We can optimise our above approach. We know all moves are guaranteed to be valid. So we do not need to keep track of an entire ‘TIC_TAC_TOE’ grid. We declare two arrays/lists ‘ROWS’ and ‘COLS’ in which we store count of moves of both players in each row and column of the ‘TIC_TAC_TOE’ grid. If at any time the count of the current player is equal to ‘N’ then that player has won.
The steps are as follows:
- We declare two arrays/lists ‘ROWS’ and ‘COLS’ in which we store count of moves of both players in each row and column of the ‘TIC_TAC_TOE’ grid.
- First, we increase the count for the row and column if the current player is 1 and decrease the count by 1 if the current player is 2.
- If the count for the row or column is ‘N’:
- Player 1 won.
- Return 1.
- If the count for the row or column is -1 * ‘N’:
- Player 2 won.
- Return 1.
- If the count for the row or column is ‘N’:
- Finally, return 0.