Tic Tac Toe

116.TicTacToe

Design

Simulation

Problem Statement:

Design a class to simulate a TicTacToe game. The class should support the following operations:

• TicTacToe(int n): Initializes the game board of size n × n.
• int move(int row, int col, int player): Indicates that the player with ID player (1 or 2) plays at cell (row, col). Returns:
  • 0: If no one wins.
  • 1: If player 1 wins.
  • 2: If player 2 wins.

Algorithm:

1. Use arrays to track the state of rows, columns, and diagonals:
   • rows[row]: Tracks the sum of moves for each row.
   • cols[col]: Tracks the sum of moves for each column.
   • diag: Tracks the sum of moves for the main diagonal.
   • diag2: Tracks the sum of moves for the anti-diagonal.
2. For each move:
   • Update the corresponding row, column, and diagonals based on the player's ID.
   • Check if any row, column, or diagonal sums to n (player 1 wins) or -n (player 2 wins).
3. If no win condition is met, return 0.

Complexity:

Time: O(1) per move | Space: O(n) for arrays tracking rows, columns, and diagonals.

Java Implementation:

public class TicTacToe {

    int[] rows, cols;
    int diag, diag2;
    int n;

    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        diag = diag2 = 0;
        this.n = n;
    }

    public int move(int row, int col, int player) {
        int k = (player == 1) ? 1 : -1;
        rows[row] += k;
        cols[col] += k;

        if (row == col) diag += k; // Main diagonal
        if (row + col == n - 1) diag2 += k; // Anti-diagonal

        if (rows[row] == n || rows[row] == -n || 
            cols[col] == n || cols[col] == -n || 
            diag == n || diag == -n || 
            diag2 == n || diag2 == -n) {
            return player; // Player wins
        }

        return 0; // No winner
    }
}
                

Python Implementation:

class TicTacToe:

    def __init__(self, n):
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.diag2 = 0
        self.n = n

    def move(self, row, col, player):
        k = 1 if player == 1 else -1
        self.rows[row] += k
        self.cols[col] += k

        if row == col:
            self.diag += k
        if row + col == self.n - 1:
            self.diag2 += k

        if (abs(self.rows[row]) == self.n or
            abs(self.cols[col]) == self.n or
            abs(self.diag) == self.n or
            abs(self.diag2) == self.n):
            return player

        return 0
                

C++ Implementation:

class TicTacToe {
    vector rows, cols;
    int diag, diag2, n;

public:
    TicTacToe(int n) : rows(n, 0), cols(n, 0), diag(0), diag2(0), n(n) {}

    int move(int row, int col, int player) {
        int k = (player == 1) ? 1 : -1;
        rows[row] += k;
        cols[col] += k;

        if (row == col) diag += k;
        if (row + col == n - 1) diag2 += k;

        if (abs(rows[row]) == n || abs(cols[col]) == n || 
            abs(diag) == n || abs(diag2) == n) {
            return player;
        }

        return 0;
    }
};