Design Tic-Tac-Toe: An LLD Machine Coding Walkthrough

Tic-Tac-Toe looks like the simplest possible coding problem. A 3x3 grid, two players, three-in-a-row wins. You could implement a working version in 30 lines with a few nested loops and a global list. So why do interviewers give it as a machine-coding problem?

Because the question isn’t “can you make it work.” The question is “can you structure it so it stays clean when requirements change?” What happens when the interviewer says “now make it 5x5, and you need 4-in-a-row to win”? Or “add a third player”? If your game logic is tangled with your board representation, you’re rewriting from scratch. If you separated concerns properly from the start, you change a constant and a constructor argument.

That’s the real lesson here. Let me reason through how I’d design this from scratch.

Requirements

Functional:

• Two players take turns placing their symbol (X or O) on a 3x3 grid
• A player wins by placing their symbol in a full row, column, or diagonal
• The game ends in a draw if the board fills without a winner
• Invalid moves (occupied cells, out-of-bounds) should be rejected

Non-functional:

• The design must extend to an NxN board with K-in-a-row win condition without major rewrites
• Adding a new player type (e.g., AI player) should not require changing game logic

Core Entities

When I reason through what objects live in this problem, I find four natural ones:

Player: has an identity and a symbol. This is a simple value object, but abstracting it lets you later add an AI player without touching anything else.

Board: owns the grid state, knows how to place a piece, and can tell you what’s at a position. It does not know who won. That distinction matters.

WinChecker: knows the win conditions. Separated from Board because win logic is a policy, and policies change. A 3x3 game checks all rows, columns, and two diagonals. A 5x5 “connect four” variant checks runs of 4. If Board owns win detection, you can’t change the rule without changing the data structure.

Game: orchestrates the state machine. It knows whose turn it is, when the game ends, and transitions between states.

The Game State Machine

The game progresses through exactly three states:

PLAYING --> WON
        --> DRAW

There’s no going back. You can’t un-win a game. This is simple enough to model with an enum rather than the full State pattern (which we’ll use in the Vending Machine post where states actually have behavior differences). Here the state just tells us when to stop.

ASCII Class Diagram

┌─────────────────────┐
│       Player        │
│─────────────────────│
│ name: str           │
│ symbol: str         │
└─────────────────────┘
           │ uses
           ▼
┌─────────────────────┐       ┌────────────────────────┐
│       Board         │       │      WinChecker        │
│─────────────────────│       │────────────────────────│
│ size: int           │◄──────│ board: Board           │
│ grid: list[list]    │       │ win_length: int        │
│ place(r,c,symbol)   │       │────────────────────────│
│ is_full() -> bool   │       │ check(symbol) -> bool  │
│ get(r,c) -> str     │       │ _check_row()           │
└─────────────────────┘       │ _check_col()           │
           ▲                  │ _check_diag()          │
           │                  └────────────────────────┘
┌──────────┴──────────┐
│        Game         │
│─────────────────────│
│ board: Board        │
│ players: list       │
│ checker: WinChecker │
│ state: GameState    │
│ current_idx: int    │
│─────────────────────│
│ play(row, col)      │
│ current_player()    │
└─────────────────────┘

Key Implementation

from __future__ import annotations
from dataclasses import dataclass
from enum import Enum, auto
from typing import Optional


class GameState(Enum):
    PLAYING = auto()
    WON = auto()
    DRAW = auto()


@dataclass
class Player:
    name: str
    symbol: str  # single character: 'X' or 'O'


class Board:
    def __init__(self, size: int = 3) -> None:
        self.size = size
        self._grid: list[list[Optional[str]]] = [
            [None] * size for _ in range(size)
        ]

    def place(self, row: int, col: int, symbol: str) -> bool:
        """Returns False if the cell is already occupied or out of bounds."""
        if not (0 <= row < self.size and 0 <= col < self.size):
            return False
        if self._grid[row][col] is not None:
            return False
        self._grid[row][col] = symbol
        return True

    def get(self, row: int, col: int) -> Optional[str]:
        return self._grid[row][col]

    def is_full(self) -> bool:
        return all(
            self._grid[r][c] is not None
            for r in range(self.size)
            for c in range(self.size)
        )


class WinChecker:
    """
    Checks win conditions independently of Board internals.
    win_length allows NxN boards with K-in-a-row rules.
    """

    def __init__(self, board: Board, win_length: Optional[int] = None) -> None:
        self.board = board
        # Default: full row/col/diagonal required (classic tic-tac-toe)
        self.win_length = win_length or board.size

    def check(self, symbol: str) -> bool:
        return (
            self._check_rows(symbol)
            or self._check_cols(symbol)
            or self._check_diags(symbol)
        )

    def _run_of(self, cells: list[Optional[str]], symbol: str) -> bool:
        """True if any consecutive run of win_length matches symbol."""
        count = 0
        for cell in cells:
            count = count + 1 if cell == symbol else 0
            if count >= self.win_length:
                return True
        return False

    def _check_rows(self, symbol: str) -> bool:
        size = self.board.size
        for r in range(size):
            row = [self.board.get(r, c) for c in range(size)]
            if self._run_of(row, symbol):
                return True
        return False

    def _check_cols(self, symbol: str) -> bool:
        size = self.board.size
        for c in range(size):
            col = [self.board.get(r, c) for r in range(size)]
            if self._run_of(col, symbol):
                return True
        return False

    def _check_diags(self, symbol: str) -> bool:
        size = self.board.size
        # Top-left to bottom-right
        main_diag = [self.board.get(i, i) for i in range(size)]
        # Top-right to bottom-left
        anti_diag = [self.board.get(i, size - 1 - i) for i in range(size)]
        return self._run_of(main_diag, symbol) or self._run_of(anti_diag, symbol)


class Game:
    def __init__(self, players: list[Player], board_size: int = 3,
                 win_length: Optional[int] = None) -> None:
        self.players = players
        self.board = Board(size=board_size)
        self.checker = WinChecker(self.board, win_length)
        self.state = GameState.PLAYING
        self._current_idx = 0

    def current_player(self) -> Player:
        return self.players[self._current_idx]

    def play(self, row: int, col: int) -> GameState:
        if self.state != GameState.PLAYING:
            raise ValueError("Game is already over.")

        player = self.current_player()

        if not self.board.place(row, col, player.symbol):
            raise ValueError(f"Invalid move: ({row}, {col})")

        if self.checker.check(player.symbol):
            self.state = GameState.WON
            return self.state

        if self.board.is_full():
            self.state = GameState.DRAW
            return self.state

        # Rotate to next player — works for 2 or more players
        self._current_idx = (self._current_idx + 1) % len(self.players)
        return self.state

Design Decisions and Trade-offs

Why separate WinChecker from Board?

The cleanest reason is the single responsibility principle. Board manages state. WinChecker evaluates policy. When you change the win condition (say, 4-in-a-row on a 5x5 board), you change one class and leave the other untouched. If win detection lived in Board, a policy change would require modifying the data structure class.

There’s a practical benefit too: WinChecker is easier to test in isolation. You can construct a board in any state and verify the checker’s output without running a full game.

Why use _run_of instead of checking full rows?

The naive implementation checks if all cells in a row match the symbol. That works for 3x3 but breaks for 5x5 with a 4-in-a-row rule. The _run_of helper scans for any consecutive run of win_length, so the same logic handles both cases without branching.

Why rotate players with modulo instead of hardcoding two?

(idx + 1) % len(players) costs nothing extra and gives you three-player games for free. Hardcoding 1 - current_idx would work for two players but is a trap you’d fall into if requirements changed.

What about the play method raising instead of returning an error?

Returning False on an invalid move puts the burden on the caller to check the return value every time. Raising a ValueError makes invalid moves impossible to ignore silently. The caller must handle it explicitly.

Extending to NxN with K-in-a-row:

# 15x15 Gomoku: first to 5 in a row wins
game = Game(players=[Player("Alice", "X"), Player("Bob", "O")],
            board_size=15, win_length=5)

That’s the only change needed. The WinChecker._run_of logic already handles it.

What I’d Add Next

If this were a real system, I’d layer on a few things. A GameHistory that records every move as an immutable log, so you can replay or undo. A Renderer interface that Game calls after each move, keeping display logic separate from game logic. An AIPlayer subclass that uses minimax to pick moves, slotting in without touching anything in Game.

Each of those extensions plugs in cleanly because the core structure has clear boundaries. That’s the real payoff of getting the design right upfront.

---

If you want to talk through the design or argue about where win detection should live, reach out on Twitter or LinkedIn. I’m always happy to reason through these problems together.