TLDR: Designing Tic Tac Toe isn't just about a 3x3 grid. A good design handles $N \times N$ boards, multiple players, and different winning strategies. We use the Factory Pattern to create pieces and an Optimized Algorithm to check for winners in $O(1)$ time.

---

1. The Problem Statement (The "No-Jargon" Explanation)

You know the game.

1. The Board: A 3x3 grid.

2. The Players: X and O.

3. The Goal: Get 3 in a row (Horizontal, Vertical, or Diagonal).

But in a System Design interview, the interviewer will ask: "What if the board is 100x100? What if there are 3 players? What if you need 5 in a row to win?" Hardcoding if (grid[0][0] == 'X' && grid[0][1] == 'X'...) won't work.

---

2. Core Entities & Relationships

We need to decouple the pieces from the board and the game logic.

Visualizing the Architecture

classDiagram
    class Game {
        -Board board
        -List~Player~ players
        -int currentPlayerIndex
        +startGame()
        +makeMove(row, col)
    }
    class Board {
        -int size
        -Piece[][] grid
        +addPiece(row, col, piece)
    }
    class Player {
        -String name
        -PlayingPiece piece
    }
    class PlayingPiece {
        -PieceType type
    }

    Game *-- Board
    Game o-- Player
    Player --> PlayingPiece

A. Playing Piece (The "What")

We use an Enum for the piece type (X, O, $, #) but wrap it in a class to allow extensibility.

enum PieceType { X, O }

class PlayingPiece {
    PieceType type;
    public PlayingPiece(PieceType type) { this.type = type; }
}

class PlayingPieceX extends PlayingPiece {
    public PlayingPieceX() { super(PieceType.X); }
}

B. Board (The "Where")

The board holds the state. It shouldn't know who is playing, just what is on it.

class Board {
    int size;
    PlayingPiece[][] grid;

    public Board(int size) {
        this.size = size;
        this.grid = new PlayingPiece[size][size];
    }

    public boolean addPiece(int row, int col, PlayingPiece piece) {
        if(grid[row][col] != null) return false;
        grid[row][col] = piece;
        return true;
    }
}

C. Player (The "Who")

class Player {
    String name;
    PlayingPiece playingPiece;

    public Player(String name, PlayingPiece playingPiece) {
        this.name = name;
        this.playingPiece = playingPiece;
    }
}

---

3. Deep Dive: The Winning Algorithm ($O(1)$ Check)

The naive approach is to traverse the whole row/column after every move to check for a win. That is $O(N)$. If $N=1000$, that's slow.

We can optimize this to $O(1)$ by keeping running counts.

The Strategy: For a 3x3 board, we need:

• Array rows[3]

• Array cols[3]

• Variable diag

• Variable antiDiag

The Logic:

• Player 1 (X) adds +1.

• Player 2 (O) adds -1.

• If any value in the arrays reaches +3 (Size) or -3 (-Size), that player wins.

Toy Dataset: 3x3 Board Player X (+1) vs Player O (-1). Target = 3.

Move	Player	Position (r, c)	rows[] State	cols[] State	Diag	Result
1	X	(0, 0)	[1, 0, 0]	[1, 0, 0]	1	Continue
2	O	(1, 1)	[1, -1, 0]	[1, -1, 0]	0	Continue
3	X	(0, 1)	[1, -1, 0]	[1, 0, 0]	0	Continue
...	...	...	...	...	...	...
5	X	(0, 2)	[3, -1, 0]	...	...	X Wins!

The Math: Win Condition:|count|==N

The Code:

class TicTacToeGame {
    int[] rows;
    int[] cols;
    int diag = 0;
    int antiDiag = 0;
    int n;

    public TicTacToeGame(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
    }

    public int move(int row, int col, int player) {
        int toAdd = (player == 1) ? 1 : -1;

        rows[row] += toAdd;
        cols[col] += toAdd;

        if (row == col) diag += toAdd;
        if (row == (n - 1 - col)) antiDiag += toAdd;

        if (Math.abs(rows[row]) == n || 
            Math.abs(cols[col]) == n || 
            Math.abs(diag) == n || 
            Math.abs(antiDiag) == n) {
            return player; // Winner
        }
        return 0; // No winner yet
    }
}

---

4. Handling Scalability & Extensibility

A. Undo Feature (Command Pattern)

If we want to allow "Undo", we shouldn't just update the board directly. We should wrap every move in a Command object.

• Command.execute(): Places the piece.

• Command.undo(): Removes the piece. We store a Stack<Command> history.

B. Different Winning Strategies (Strategy Pattern)

What if we want a rule where "Corners count as 2 points"? We create a WinningStrategy interface.

• NormalWinningStrategy

• CornerWinningStrategy

---

5. System Design: API & Database

If this were an online multiplayer game:

API Design (REST/WebSocket)

Method	Endpoint	Description
POST	/api/v1/games	Create a new game room.
POST	/api/v1/games/{id}/join	Join an existing game.
WS	/ws/games/{id}	WebSocket for real-time moves.

Database Schema (NoSQL)

Since game state is transient and we need fast writes, a NoSQL DB (like DynamoDB or Redis) is good.

Table: Games

• game_id (PK), player1_id, player2_id, board_state (JSON), status (IN_PROGRESS/FINISHED), winner_id

---

6. CI/CD & Deployment

1. Unit Tests: Test the $O(1)$ winning logic with edge cases (diagonals, full board draw).

2. Deployment: Deploy the WebSocket server on Kubernetes with a Load Balancer that supports sticky sessions (so players stay connected to the same game server).

---

Summary & Key Takeaways

• Separation of Concerns: Board holds data, Game holds logic, Player holds identity.

• Optimization: Don't scan the board. Use frequency arrays to check wins in $O(1)$.

• Extensibility: Use the Command Pattern for Undo/Redo functionality.

Future Proofing: This design supports any board size ($N$) and any number of players ($P$) just by changing the constructor parameters.

---

Practice Quiz: Test Your Design Skills

Click to expand Quiz

1. Scenario: You are designing a Tic Tac Toe game for a 1,000,000 x 1,000,000 board. Storing the full 2D array in memory is too expensive. Most of the board is empty. What data structure should you use for the Board?

   • A) int[][]
   • B) ArrayList>
   • C) HashMap (Key = "row,col")

2. Scenario: In the $O(1)$ winning algorithm, why do we use +1 for Player A and -1 for Player B?

   • A) To save memory.
   • B) So that their moves cancel each other out. If a row has one X (+1) and one O (-1), the sum is 0, correctly indicating no one dominates that row.
   • C) It is required by the Java compiler.

3. Scenario: Which Design Pattern is best suited for creating different types of games (e.g., "Standard TicTacToe" vs "3-Player TicTacToe")?

   • A) Singleton Pattern
   • B) Factory Pattern
   • C) Observer Pattern

(Answers: 1-C, 2-B, 3-B)