Coding - Tic-Tac-Toe Game (M x N Board with Configurable Win Condition)

Coding - Tic-Tac-Toe Game (M x N Board with Configurable Win Condition)

Problem Description

Design and implement a Tic-Tac-Toe game class with the following specifications:

Requirements

• Board Configuration:

  • The board is M x N (not necessarily square).
  • Win condition requires K consecutive marks in a row, column, or diagonal.

• Class Structure:

  • The game should support two players, X and O, taking turns.
  • The game should be able to handle invalid moves and determine the winner.

Examples

1. Input:

   • TicTacToe game = new TicTacToe(3, 3, 3);
   • game.move(0, 0, 1); (Player 1 places an X at (0, 0))
   • game.move(0, 2, 2); (Player 2 places an O at (0, 2))
   • game.move(2, 2, 1); (Player 1 places an X at (2, 2))
   • game.move(1, 1, 2); (Player 2 places an O at (1, 1))
   • game.move(2, 0, 1); (Player 1 places an X at (2, 0))
   • game.move(1, 0, 2); (Player 2 places an O at (1, 0))
   • game.move(2, 1, 1); (Player 1 places an X at (2, 1))

2. Output:

   • game.getWinner() should return 1 (Player 1 wins)

Constraints

• 1 <= M, N <= 20
• 1 <= K <= min(M, N)
• K <= M * N
• 0 <= row, col, player <= 0
• row and col are within the board size (M x N)
• player is either 1 or 2

Hints

1. Board Representation:

   • Use a 2D array or matrix to represent the board.
   • Initialize the board with empty spaces.

2. Move Validation:

   • Check if the move is within the board boundaries.
   • Ensure the cell is empty before placing a mark.

3. Winning Condition:

   • Check for K consecutive marks in all possible directions (rows, columns, and diagonals).
   • Use nested loops or recursive functions to check for consecutive marks.

4. Game State:

   • Keep track of the current player and the number of moves.
   • Determine the winner or if the game is a draw.

Solution

class TicTacToe:
    def __init__(self, n: int, m: int, k: int):
        self.board = [[0] * m for _ in range(n)]
        self.n = n
        self.m = m
        self.k = k

    def move(self, row: int, col: int, player: int) -> bool:
        if self.board[row][col] != 0 or not (0 <= row < self.n) or not (0 <= col < self.m):
            return False
        self.board[row][col] = player
        return self.check_win(player)

    def check_win(self, player: int) -> bool:
        for i in range(self.n):
            for j in range(self.m - self.k + 1):
                if all(self.board[i][j + x] == player for x in range(self.k)):
                    return True
                if all(self.board[j + x][i] == player for x in range(self.k)):
                    return True
        for i in range(self.n - self.k + 1):
            for j in range(self.m - self.k + 1):
                if all(self.board[i + x][j + x] == player for x in range(self.k)):
                    return True
                if all(self.board[i + x][j + self.k - 1 - x] == player for x in range(self.k)):
                    return True
        return False

    def getWinner(self) -> int:
        for i in range(self.n):
            for j in range(self.m):
                if self.board[i][j] == 0:
                    return 0
        for i in range(self.n):
            for j in range(self.m - self.k + 1):
                if all(self.board[i][j + x] == self.board[i][j] for x in range(1, self.k)):
                    return self.board[i