Complete Tic-Tac-Toe System Design & Low-Level Design

This chapter covers the complete Low-Level Design (LLD) and object-oriented implementation of a classic Tic-Tac-Toe game. We will explore how to approach this problem in a high-pressure interview setting, establish a robust mental model, apply key design patterns (Strategy, State, Observer, and Factory), and write clean, extensible, production-ready code.

1. Why Do We Need This? (Problem Statement & Interview Context)

In top-tier technical interviews (such as those at Uber, Confluent, and other major tech firms), Tic-Tac-Toe is a highly popular LLD question. While the game rules are simple, the question is designed to evaluate how a candidate manages time as a currency and balances rapid implementation with clean, extensible, and decoupled code.

The core challenge is not just making the game work, but designing it so that future requirements—such as changing the board size, adding AI players, supporting multiple players, or adding event logging—can be integrated with minimal changes to existing classes (adhering to the Open-Closed Principle).

2. Core Mental Model & Real-World Analogy

To design a system effectively under pressure, start by enacting the game as a physical, real-world board game.

Real-Life Analogy

Imagine sitting across from an opponent with a physical wooden board, a bag of 'X' and 'O' pegs, and a referee watching over the game.

The referee sets up an empty $3 \times 3$ grid.

Player 1 (using 'X' pegs) chooses an empty coordinate and places a peg.

The referee validates that the coordinate is within bounds and not already occupied.

The referee checks if Player 1 has formed a straight line of three pegs (horizontally, vertically, or diagonally).

If yes, the referee halts the game and declares Player 1 the winner. If the board is full and no one has won, the referee declares a draw.

If the game continues, the referee prompts Player 2 (using 'O' pegs) to make a move.

Game Flow Workflow

Structure & Concept Flow

Referee sets up empty 3x3 board

Player 1 (X) chooses an empty coordinate (row, col)

Referee validates move -> Places 'X' peg on board

Referee checks for Win/Draw conditions

+---> Win/Draw detected? -> End Game & Announce Result

+---> No? -> Switch turn to Player 2 (O)

3. Clarifying Questions & Requirements Gathering

Before writing any code, you must clarify the scope with your interviewer. Use closed-ended questions to establish boundaries quickly:

Board Size: "Are we designing strictly for a standard $3 \times 3$ $3 \times 3$ board, or should the system support an $N \times N$ $N \times N$ grid?"
- Standard response: Start with $3 \times 3$ , but keep the design extensible for $N \times N$ .
Players: "Is this strictly a two-player game, or should we support multiple players ( $M$ $M$ players) with unique symbols?"
- Standard response: Two players for now, but design it to easily scale to $M$ players.
Player Types: "Are the players strictly human, or should we support automated AI players?"
- Standard response: Implement human players first, but allow AI players to be plugged in seamlessly.
Core Rules:
- A move is invalid if placed outside the grid or on an already occupied cell.
- The game ends immediately when a player wins (completes a row, column, or diagonal) or when the board is fully occupied (resulting in a draw).

4. Key Entities & Domain Modeling

Based on our mental model, we can extract the primary domain entities.

Entity	Responsibility	Key Attributes / Methods
`Symbol`	Represents the mark placed on the board.	Enum: `X`, `O`, `EMPTY`
`Board`	Manages the grid state, cell updates, and boundary/occupancy validations.	`grid`, `isMoveValid()`, `placeSymbol()`, `checkWin()`
`Player`	Represents a participant in the game.	`name`, `symbol`, `strategy`
`Game`	Orchestrates the game loop, turn switching, and overall state.	`board`, `players`, `currentPlayer`, `play()`

5. Architectural Design Patterns

To make our Tic-Tac-Toe system highly extensible, we can introduce several design patterns. In a 45-minute interview, prioritize them in this order:

Structure & Concept Flow

1. Strategy Pattern (High Priority - Decouples move logic for Human/AI)

2. Factory Pattern (Medium Priority - Instantiates players/strategies)

3. Observer Pattern (Medium Priority - Decouples game events from console output)

4. State Pattern (Low Priority - Manages turn-based transitions)

1. Strategy Pattern

Use Case: Decouples the player from how they make a move. A human player makes a move via console input, while an AI player makes a move using an algorithm (e.g., Minimax or random selection).
Benefit: Allows us to add new AI difficulty levels without modifying the Player class.

2. Factory Pattern

Use Case: Simplifies the creation of players and their associated strategies.
Benefit: Centralizes object creation logic.

3. Observer Pattern

Use Case: Notifies external listeners (such as a UI renderer, a game logger, or a notification service) whenever a move is made or the game state changes.
Benefit: Decouples core game logic from the presentation layer.

4. State Pattern

Use Case: Manages transitions between game states (e.g., XTurnState, OTurnState, XWinState, OWinState, DrawState).
Benefit: Eliminates complex conditional blocks (if/else) for state transitions, though it can sometimes be over-engineered for simple turn-based games.

6. Step-by-Step Implementation: Strategy & State Patterns

Let's implement the core interfaces and classes for the Strategy and State patterns in Java.

Position Helper Class

JAVA

public class Position {
    private final int row;
    private final int col;

    public Position(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int getRow() { return row; }
    public int getCol() { return col; }
}

Strategy Pattern: Player Move Strategy

JAVA

import java.util.Scanner;

// Strategy Interface
public interface PlayerStrategy {
    Position makeMove(Board board);
}

// Human Implementation
public class HumanPlayerStrategy implements PlayerStrategy {
    private final Scanner scanner = new Scanner(System.in);

    @Override
    public Position makeMove(Board board) {
        while (true) {
            System.out.print("Enter row and column (0-indexed, separated by space): ");
            if (scanner.hasNextInt()) {
                int row = scanner.nextInt();
                if (scanner.hasNextInt()) {
                    int col = scanner.nextInt();
                    Position pos = new Position(row, col);
                    if (board.isMoveValid(pos)) {
                        return pos;
                    }
                }
            }
            System.out.println("Invalid move on board! Try again.");
            scanner.nextLine(); // Clear buffer
        }
    }
}

// AI Implementation (Extensible Placeholder)
public class RandomAIPlayerStrategy implements PlayerStrategy {
    @Override
    public Position makeMove(Board board) {
        int size = board.getSize();
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                Position pos = new Position(r, c);
                if (board.isMoveValid(pos)) {
                    return pos; // Returns the first available empty cell
                }
            }
        }
        return null;
    }
}

State Pattern: Game States

JAVA

// State Interface
public interface GameState {
    void next(GameContext context);
    boolean isOver();
}

// Context Class
public class GameContext {
    private GameState currentState;

    public GameContext(GameState initialState) {
        this.currentState = initialState;
    }

    public GameState getCurrentState() {
        return currentState;
    }

    public void setCurrentState(GameState state) {
        this.currentState = state;
    }

    public void next() {
        currentState.next(this);
    }

    public boolean isGameOver() {
        return currentState.isOver();
    }
}

// Concrete Turn States
public class XTurnState implements GameState {
    @Override
    public void next(GameContext context) {
        context.setCurrentState(new OTurnState());
    }

    @Override
    public boolean isOver() { return false; }
}

public class OTurnState implements GameState {
    @Override
    public void next(GameContext context) {
        context.setCurrentState(new XTurnState());
    }

    @Override
    public boolean isOver() { return false; }
}

// Concrete Terminal States
public class GameWonState implements GameState {
    private final String winnerName;

    public GameWonState(String winnerName) {
        this.winnerName = winnerName;
    }

    @Override
    public void next(GameContext context) {
        // Terminal state: No transition
    }

    @Override
    public boolean isOver() { return true; }

    public String getWinnerName() { return winnerName; }
}

public class DrawState implements GameState {
    @Override
    public void next(GameContext context) {
        // Terminal state: No transition
    }

    @Override
    public boolean isOver() { return true; }
}

7. Step-by-Step Implementation: The Board & Game Logic

The Board class manages the grid state and checks for win or draw conditions.

JAVA

public enum Symbol {
    X, O, EMPTY
}

public class Board {
    private final int size;
    private final Symbol[][] grid;
    private int emptyCellsCount;

    public Board(int size) {
        this.size = size;
        this.grid = new Symbol[size][size];
        this.emptyCellsCount = size * size;
        initializeBoard();
    }

    private void initializeBoard() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                grid[i][j] = Symbol.EMPTY;
            }
        }
    }

    public int getSize() {
        return size;
    }

    public boolean isMoveValid(Position pos) {
        int r = pos.getRow();
        int c = pos.getCol();
        return r >= 0 && r < size && c >= 0 && c < size && grid[r][c] == Symbol.EMPTY;
    }

    public void placeSymbol(Position pos, Symbol symbol) {
        if (!isMoveValid(pos)) {
            throw new IllegalArgumentException("Illegal move attempted!");
        }
        grid[pos.getRow()][pos.getCol()] = symbol;
        emptyCellsCount--;
    }

    public boolean isFull() {
        return emptyCellsCount == 0;
    }

    // Checks if the last move resulted in a win
    public boolean checkWin(Position lastMove, Symbol symbol) {
        int row = lastMove.getRow();
        int col = lastMove.getCol();

        // 1. Check Row
        boolean rowWin = true;
        for (int c = 0; c < size; c++) {
            if (grid[row][c] != symbol) {
                rowWin = false;
                break;
            }
        }
        if (rowWin) return true;

        // 2. Check Column
        boolean colWin = true;
        for (int r = 0; r < size; r++) {
            if (grid[r][col] != symbol) {
                colWin = false;
                break;
            }
        }
        if (colWin) return true;

        // 3. Check Main Diagonal (if applicable)
        if (row == col) {
            boolean diagWin = true;
            for (int i = 0; i < size; i++) {
                if (grid[i][i] != symbol) {
                    diagWin = false;
                    break;
                }
            }
            if (diagWin) return true;
        }

        // 4. Check Anti-Diagonal (if applicable)
        if (row + col == size - 1) {
            boolean antiDiagWin = true;
            for (int i = 0; i < size; i++) {
                if (grid[i][size - 1 - i] != symbol) {
                    antiDiagWin = false;
                    break;
                }
            }
            if (antiDiagWin) return true;
        }

        return false;
    }

    public void printBoard() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                char displayChar = (grid[i][j] == Symbol.EMPTY) ? '-' : grid[i][j].name().charAt(0);
                System.out.print(displayChar + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

8. Step-by-Step Implementation: The Game Orchestrator

The TicTacToeGame class acts as the central orchestrator, managing players, turns, and the game loop.

JAVA

public interface BoardGame {
    void play();
}

public class Player {
    private final String name;
    private final Symbol symbol;
    private final PlayerStrategy strategy;

    public Player(String name, Symbol symbol, PlayerStrategy strategy) {
        this.name = name;
        this.symbol = symbol;
        this.strategy = strategy;
    }

    public String getName() { return name; }
    public Symbol getSymbol() { return symbol; }
    public Position playTurn(Board board) {
        return strategy.makeMove(board);
    }
}

public class TicTacToeGame implements BoardGame {
    private final Board board;
    private final Player player1;
    private final Player player2;
    private Player currentPlayer;
    private final GameContext gameContext;

    public TicTacToeGame(int boardSize, Player p1, Player p2) {
        this.board = new Board(boardSize);
        this.player1 = p1;
        this.player2 = p2;
        this.currentPlayer = p1;
        // Start with Player 1's turn
        this.gameContext = new GameContext(new XTurnState());
    }

    @Override
    public void play() {
        System.out.println("Starting Tic-Tac-Toe Game!");
        board.printBoard();

        while (!gameContext.isGameOver()) {
            System.out.println(currentPlayer.getName() + "'s turn (" + currentPlayer.getSymbol() + "):");
            Position move = currentPlayer.playTurn(board);
            
            board.placeSymbol(move, currentPlayer.getSymbol());
            board.printBoard();

            if (board.checkWin(move, currentPlayer.getSymbol())) {
                gameContext.setCurrentState(new GameWonState(currentPlayer.getName()));
                break;
            } else if (board.isFull()) {
                gameContext.setCurrentState(new DrawState());
                break;
            }

            // Transition state and switch player
            gameContext.next();
            switchPlayer();
        }

        announceResult();
    }

    private void switchPlayer() {
        currentPlayer = (currentPlayer == player1) ? player2 : player1;
    }

    private void announceResult() {
        GameState finalState = gameContext.getCurrentState();
        if (finalState instanceof GameWonState) {
            System.out.println("Congratulations! " + ((GameWonState) finalState).getWinnerName() + " wins!");
        } else if (finalState instanceof DrawState) {
            System.out.println("It's a draw!");
        }
    }
}

Main Execution Entry Point

JAVA

public class Main {
    public static void main(String[] args) {
        PlayerStrategy humanStrategy = new HumanPlayerStrategy();
        PlayerStrategy aiStrategy = new RandomAIPlayerStrategy();

        Player p1 = new Player("Alice", Symbol.X, humanStrategy);
        Player p2 = new Player("Bob (AI)", Symbol.O, aiStrategy);

        BoardGame game = new TicTacToeGame(3, p1, p2);
        game.play();
    }
}

9. Extensibility: Custom Board Sizes & Multi-Player Support

To scale the game to support $M$ players on an $N \times N$ board, we can modify our turn management logic. Instead of hardcoding two players, we can use a list of players and cycle through them using modulo arithmetic.

JAVA

import java.util.List;

public class MultiPlayerTicTacToeGame implements BoardGame {
    private final Board board;
    private final List<Player> players;
    private int currentPlayerIndex;
    private final GameContext gameContext;

    public MultiPlayerTicTacToeGame(int boardSize, List<Player> players) {
        this.board = new Board(boardSize);
        this.players = players;
        this.currentPlayerIndex = 0;
        this.gameContext = new GameContext(new XTurnState()); // Generic turn state
    }

    @Override
    public void play() {
        while (!gameContext.isGameOver()) {
            Player currentPlayer = players.get(currentPlayerIndex);
            System.out.println(currentPlayer.getName() + "'s turn:");
            
            Position move = currentPlayer.playTurn(board);
            board.placeSymbol(move, currentPlayer.getSymbol());
            board.printBoard();

            if (board.checkWin(move, currentPlayer.getSymbol())) {
                gameContext.setCurrentState(new GameWonState(currentPlayer.getName()));
                break;
            } else if (board.isFull()) {
                gameContext.setCurrentState(new DrawState());
                break;
            }

            // Cycle to the next player
            currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
        }
        
        announceResult();
    }

    private void announceResult() {
        if (gameContext.getCurrentState() instanceof GameWonState) {
            System.out.println("Winner: " + ((GameWonState) gameContext.getCurrentState()).getWinnerName());
        } else {
            System.out.println("The game ended in a draw!");
        }
    }
}

10. Extensibility: Decoupling with Observer & Factory Patterns

To keep our core game logic decoupled from presentation and creation details, we can implement the Observer and Factory patterns.

Observer Pattern: Decoupling Game Events

We can define a listener interface to track game events, such as moves or state changes, without hardcoding console output inside our core classes.

JAVA

import java.util.ArrayList;
import java.util.List;

// Observer Interface
public interface GameEventListener {
    void onMoveMade(Position pos, Symbol symbol);
    void onGameStateChanged(GameState newState);
}

// Concrete Observer for Console Logging
public class ConsoleGameEventListener implements GameEventListener {
    @Override
    public void onMoveMade(Position pos, Symbol symbol) {
        System.out.println("[EVENT] Move placed at (" + pos.getRow() + ", " + pos.getCol() + ") with symbol " + symbol);
    }

    @Override
    public void onGameStateChanged(GameState newState) {
        if (newState instanceof GameWonState) {
            System.out.println("[EVENT] Game Over: Winner is " + ((GameWonState) newState).getWinnerName());
        } else if (newState instanceof DrawState) {
            System.out.println("[EVENT] Game Over: Draw");
        }
    }
}

// Subject (Observable) Integration within TicTacToeGame
public class ObservableTicTacToeGame extends TicTacToeGame {
    private final List<GameEventListener> listeners = new ArrayList<>();

    public ObservableTicTacToeGame(int boardSize, Player p1, Player p2) {
        super(boardSize, p1, p2);
    }

    public void addListener(GameEventListener listener) {
        listeners.add(listener);
    }

    public void notifyMove(Position pos, Symbol symbol) {
        for (GameEventListener listener : listeners) {
            listener.onMoveMade(pos, symbol);
        }
    }

    public void notifyStateChange(GameState state) {
        for (GameEventListener listener : listeners) {
            listener.onGameStateChanged(state);
        }
    }
}

Factory Pattern: Player Creation

A factory class centralizes player creation, making it easy to instantiate players with different strategies (e.g., Human vs. AI).

JAVA

public class PlayerFactory {
    public static Player createPlayer(String name, Symbol symbol, String type) {
        PlayerStrategy strategy;
        if ("AI".equalsIgnoreCase(type)) {
            strategy = new RandomAIPlayerStrategy();
        } else {
            strategy = new HumanPlayerStrategy();
        }
        return new Player(name, symbol, strategy);
    }
}

11. Production Pitfalls, Edge Cases & Debugging Workflows

When deploying or presenting this system, consider these common edge cases and performance optimizations:

1. Algorithmic Optimization for Win Checking

Naive Approach: Iterating through rows, columns, and diagonals on every turn takes $O(N)$ time, where $N$ is the board dimension.
Optimized Approach: We can achieve $O(1)$ win checking by keeping track of row, column, and diagonal counts in memory.

Let's represent this mathematically. For a board of size $N$ , we can maintain:

An array rows of size $N$
An array cols of size $N$
Integer variables diagonal and antiDiagonal

When a player places a symbol, we increment the count for player 1 (+1) or decrement it for player 2 (-1). If any count reaches $+N$ or $-N$ , that player has won.

\text{Win Condition: } |\text{count}| = N

JAVA

public class OptimizedBoard {
    private final int n;
    private final int[] rows;
    private final int[] cols;
    private int diagonal;
    private int antiDiagonal;

    public OptimizedBoard(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
        this.diagonal = 0;
        this.antiDiagonal = 0;
    }

    // Returns +1 if Player 1 wins, -1 if Player 2 wins, 0 otherwise
    public int makeMoveAndCheckWin(int row, int col, int playerVal) {
        // playerVal is +1 for Player 1, -1 for Player 2
        rows[row] += playerVal;
        cols[col] += playerVal;

        if (row == col) {
            diagonal += playerVal;
        }
        if (row + col == n - 1) {
            antiDiagonal += playerVal;
        }

        if (Math.abs(rows[row]) == n || 
            Math.abs(cols[col]) == n || 
            Math.abs(diagonal) == n || 
            Math.abs(antiDiagonal) == n) {
            return playerVal;
        }
        return 0;
    }
}

2. Concurrency and Thread Safety

If this game is hosted on a multi-threaded server where multiple clients can submit moves simultaneously, the board state must be protected.

Solution: Use synchronized blocks or a ReentrantLock around the placeSymbol and checkWin operations to prevent race conditions.

12. Summary and Key Takeaways

Time is Your Currency: In an LLD interview, prioritize core functionality first. Implement the Board and Game loop before adding advanced design patterns.
Decouple with Strategy: Use the Strategy Pattern to separate player actions from move logic. This makes it easy to switch between human and AI players.
Design for Scale: Avoid hardcoding a $3 \times 3$ grid or a 2-player limit. Use $N \times N$ variables and list-based turn rotations to make the system highly extensible.
Optimize Win Checks: For large values of $N$ , use an $O(1)$ win-checking algorithm with row and column counters instead of scanning the entire board on every turn.
Decouple UI with Observers: Use the Observer Pattern to separate game state updates from console output, making it easy to plug in a GUI or web interface later.
Centralize Creation: Use the Factory Pattern to instantiate players and strategies, keeping your main orchestrator clean and focused.

✅ Complete Tic-Tac-Toe System Design & Low Level Design | Full Explanation + Code

Complete Tic-Tac-Toe System Design & Low-Level Design

1. Why Do We Need This? (Problem Statement & Interview Context)

2. Core Mental Model & Real-World Analogy

Real-Life Analogy

Game Flow Workflow

3. Clarifying Questions & Requirements Gathering

4. Key Entities & Domain Modeling

5. Architectural Design Patterns

1. Strategy Pattern

2. Factory Pattern

3. Observer Pattern

4. State Pattern

6. Step-by-Step Implementation: Strategy & State Patterns

Position Helper Class

Strategy Pattern: Player Move Strategy

State Pattern: Game States

7. Step-by-Step Implementation: The Board & Game Logic

8. Step-by-Step Implementation: The Game Orchestrator

Main Execution Entry Point

9. Extensibility: Custom Board Sizes & Multi-Player Support

10. Extensibility: Decoupling with Observer & Factory Patterns

Observer Pattern: Decoupling Game Events

Factory Pattern: Player Creation

11. Production Pitfalls, Edge Cases & Debugging Workflows

1. Algorithmic Optimization for Win Checking

2. Concurrency and Thread Safety

12. Summary and Key Takeaways