Design Tic-Tac-Toe
A low-level design for Tic-Tac-Toe that generalizes to an N×N board with a K-in-a-row win condition, and an O(1)-per-move win detection algorithm instead of a full board scan.
Design Tic-Tac-Toe
Tic-Tac-Toe looks trivial, and the surface requirements are — which is exactly why interviewers use it to probe a narrower, deeper question: can you generalize a 3×3, 3-in-a-row game to an N×N board with a K-in-a-row win condition, and can you detect a win in O(1) per move instead of rescanning the whole board? This guide works the problem end-to-end using the six-step framework used throughout this phase: requirements → actors → class diagram → class design → patterns → algorithms/concurrency → trade-offs.
1. Requirements
Functional:
- An N×N board (default 3×3), two players marking X and O, alternating turns.
- Detect a win: K marks in a row, horizontally, vertically, or diagonally (default K=N=3, but the design must generalize to, say, a 15×15 board with K=5 — "Gomoku" rules).
- Detect a draw (board full, no winner).
- Reject a move to an already-occupied cell.
- Maintain move history for replay.
Non-functional:
- Win detection must not require scanning the entire board after every move — for a large N (e.g. 15×15 Gomoku), an O(N²) scan per move is wasteful when only one row/column/diagonal actually changed.
2. Actors & Use Cases
| Actor | Use cases |
|---|---|
| Player (X / O) | Make a move at (row, col) |
| Game | Validate move, update board, detect win/draw, enforce turn order |
3. Class Diagram
4. Core Class Design (Java)
Board
final class Board {
private final int size;
private final Symbol[][] grid;
Board(int size) {
this.size = size;
this.grid = new Symbol[size][size];
for (Symbol[] row : grid) Arrays.fill(row, Symbol.EMPTY);
}
boolean placeMark(int row, int col, Symbol symbol) {
if (grid[row][col] != Symbol.EMPTY) return false; // already occupied
grid[row][col] = symbol;
return true;
}
boolean isFull() {
return Arrays.stream(grid).flatMap(Arrays::stream).noneMatch(s -> s == Symbol.EMPTY);
}
}The O(1)-per-move win detection
The naive approach — after every move, scan every row, column, and both diagonals for K-in-a-row — is O(N) work per move (or worse for K-in-a-row generalization). The fix: maintain running counts per row, column, and the two diagonals, and update only the four counts touched by the move just played.
final class LineCountWinStrategy implements WinStrategy {
private final int size, k;
private final int[] rowCount; // rowCount[r] = consecutive-run tracking per row (see note)
private final int[] colCount;
// For the general K-in-a-row case, "count" isn't a simple sum — it must track
// the longest CURRENT RUN through the just-played cell, not total marks in the line.
// Below shows the simpler N==K classic 3x3 case; the general form is discussed after.
LineCountWinStrategy(int size, int k) {
this.size = size;
this.k = k;
this.rowCount = new int[size];
this.colCount = new int[size];
}
private int diagonalCount = 0;
private int antiDiagonalCount = 0;
public boolean checkWin(Board board, Move move, Symbol symbol) {
int delta = (symbol == Symbol.X) ? 1 : -1; // opposite players push counts in opposite directions
int row = move.row(), col = move.col();
rowCount[row] += delta;
colCount[col] += delta;
if (row == col) diagonalCount += delta;
if (row + col == size - 1) antiDiagonalCount += delta;
return Math.abs(rowCount[row]) == size
|| Math.abs(colCount[col]) == size
|| Math.abs(diagonalCount) == size
|| Math.abs(antiDiagonalCount) == size;
}
}This delta-sum trick (classic for the N==K case, e.g. LeetCode's "Design Tic-Tac-Toe") works because it's a signed count: X pushes each line's count up by 1, O pushes it down by 1. A line count of +size means all X, -size means all O — either way, Math.abs(count) == size catches it in O(1) per move, checking only the 4 lines the current move actually touches instead of the whole board.
This exact trick only works when K == N (a mark anywhere in a line always contributes to the same win condition for that whole line). For the general K-in-a-row case (N=15, K=5 — Gomoku), you instead track the longest current run through the played cell in each of the 4 directions (row, column, both diagonals), extending outward from (row, col) in both directions along each axis and checking if the total reaches K. That's still O(1) per direction checked, independent of N — just a different bookkeeping structure (a small local scan bounded by K, not by N).
// General K-in-a-row check: for each of the 4 directions, count consecutive
// same-symbol cells extending outward from the just-played cell.
boolean checkWinGeneral(Board board, int row, int col, Symbol symbol, int k) {
int[][] directions = {{0, 1}, {1, 0}, {1, 1}, {1, -1}}; // horizontal, vertical, both diagonals
for (int[] dir : directions) {
int count = 1; // the cell just played
count += countInDirection(board, row, col, dir[0], dir[1], symbol);
count += countInDirection(board, row, col, -dir[0], -dir[1], symbol);
if (count >= k) return true;
}
return false;
}
private int countInDirection(Board board, int row, int col, int dRow, int dCol, Symbol symbol) {
int count = 0;
int r = row + dRow, c = col + dCol;
while (board.inBounds(r, c) && board.symbolAt(r, c) == symbol) {
count++;
r += dRow;
c += dCol;
}
return count;
}Game orchestration
final class Game {
private final Board board;
private final List<Player> players;
private int currentPlayerIndex = 0;
private final WinStrategy winStrategy;
private final List<Move> history = new ArrayList<>();
private GameResult result;
boolean makeMove(int row, int col) {
if (result != null) throw new IllegalStateException("Game already over");
Player current = players.get(currentPlayerIndex);
if (!board.placeMark(row, col, current.getSymbol())) return false; // occupied
Move move = new Move(current, row, col);
history.add(move);
if (winStrategy.checkWin(board, move, current.getSymbol())) {
result = new GameResult(current, false);
} else if (board.isFull()) {
result = new GameResult(null, true);
} else {
currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
}
return true;
}
}5. Design Patterns Applied
| Pattern | Where used | Why |
|---|---|---|
| Strategy | WinStrategy | Swapping between the O(1) signed-count check (N==K) and the general K-in-a-row directional scan without touching Game |
| State | GameResult transitions (in progress → won / drawn) | Once a result exists, no further moves are accepted — enforced at the state boundary, not scattered checks |
6. Key Algorithms, Concurrency & Edge Cases
- Move validation order matters: check
result == null(game not over) before checking cell occupancy, so a stray move after game-end fails with a clear "game over" signal rather than a confusing "cell occupied" one. - N×N generalization: the board size and win condition K are both constructor parameters on
Game/WinStrategy— nothing aboutBoardorGamehardcodes 3. - Replay/history: storing the full
Movelist (not just the final board) lets you reconstruct the board at any point in the game, which is what a "review the game" or "undo" feature needs.
A common follow-up: "what if this needed to support more than 2 players?" The signed-count trick breaks (it only distinguishes two directions, +1/-1), but the general directional-scan approach generalizes cleanly — just check "same symbol as the mover," not "positive vs negative."
7. Trade-offs & Extensions
- Signed-count (O(1), N==K only) vs. directional scan (O(K) per move, works for any K≤N): pick signed-count for the classic 3×3 case if the interviewer doesn't ask for K-in-a-row generalization; lead with directional scan if they do, since it's strictly more general at a small, bounded cost.
- Extensions: online multiplayer (turn broadcast via Observer), AI opponent (minimax over the same
Board/WinStrategyabstractions), replay/spectator mode using the storedMovehistory.
Interview Questions
- Walk through the O(1) win-detection trick for the classic 3×3 case and explain why it only works when K equals N.
- How would you generalize win detection to a 15×15 board with a 5-in-a-row win condition?
- Why is
WinStrategya separate interface instead of a method onBoardorGame? - How do you prevent a move after the game has already ended?
- How would you extend this design to support more than two players?