Design Tic-Tac-Toe

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
11 upvotes
Asked in companies
AmazonUberAdobe

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3
5
0 0 1
1 0 2
0 1 1
1 1 2
0 2 1
Sample Output 1:
Player 1 wins

Explanation for Sample Output 1:

In test case 1, The tic-tac-toe  board is of size 3 x 3.


After the final query move function returns 1, it means Player 1 wins the game.
Sample Input 2:
1
3
9
0 0 1
0 2 2
2 0 1
1 0 2
2 1 1
2 2 2
1 2 1
1 1 2
0 1 1
Sample Output 2:
Draw

Explanation for Sample Output 2:

In test case 1, The tic-tac-toe board is of size 3x3.


After the final query move function returns 0, it means the game ends in a draw.
Hint

Think of the Brute Force Approach by checking the row and column of the move added.

Approaches (2)
Brute Force

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:

 

  1. We declare an array/list ‘TIC_TAC_TOE’ of size ‘N’ * ‘N’ in which we store ‘X’ or ‘O’.
  2. We make a move:
    • Fill ‘X’ or ‘O’ in the ‘TIC_TAC_TOE’ grid with respect to the player.
  3. 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’.
  4. Finally, return 0.
Time Complexity

O(N ^ 3), Where ‘N’ represents the size of ‘N’ * ‘N’ Tic_Tac_Toe grid.

 

Since we are making a move or placing a ‘X’ or ‘O’ with respect to the player on the ‘TIC_TAC_TOE’ grid, we are checking if the current player has successfully placed 'N' of their marks in a horizontal, vertical, or diagonal row. 

 

Hence the overall time complexity is O(N ^ 3) because we have at most ‘N’ ^ 2 queries in the worst case when the game ends in a draw and for each query we are doing O(N) operations for checking if the current player is won or not.

Space Complexity

O(N ^ 2), Where ‘N’ represents the size of ‘N’ * ‘N’ TIC_TAC_TOE grid.

 

Since for checking if the current player has successfully placed 'N' of their marks in a horizontal, vertical, or diagonal row we are using an array/list ‘TIC_TAC_TOE’ of size ‘N’ * ‘N’. Hence, the space complexity is O(N ^ 2).

Code Solution
(100% EXP penalty)
Design Tic-Tac-Toe
Full screen
Console