DSA & System Design
BackendEasy25 min

Design Tic-Tac-Toe (LLD)

Two classes with two jobs: a board that knows its lines and a game that knows the turn. Running totals check a win in O(1) on any size.

Related:Design a Vending Machine (LLD)From Requirements to Classes Explain it back
Say it in 30 seconds
  • O(1)win check per move, at any board size
  • n or -na line total that means a win
  • 4 totalsrow, column and two diagonals touched
Show what to say

“I'd split it into a Board that owns the grid and a Game that owns the turn and the ending. The board keeps a signed total per row, column and diagonal, so a move is checked in O(1) at any size: a line is won when its total reaches n or minus n. Undo is a stack of moves, and a bot is a swappable strategy.”

Trade-offs

  • Running totals vs scanning: constant time per move, but only for n in a row, and they must stay in step with the grid.
  • Mark as a string vs a Player class: less code now, but no place for a name or a score later.
  • Lock plus version vs trusting the client: a little more state, but two tabs can never both apply a move.

Bring it up before they ask

A rejected move must change nothing and must not use up the turn, so every check runs before the board is touched.

0 of 0 sections ticked
30-second answer

Two classes with two jobs: a Board that knows its lines, and a Game that knows the turn and how the match ends. Keep a running total per row, column and diagonal and a move is checked in O(1), on a 3 by 3 board or a 500 by 500 one.

Functional

  • Two players, X first, then alternating
  • Place a mark on a free cell
  • A full row, column or diagonal wins
  • A full board with no line is a draw
  • Rejected moves change nothing and keep the turn
  • Undo the last move
  • Optional computer opponent

Non-functional

  • Checking a move is O(1)
  • Board size is a parameter, not a constant
  • Safe when two clients send moves at once
  • The opponent can be swapped without touching the game
  • Deterministic tests: no clock, no randomness in the core

Out of scope

  • Rendering and animation
  • Matchmaking and accounts (an HLD follow-up)
  • More than two players (a follow-up)

A low-level design (LLD) question that looks trivial. The grade is on who owns what, and on the follow-ups.

New to this? Read From requirements to classes first.

Clarifying questions and interface

Read more · 165 words
  • Is the board always 3 by 3, or n by n?
  • Is it n in a row, or fewer than n (a k-in-a-row game)?
  • Two players only, or more?
  • Is there undo? Is there a computer opponent?
  • One screen, or two remote clients?

Public interface

CallReturnsNotes
move(mark, row, col)OK, WIN, DRAWApplies the move
NOT_YOUR_TURN, INVALID_MOVE, GAME_OVER, STALERejected: nothing changes
undo()true if there was a moveAlso takes a game back from won or drawn
status, winner, currentRead-only views

Every check runs before any change, in a fixed order: game over, stale version, turn, cell.

What it remembers

  • cells: the grid, empty or a mark.
  • rows, cols, diag, anti: one signed total per line.
  • filled: how many cells are used, so a draw needs no scan.
  • turn, status, winner, version, and the history stack for undo.

The totals and the grid describe one board. Only place and clear write them, so they cannot drift.

Build the design in stages

Step through: board, game, undo, then the opponent. Green marks what the latest stage added.

Read more · 100 words

Patterns, and when to skip them

Command earns its place once there is undo: each move is a record that can reverse itself. Strategy earns its place once there is a computer player: a bot is a function from board to cell. A tiny state machine (in progress, won, draw) makes the ending one field instead of three flags.

Skip the rest. A Player class holding one string, a WinChecker with one implementation, or a rules engine for three rules gets marked down. For a plain 3 by 3, a function over a 2D array is a fine first answer.

Stage 1 of 5

A board that knows its lines

Board owns the grid and one running total per row, column and diagonal. Adding +1 for X and -1 for O means a line is complete exactly when its total reaches n or minus n.

Tic-tac-toe class diagramBoard owns the grid and the running total of each row, column and diagonal, so it can say in O(1) whether a mark finishes a line. Game owns the turn, the status and the undo stack of moves. A Bot is a swappable strategy that reads the board and picks a cell.MarkX = +1O = -1other(): MarkBoardcells: n x nrows[n], cols[n]diag, antifilledisFree(r, c)wouldComplete(mark, r, c)place(mark, r, c)clear(r, c)

Board owns the grid and the running total of each row, column and diagonal, so it can say in O(1) whether a mark finishes a line. Game owns the turn, the status and the undo stack of moves. A Bot is a swappable strategy that reads the board and picks a cell.

  • ◆ composition (owns)
  • ◇ aggregation
  • △ inheritance / implements (dashed)
  • → association · ⇢ dependency

One move, and the O(1) win check

Pick a branch: a normal move, a win, a draw on the last cell, and a rejected move.

Read more · 146 words

Win check in O(1)

Scanning a row, a column and two diagonals costs O(n) per move. A running total per line costs nothing to read.

Give X the value +1 and O the value -1. A move touches one row, one column, and at most two diagonals, so add its value to just those totals. A line belongs to one player exactly when its total is n or minus n, because a mixed line cancels toward zero.

After X plays 0,0 then 1,1Total
Row 01
Main diagonal2
X plays 2,23 = n, X wins

Fewer than n in a row? The totals no longer work, because a winning run can sit inside a longer line. Then count same marks outward from the new cell in four directions. That is O(k) per move, and still no board scan.

Press Play to watch it run · 6 steps

Game checks the version, the turn and the cell, asks the board whether the move would finish a line, places the mark, and then decides between win, draw and next turn. Pick a branch to see a normal move, a winning move, a draw and a rejected move.

One move, from the client to the boardGame checks the version, the turn and the cell, asks the board whether the move would finish a line, places the mark, and then decides between win, draw and next turn. Pick a branch to see a normal move, a winning move, a draw and a rejected move.move(X, 1, 1)lock taken: one writer at a timealt [normal move]isFree(1, 1)wouldComplete(X, 1, 1)false: totals 1, 1, 1, 1place(X, 1, 1)turn passes to O, version +1OK
  • Client
  • Service
  • Cache
Text description
  1. Client → Game: move(X, 1, 1)
  2. Game → Board: isFree(1, 1)
  3. Game → Board: wouldComplete(X, 1, 1)
  4. Board replies to Game: false: totals 1, 1, 1, 1
  5. Game → Board: place(X, 1, 1)
  6. Game replies to Client: OK

Two clients, one game

With two clients the danger is a lost update: both act on the same board.

Read more · 38 words
  • One writer. A lock per game makes the turn check and the cell check one step.
  • A version number. A move based on an older version is refused as stale.
  • The server decides the turn, never the client.

Press Play to watch it run · 5 steps

Both players' clients read version 0 and send a move at the same time. The lock lets one in first and bumps the version. The second move carries the old version, so it is refused as stale and the client refreshes instead of overwriting.

Two clients act on the same boardBoth players' clients read version 0 and send a move at the same time. The lock lets one in first and bumps the version. The second move carries the old version, so it is refused as stale and the client refreshes instead of overwriting.both clients show version 0move(X, 0, 0, seen 0)move(X, 0, 0, seen 0)the lock admits A first; version becomes 1OKSTALEread the board, version 1B sees the new board and decides again
  • Client
  • Service
Text description
  1. Client A → Game: move(X, 0, 0, seen 0)
  2. Client B → Game: move(X, 0, 0, seen 0)
  3. Game replies to Client A: OK
  4. Game replies to Client B: STALE
  5. Client B → Game: read the board, version 1

How to approach it

  1. Clarify

    Size, k in a row, players, undo, bot, remote.

  2. Name the owners

    Board owns lines. Game owns turns.

  3. Order the checks

    Over, stale, turn, cell, then place.

  4. Make the win check O(1)

    A signed total per line.

  5. Add the extras only on request

    Undo, bot, remote play.

Read more · 219 words

Step-by-step answer

  1. Nouns and verbs

    Nouns: game, board, mark. Verbs: move, check a win, report the result. A Player class would hold one string, so the mark is enough.

  2. Board.wouldComplete

    Read the totals before placing, so the game knows the result without changing anything yet.

    wouldComplete(mark, r, c) {
  const d = weight(mark);
  const totals = [this.rows[r] + d, this.cols[c] + d];
  if (r === c) totals.push(this.diag + d);
  if (r + c === this.n - 1) totals.push(this.anti + d);
  return totals.some(t => Math.abs(t) === this.n);
}

  3. Game.move is a short list

    Game over, stale, turn, cell. Then place, push on the history, and choose win, draw or next turn. Check the win before the draw, so a last move that completes a line is a win.

  4. Undo reverses the same counters

    clear is place with the sign flipped. Undo also restores the turn and the status, which can go back from won or drawn.

  5. A bot is a function

    The sensible bot wins if it can, then blocks, then takes the middle. It uses wouldComplete for both checks. Minimax is another function behind the same interface.

  6. Tests

    Compare the counters against a brute-force scan over hundreds of random games. Add the mixed line, the last-cell win and a 500 by 500 board.

Implementation

The same design in JavaScript, Java or Python. Java and Python guard the game with a real lock.

Read more · 52 words
  • wouldComplete is read-only, so bots can try every cell without touching the board.
  • The Java test races two threads for the same move 200 times: exactly one is applied.

Code it yourself

Try the Tic-Tac-Toe exercise: the same Board and Game split, with a 500 by 500 board that rules out scanning.

const weight = mark => (mark === 'X' ? 1 : -1);

// Board knows the grid and whether a mark finishes a line. It keeps a running total per line
// (+1 for each X, -1 for each O), so a line is won exactly when its total reaches n or -n.
export class Board {
  constructor(n) {
    this.n = n;
    this.cells = Array.from({ length: n }, () => Array(n).fill(null));
    this.rows = Array(n).fill(0);
    this.cols = Array(n).fill(0);
    this.diag = 0;                                 // cells where row === col
    this.anti = 0;                                 // cells where row + col === n - 1
    this.filled = 0;
  }

  isFree(r, c) {
    return Number.isInteger(r) && Number.isInteger(c) && r >= 0 && r < this.n && c >= 0 && c < this.n && this.cells[r][c] === null;
  }

  isFull() { return this.filled === this.n * this.n; }

  // O(1) and read-only: would this mark complete a line? A mixed line can never reach n in absolute value.
  wouldComplete(mark, r, c) {
    const d = weight(mark);
    const totals = [this.rows[r] + d, this.cols[c] + d];
    if (r === c) totals.push(this.diag + d);
    if (r + c === this.n - 1) totals.push(this.anti + d);
    return totals.some(t => Math.abs(t) === this.n);
  }

  place(mark, r, c) { this.#apply(r, c, mark, 1); }

  clear(r, c) { this.#apply(r, c, this.cells[r][c], -1); }   // the undo of place: same counters, opposite sign

  #apply(r, c, mark, sign) {
    const d = weight(mark) * sign;
    this.cells[r][c] = sign > 0 ? mark : null;
    this.filled += sign;
    this.rows[r] += d;
    this.cols[c] += d;
    if (r === c) this.diag += d;
    if (r + c === this.n - 1) this.anti += d;
  }
}

Failure modes and trade-offs

Read more · 168 words
What breaksEffectMitigation
Win checked after the drawA winning last move counts as a drawCheck the win first
Mark placed before validationA bad move uses up the turnValidate everything first
Grid and totals disagreeA phantom win after undoOne method writes both
Two moves raceLost update, wrong turnLock plus version
Client picks the markA player moves for the otherThe server owns the turn

Trade-offs

ChoiceProsCons
Totals vs scanningO(1) per moveOnly for n in a row
Mark as a string vs a Player classLess codeNo place for names or scores
Lock vs one thread per gameSimpleContention if one game is hot
Undo stack vs recomputingFastExtra state to keep correct

Follow-up questions

How would you support k in a row on a larger board?

Keep the grid, drop the totals, and after each move count same marks outward in the four line directions from the new cell. That is O(k) and needs no board scan.

How would you add a computer opponent?

A Bot that maps board and mark to a cell. Start with win, block, middle. Minimax searches every reply and is fine for 3 by 3, with pruning for more.

How would you support three players?

Replace the two-way turn toggle with a list of marks. The totals need one map per mark instead of a sign.

How do you store and replay a game?

The history already lists every move. Save it as a list of mark, row and column, and replay by calling move again.

How would you run it as an online service?

One game per key, one writer per game, a version in every request, and the history as the source of truth. That is the HLD version of the same design.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. On an n by n board, how do you check for a win in O(1) after each move?

Patterns behind this

The coding patterns this design is built on. Practise them and the design questions get easier.