LLD: Tic Tac Toe¶

Difficulty: Beginner | Time: 20–30 minutes

1. Problem Statement¶

Design a two-player Tic Tac Toe game on an N×N board (default N=3). Players alternate placing their symbol on an empty cell; the game detects a win (N in a row, horizontally, vertically, or diagonally) or a draw (board full, no winner), and rejects invalid moves.

The board size should not be hardcoded to 3 — design so N is a parameter, and so a future "Connect 4"-style variant (bigger board, win condition is K-in-a-row where K < N, not "fill the whole row") is a plausible extension, not a rewrite. That constraint is what makes this an actual LLD problem: the naive approach — after every move, rescan every row, column, and both diagonals for N-in-a-row — is O(N) per move and gets worse as the board grows for the Connect-4 variant, where you'd otherwise rescan windows across the whole board. A good design instead maintains running counters that make the win check after each move O(1), independent of N.

2. Requirements¶

Functional (in scope):

• N×N board, N configurable at game construction (default 3)
• Two players, alternating turns, each with a distinct symbol (X / O)
• Reject a move on an occupied cell, an out-of-bounds cell, or a move made after the game has ended
• Detect a win — N symbols in a row, column, or either diagonal — in O(1) time after the move that causes it
• Detect a draw — board full, no winner
• Report game state (IN_PROGRESS, X_WON, O_WON, DRAW) after each move

Explicitly out of scope for v1: an AI opponent (touched on in Extensibility), a networked multiplayer transport layer (touched on in Concurrency), move undo/redo, board sizes where N is even and the diagonal win condition is ambiguous (assume square boards with well-defined diagonals).

3. Entities¶

The nouns in the problem statement: Symbol, Player, Board, WinChecker, Game.

4. Class Design¶

classDiagram
    class Symbol {
        <<enumeration>>
        X
        O
        EMPTY
    }

    class GameState {
        <<enumeration>>
        IN_PROGRESS
        X_WON
        O_WON
        DRAW
    }

    class Player {
        +name: str
        +symbol: Symbol
    }

    class Board {
        +size: int
        +grid: List~List~Symbol~~
        +place(row, col, symbol) void
        +is_within_bounds(row, col) bool
        +is_full() bool
    }

    class WinChecker {
        +win_length: int
        +register_move(row, col, symbol) bool
    }

    class Game {
        +board: Board
        +players: List~Player~
        +win_checker: WinChecker
        +state: GameState
        +make_move(row, col) GameState
    }

    Game *-- Board : composition
    Game *-- WinChecker : composition
    Game o-- Player : aggregation, players exist before/after the game
    Board --> Symbol
    Player --> Symbol

stateDiagram-v2
    [*] --> IN_PROGRESS
    IN_PROGRESS --> X_WON : make_move() [win_checker.register_move() true, mover is X]
    IN_PROGRESS --> O_WON : make_move() [win_checker.register_move() true, mover is O]
    IN_PROGRESS --> DRAW : make_move() [no win, board.is_full()]
    IN_PROGRESS --> IN_PROGRESS : make_move() [no win, board not full]
    X_WON --> [*]
    O_WON --> [*]
    DRAW --> [*]

Why composition for Game *-- Board and Game *-- WinChecker: neither has meaning outside a specific game — a Board isn't shared across games, and a WinChecker's running counters are only valid for the single board it was tracking. Delete the game, both go with it. Why aggregation for Game o-- Player: a Player (name, chosen symbol, and in a real system an account/session) exists before the game starts and after it ends — the game references two players, it doesn't own their lifecycle — see Class Relationships.

WinChecker is deliberately a separate class from Board, not a method on it: Board owns what's on the grid; WinChecker owns whether the current grid state is a win, including the running-counter state that makes that check fast. Splitting them keeps Board a dumb, reusable grid and keeps the win-detection algorithm swappable (see Patterns below) without touching grid storage.

5. Patterns Applied¶

• Strategy, legitimately, only if the requirement is "support multiple win-condition rules" — e.g. classic N-in-a-row-fills-everything on a 3x3 versus K-in-a-row-on-a-bigger-board (Connect-4-style) versus some custom variant. In that case WinChecker becomes an interface with register_move() as the seam, and each rule set is its own implementation sharing nothing but the interface. See Strategy. For a single fixed rule set (classic 3x3), don't introduce the interface — a concrete WinChecker class is enough, and adding the abstraction speculatively is over-engineering for a problem this small.
• Explicitly not using Singleton for Game — it's tempting because "there's only one game on screen right now," but a server hosting many concurrent games (see Concurrency) needs one Game instance per game session, and a singleton would have to be unwound the moment that requirement shows up. Construct and pass around Game instances normally.
• No Factory here — there's nothing to centralize; Player and Board construction is trivial and doesn't vary by input in a way that earns a creational pattern.

6. Core Code¶

The interesting part of this problem is entirely in WinChecker: instead of rescanning the board after every move, it maintains a running count per row, per column, and per diagonal, incremented (or decremented, for the other player) on each placement, so register_move is O(1) regardless of board size.

from dataclasses import dataclass
from enum import Enum


class Symbol(Enum):
    EMPTY = 0
    X = 1
    O = -1          # signed values let counters cancel out when players share a line


class GameState(Enum):
    IN_PROGRESS = "in_progress"
    X_WON = "x_won"
    O_WON = "o_won"
    DRAW = "draw"


@dataclass
class Player:
    name: str
    symbol: Symbol


class Board:
    def __init__(self, size: int = 3):
        self.size = size
        self.grid: list[list[Symbol]] = [[Symbol.EMPTY] * size for _ in range(size)]

    def is_within_bounds(self, row: int, col: int) -> bool:
        return 0 <= row < self.size and 0 <= col < self.size

    def is_occupied(self, row: int, col: int) -> bool:
        return self.grid[row][col] != Symbol.EMPTY

    def place(self, row: int, col: int, symbol: Symbol) -> None:
        self.grid[row][col] = symbol

    def is_full(self) -> bool:
        return all(cell != Symbol.EMPTY for row in self.grid for cell in row)


class WinChecker:
    """
    Classic win rule: N-in-a-row fills an entire row, column, or diagonal.

    Why running counters instead of rescanning the board after every move:
    a full rescan is O(N) per move (N cells in the affected row/col, plus
    the diagonals) and the naive "check the whole board" version is O(N^2).
    Neither is expensive for N=3, but the design should scale to a larger
    board without changing shape — and it costs nothing to do it right here.

    Each line (row i, column j, main diagonal, anti-diagonal) gets a running
    signed sum. X contributes +1 per cell, O contributes -1 (see Symbol).
    After incrementing the relevant line(s) for a move, the sum reaching
    +size means X completed that line; -size means O did. This turns "did
    this move complete a line" into an O(1) check: at most 3 lines (row,
    column, and 0-2 diagonals) are touched by any single move, never the
    whole board.
    """

    def __init__(self, size: int):
        self.size = size
        self._row_counts = [0] * size
        self._col_counts = [0] * size
        self._diag_count = 0          # top-left to bottom-right
        self._anti_diag_count = 0     # top-right to bottom-left

    def register_move(self, row: int, col: int, symbol: Symbol) -> bool:
        delta = symbol.value                      # +1 for X, -1 for O
        self._row_counts[row] += delta
        self._col_counts[col] += delta
        if row == col:
            self._diag_count += delta
        if row + col == self.size - 1:
            self._anti_diag_count += delta

        target = self.size * delta                # +size for an X win, -size for an O win
        return (
            self._row_counts[row] == target
            or self._col_counts[col] == target
            or self._diag_count == target
            or self._anti_diag_count == target
        )


class Game:
    def __init__(self, players: list[Player], size: int = 3):
        if len(players) != 2 or players[0].symbol == players[1].symbol:
            raise ValueError("tic tac toe requires exactly two players with distinct symbols")
        self.board = Board(size)
        self.players = players
        self.win_checker = WinChecker(size)
        self.state = GameState.IN_PROGRESS
        self._turn_index = 0                       # players[0] moves first

    def make_move(self, row: int, col: int) -> GameState:
        if self.state != GameState.IN_PROGRESS:
            raise ValueError("game has already ended")
        if not self.board.is_within_bounds(row, col):
            raise ValueError(f"({row}, {col}) is out of bounds for a {self.board.size}x{self.board.size} board")
        if self.board.is_occupied(row, col):
            raise ValueError(f"cell ({row}, {col}) is already occupied")

        player = self.players[self._turn_index]
        self.board.place(row, col, player.symbol)

        if self.win_checker.register_move(row, col, player.symbol):
            self.state = GameState.X_WON if player.symbol == Symbol.X else GameState.O_WON
        elif self.board.is_full():
            self.state = GameState.DRAW
        else:
            self._turn_index = 1 - self._turn_index   # only advance turn if the game continues

        return self.state

7. Edge Cases¶

8. Concurrency¶

A single in-memory game played by two people sharing one screen has no concurrency concern — make_move is called serially. The concurrency question shows up the moment this becomes a networked/multiplayer game: two clients, each representing one player, could submit a move for the same game at close to the same instant (e.g. a slow network makes a stale client retry, or a buggy client double-submits).

Two race conditions matter here, both instances of the race condition pattern:

• Turn violation: without a check, both clients' moves could be applied even though only one player's symbol should be allowed to move — e.g. O sneaks in a move immediately after X's, before O's _turn_index update was visible. The fix already in make_move — reading self._turn_index to determine whose turn it is, and only advancing it after a successful move — must happen inside the same critical section as the board write, or the read-turn/write-board/advance-turn sequence itself becomes the race.
• Double-write to the same cell: two near-simultaneous calls to make_move (even from the correct alternating players, if a client retries) could both pass the is_occupied check before either has written, then both write — corrupting the board and potentially awarding a win to the wrong symbol.

The fix is a single per-game lock — not per-cell, unlike Parking Lot's per-spot locking. That asymmetry is deliberate: a parking lot has many independent spots where fine-grained locking buys real concurrency between unrelated resources, but a tic-tac-toe game has exactly one shared resource (the whole board plus whose-turn-it-is state) and exactly two contending clients — there's no unrelated work to parallelize, so a single lock around make_move costs nothing in practice and eliminates both races at once:

from threading import Lock

class Game:
    def __init__(self, players: list[Player], size: int = 3):
        ...
        self._lock = Lock()

    def make_move(self, row: int, col: int, requesting_player: Player) -> GameState:
        with self._lock:
            if requesting_player != self.players[self._turn_index]:
                raise ValueError("not this player's turn")
            # ... existing bounds/occupancy/state checks and board write, unchanged

Note the added requesting_player parameter and the turn check as the first thing inside the lock — in a networked version, the caller can no longer be trusted to only call make_move when it's actually their turn; that trust boundary moves from "the local UI only lets you click when it's your turn" to "the server must verify identity server-side."

9. Extensibility¶

Interview Questions¶

Key Takeaways¶

Previous: LLD Problem Roadmap | Next: Library Management