📌 1. Problem Statement

Design a Tic Tac Toe game that:

Supports configurable board size (N × N)
Supports 2 players
Validates moves
Detects win efficiently
Detects draw
Logs moves
Is extensible (AI, multiplayer, new win strategies)
Uses proper design patterns
Is written in C++ (single-threaded)

📌 2. Functional Requirements

Core Features

Create game with size N
Add 2 players
Players make alternate moves
Validate moves
Detect winner
Detect draw
Display result
Log game events
Allow restart (extensible)

📌 3. Non-Functional Requirements

Clean architecture
O(1) win detection
Extensible strategy
Easy to add AI
Maintainable code
Testable components

📌 4. High-Level Architecture

Game
 ├── Board
 │     └── Cell
 ├── Player
 ├── WinningStrategy
 ├── Logger
 └── GameState

📌 5. Design Patterns Used (With Clear Reasoning)

Pattern	Where Used	Why Used
Strategy	Winning algorithm	Switch win logic easily
Factory Method	Player creation	Encapsulate object creation
Singleton	Logger	One global logger
Observer	Logging system	Notify events
Decorator	AI Player	Add behavior dynamically
Builder	Game construction	Clean configuration
Command	Move execution	Encapsulate actions
State	Game lifecycle	Manage transitions
Template Method	Winning base class	Standard win-check structure

📌 6. Algorithms Used

🟢 1. O(1) Winning Algorithm (Optimized)

Instead of scanning entire board after every move (O(n²)):

We maintain:

rowCount[n]
colCount[n]
diag
antiDiag

For Player X → +1 For Player O → -1

If:

abs(rowCount[i]) == n
OR abs(colCount[i]) == n
OR abs(diag) == n
OR abs(antiDiag) == n

→ Winner found

Complexity:

Move: O(1)
Win check: O(1)

🟢 2. Move Validation

Check bounds
Check if cell empty

Complexity: O(1)

🟢 3. Draw Detection

if totalMoves == n*n

📌 7. Complete C++ Implementation

🔹 ENUMS

enum class Symbol { X = 1, O = -1 };
enum class GameStatus { IN_PROGRESS, DRAW, WIN };

🔹 Observer Pattern

class Observer {
public:
    virtual void update(string message) = 0;
    virtual ~Observer() {}
};

🔹 Singleton Logger

class Logger : public Observer {
private:
    Logger() {}
public:
    static Logger& getInstance() {
        static Logger instance;
        return instance;
    }

    void update(string message) override {
        cout << "[LOG] " << message << endl;
    }
};

🔹 Cell Class

class Cell {
public:
    int row, col;
    Symbol* symbol;

    Cell(int r, int c) : row(r), col(c), symbol(nullptr) {}

    bool isEmpty() {
        return symbol == nullptr;
    }

    void setSymbol(Symbol* s) {
        symbol = s;
    }
};

🔹 Board Class

class Board {
private:
    int size;
    vector<vector<Cell>> grid;

public:
    Board(int n) : size(n) {
        for(int i=0;i<n;i++) {
            vector<Cell> row;
            for(int j=0;j<n;j++)
                row.emplace_back(i,j);
            grid.push_back(row);
        }
    }

    int getSize() { return size; }

    bool placeMove(int r, int c, Symbol* s) {
        if(r<0 || c<0 || r>=size || c>=size)
            return false;
        if(!grid[r][c].isEmpty())
            return false;

        grid[r][c].setSymbol(s);
        return true;
    }
};

🔹 Strategy Pattern – Winning Strategy Base

class BaseWinningStrategy {
protected:
    int size;
public:
    BaseWinningStrategy(int n): size(n){}
    virtual bool checkWin(int row, int col, Symbol sym)=0;
    virtual ~BaseWinningStrategy(){}
};

🔹 Efficient Winning Strategy (O(1))

class EfficientWinningStrategy : public BaseWinningStrategy {
private:
    vector<int> rowCount;
    vector<int> colCount;
    int diag=0, antiDiag=0;

public:
    EfficientWinningStrategy(int n)
        : BaseWinningStrategy(n),
          rowCount(n,0), colCount(n,0) {}

    bool checkWin(int row, int col, Symbol sym) override {
        int val = (int)sym;

        rowCount[row]+=val;
        colCount[col]+=val;

        if(row==col) diag+=val;
        if(row+col==size-1) antiDiag+=val;

        if(abs(rowCount[row])==size ||
           abs(colCount[col])==size ||
           abs(diag)==size ||
           abs(antiDiag)==size)
            return true;

        return false;
    }
};

🔹 Factory Method – Player Creation

class Player {
protected:
    string name;
    Symbol symbol;

public:
    Player(string n, Symbol s): name(n), symbol(s){}
    virtual pair<int,int> makeMove()=0;
    Symbol getSymbol(){ return symbol; }
    string getName(){ return name; }
    virtual ~Player(){}
};

class HumanPlayer : public Player {
public:
    HumanPlayer(string n, Symbol s)
        : Player(n,s){}

    pair<int,int> makeMove() override {
        int r,c;
        cout<<"Enter row and col: ";
        cin>>r>>c;
        return {r,c};
    }
};

class PlayerFactory {
public:
    static shared_ptr<Player> createPlayer(
        string type, string name, Symbol s) {
        if(type=="HUMAN")
            return make_shared<HumanPlayer>(name,s);
        return nullptr;
    }
};

🔹 Decorator Pattern – AI Extension

class PlayerDecorator : public Player {
protected:
    shared_ptr<Player> player;
public:
    PlayerDecorator(shared_ptr<Player> p)
        : Player(p->getName(), p->getSymbol()),
          player(p) {}
};

class AIPlayerDecorator : public PlayerDecorator {
public:
    AIPlayerDecorator(shared_ptr<Player> p)
        : PlayerDecorator(p){}

    pair<int,int> makeMove() override {
        cout<<"AI making move...\n";
        return {0,0}; 
    }
};

🔹 Game Class

class Game {
private:
    Board board;
    shared_ptr<Player> p1;
    shared_ptr<Player> p2;
    shared_ptr<Player> current;
    unique_ptr<BaseWinningStrategy> strategy;
    GameStatus status;
    int moves=0;

public:
    Game(int n,
         shared_ptr<Player> pl1,
         shared_ptr<Player> pl2)
        : board(n), p1(pl1), p2(pl2),
          current(pl1),
          strategy(make_unique<EfficientWinningStrategy>(n)),
          status(GameStatus::IN_PROGRESS) {}

    void play() {

        while(status==GameStatus::IN_PROGRESS) {

            auto move=current->makeMove();
            bool placed=board.placeMove(
                move.first, move.second,
                &current->getSymbol());

            if(!placed){
                cout<<"Invalid Move\n";
                continue;
            }

            Logger::getInstance().update(
                current->getName()+" moved");

            moves++;

            if(strategy->checkWin(
                move.first, move.second,
                current->getSymbol())) {

                status=GameStatus::WIN;
                cout<<current->getName()<<" Wins!\n";
                break;
            }

            if(moves==board.getSize()*board.getSize()){
                status=GameStatus::DRAW;
                cout<<"Game Draw\n";
                break;
            }

            current=(current==p1? p2:p1);
        }
    }
};

🔹 Builder Pattern – Game Builder

class GameBuilder {
private:
    int size;
    shared_ptr<Player> p1;
    shared_ptr<Player> p2;

public:
    GameBuilder& setSize(int n){
        size=n;
        return *this;
    }

    GameBuilder& setPlayer1(shared_ptr<Player> pl){
        p1=pl;
        return *this;
    }

    GameBuilder& setPlayer2(shared_ptr<Player> pl){
        p2=pl;
        return *this;
    }

    unique_ptr<Game> build(){
        return make_unique<Game>(size,p1,p2);
    }
};

🔹 Main Function

int main(){

    auto player1=PlayerFactory::createPlayer(
        "HUMAN","Alice",Symbol::X);

    auto player2=PlayerFactory::createPlayer(
        "HUMAN","Bob",Symbol::O);

    auto game=GameBuilder()
                .setSize(3)
                .setPlayer1(player1)
                .setPlayer2(player2)
                .build();

    game->play();

    return 0;
}

📌 Complexity Analysis

Operation	Complexity
Move Placement	O(1)
Win Check	O(1)
Draw Check	O(1)
Space	O(n²)

🧵 Multithreading Problems in the Tic Tac Toe Implementation

Our current implementation is single-threaded and assumes:

Only one thread calls game->play()
Only one thread makes moves
No external UI thread
No AI thread
No logging concurrency

If we allow:

Multiple threads (UI thread + AI thread)
Network multiplayer
Async logging
Spectator updates

👉 The current design becomes unsafe.

Below is a complete breakdown of every multithreading issue and its proper fix.

🚨 PROBLEM 1: Race Condition on Board State

Where?

bool placeMove(int r, int c, Symbol* s)

Two threads:

Thread A: places move at (0,0) Thread B: places move at (0,0)

Both check:

if(!grid[r][c].isEmpty())

Both see empty Both write Result: corrupted state ❌

✅ Solution: covered in our course.

🚨 PROBLEM 2: Race Condition in Winning Strategy Counters

In EfficientWinningStrategy:

rowCount[row] += val;
colCount[col] += val;
diag += val;

Two threads updating simultaneously → lost updates.

Example:

Thread A: rowCount[0] = 1 Thread B: rowCount[0] = 1 Final: 1 (should be 2)

✅ Solution : covered in our course.

🚨 PROBLEM 3: Race Condition on `moves` Counter

In Game class:

moves++;

Two threads increment → lost update.

✅ Fix: covered in our course.

🚨 PROBLEM 4: Race Condition on `current` Player Switch

current = (current==p1? p2:p1);

If two threads call play logic:

Player may switch twice
Wrong turn execution
Inconsistent state

✅ Fix: covered in our course.

🚨 PROBLEM 5: Logger Output Interleaving

cout << "[LOG] ...";

Two threads log simultaneously:

Output becomes:

[LOG] Alice m[LOG] Bob moved
oved

✅ Fix: covered in our course.

🚨 PROBLEM 6: Deadlock Risk

If:

Board mutex
Strategy mutex
Game mutex

Are locked in different order across threads → deadlock.

✅ Fix: covered in our course.

🚨 PROBLEM 7: Check-Then-Act Race

Example:

if(!placed)
    continue;

if(strategy->checkWin(...))

If two threads process same turn → invalid.

✅ Fix: covered in our course.

🚨 PROBLEM 8: AI Thread vs Human Thread

If AI runs in separate thread:

Both may place move simultaneously
Breaks turn logic

✅ Solution: covered in our course.

🚨 PROBLEM 9: Memory Visibility Issue

Without synchronization:

Thread A updates board Thread B may not see updated state (CPU cache issue)

✅ Solution: covered in our course.

🚨 PROBLEM 10: Builder Not Thread-Safe

If multiple threads call:

GameBuilder builder;
builder.setSize(3);

Shared builder instance → race.

📌 1. Problem Statement

📌 2. Functional Requirements

Core Features

📌 3. Non-Functional Requirements

📌 4. High-Level Architecture

📌 5. Design Patterns Used (With Clear Reasoning)

📌 6. Algorithms Used

🟢 1. O(1) Winning Algorithm (Optimized)

Complexity:

🟢 2. Move Validation

🟢 3. Draw Detection

📌 7. Complete C++ Implementation

🔹 ENUMS

🔹 Observer Pattern

🔹 Singleton Logger

🔹 Cell Class

🔹 Board Class

🔹 Strategy Pattern – Winning Strategy Base

🔹 Efficient Winning Strategy (O(1))

🔹 Factory Method – Player Creation

🔹 Decorator Pattern – AI Extension

🔹 Game Class

🔹 Builder Pattern – Game Builder

🔹 Main Function

📌 Complexity Analysis

🧵 Multithreading Problems in the Tic Tac Toe Implementation

🚨 PROBLEM 1: Race Condition on Board State

Where?

✅ Solution: covered in our course.

🚨 PROBLEM 2: Race Condition in Winning Strategy Counters

✅ Solution : covered in our course.

🚨 PROBLEM 3: Race Condition on moves Counter

✅ Fix: covered in our course.

🚨 PROBLEM 4: Race Condition on current Player Switch

✅ Fix: covered in our course.

🚨 PROBLEM 5: Logger Output Interleaving

✅ Fix: covered in our course.

🚨 PROBLEM 6: Deadlock Risk

✅ Fix: covered in our course.

🚨 PROBLEM 7: Check-Then-Act Race

✅ Fix: covered in our course.

🚨 PROBLEM 8: AI Thread vs Human Thread

✅ Solution: covered in our course.

🚨 PROBLEM 9: Memory Visibility Issue

✅ Solution: covered in our course.

🚨 PROBLEM 10: Builder Not Thread-Safe

✅ Fix: covered in our course.

🚨 PROBLEM 3: Race Condition on `moves` Counter

🚨 PROBLEM 4: Race Condition on `current` Player Switch

Design (LLD) Tic Tac Toe - C++