Back to Notes

Design a Board Game (Tic-Tac-Toe, generalized)

1. Problem & Why It's Asked

Tic-Tac-Toe itself is trivial; the interview value is in generalizing win detection so it doesn't hardcode "3 in a row on a 3x3 board" — a candidate who writes 8 explicit if checks for the 8 winning lines on a 3x3 board has solved the wrong problem. The correct generalization (N×N board, K-in-a-row to win, extendable to Connect Four-style gravity) is what separates a shallow solution from a properly designed one.

2. Requirements

Functional: two (or more) players take turns placing a mark on an N×N grid; detect a win (K marks in a row — horizontal, vertical, or diagonal) or a draw (board full, no winner).

Non-functional: win-check should not be O(board size) per move if avoidable (see §5 for the optimized version); extensible to different board sizes, win conditions, and player counts without rewriting the win-detection core.

3. Class Diagram

classDiagram
    class Player {
        +str name
        +str symbol
    }
    class Board {
        -int size
        -list~list~ grid
        +place(row, col, symbol) bool
        +is_full() bool
    }
    class GameStatus {
        <<enumeration>>
        IN_PROGRESS
        WIN
        DRAW
    }
    class TicTacToeGame {
        -Board board
        -list~Player~ players
        -int current_player_idx
        -WinChecker win_checker
        +make_move(row, col) GameStatus
    }
    class WinChecker {
        <<interface>>
        +check(board, row, col, symbol) bool
    }
    TicTacToeGame --> Board
    TicTacToeGame --> Player
    TicTacToeGame --> WinChecker
    TicTacToeGame --> GameStatus

4. Design Patterns Used

  • Strategy for win-condition checking (WinChecker) — swappable between "3-in-a-row on 3x3" and "K-in-a-row on N×N" without touching TicTacToeGame (see [[OOD Design Patterns]]).
  • The optimized win-check below (line-sum tracking) is a space-time trade-off pattern, not a named GoF pattern — worth explaining the trade-off explicitly rather than naming a pattern that doesn't apply.

5. Implementation — Naive O(N) Win Check, Then the O(1) Optimization

Naive version — after every move, check the entire row, column, and both diagonals through the just-placed cell:

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

    def place(self, row: int, col: int, symbol: str) -> bool:
        if self.grid[row][col] is not None:
            return False
        self.grid[row][col] = symbol
        return True

    def is_full(self) -> bool:
        return all(cell is not None for row in self.grid for cell in row)


def check_win_naive(board: Board, row: int, col: int, symbol: str) -> bool:
    n = board.size
    row_match = all(board.grid[row][c] == symbol for c in range(n))
    col_match = all(board.grid[r][col] == symbol for r in range(n))
    diag_match = row == col and all(board.grid[i][i] == symbol for i in range(n))
    anti_diag_match = row + col == n - 1 and all(board.grid[i][n - 1 - i] == symbol for i in range(n))
    return row_match or col_match or diag_match or anti_diag_match

This is O(N) per move — fine for a 3x3 board, but the interviewer's natural follow-up is "what if the board is 1000x1000?"

O(1) optimized version — maintain running sums per row, column, and both diagonals; a line is won the instant its sum reaches ±N (encoding player 1 as +1, player 2 as -1):

class OptimizedTicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        """player: 1 or 2. Returns the winning player (1 or 2), or 0 if no winner yet."""
        delta = 1 if player == 1 else -1
        self.rows[row] += delta
        self.cols[col] += delta
        if row == col:
            self.diag += delta
        if row + col == self.n - 1:
            self.anti_diag += delta

        if abs(self.rows[row]) == self.n or abs(self.cols[col]) == self.n \
           or abs(self.diag) == self.n or abs(self.anti_diag) == self.n:
            return player
        return 0

Why this is O(1): each move updates 2–4 counters (its row, its column, and diagonal(s) only if it lies on one) and checks 4 values — no scanning. This is the answer that signals "this candidate thought about scale," not just "this candidate can code Tic-Tac-Toe."

6. Generalizing to K-in-a-Row (not just full-line wins)

For Gomoku-style "5 in a row on a 15x15 board" (win condition shorter than the board dimension), the O(1) running-sum trick doesn't directly apply (a full-board sum doesn't tell you where K consecutive marks are). The standard approach: after each move, check outward from the placed cell in the 4 line directions (horizontal, vertical, 2 diagonals), counting consecutive same-symbol cells in both directions from the move — O(K) per move, independent of board size N. This is the right generalization to reach for when explicitly asked to relax "win = full line."

def check_k_in_a_row(board: Board, row: int, col: int, symbol: str, k: int) -> bool:
    directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
    n = board.size
    for dr, dc in directions:
        count = 1
        for sign in (1, -1):
            r, c = row + sign * dr, col + sign * dc
            while 0 <= r < n and 0 <= c < n and board.grid[r][c] == symbol:
                count += 1
                r += sign * dr
                c += sign * dc
        if count >= k:
            return True
    return False

7. Edge Cases

  • Move on an already-occupied cell: Board.place returns False; caller must reject the move without mutating turn state.
  • Move out of bounds: validate 0 <= row, col < size before calling place — an unchecked index would raise on a plain list, which is arguably acceptable (fail loud) but should be a deliberate choice, not an accident.
  • Draw detection: must check after confirming no win — a full board with a winning move on the very last cell is a win, not a draw; checking is_full() before the win check would misreport it.

8. Extensibility

  • More than 2 players: the O(1) running-sum trick specifically relies on the ±1 encoding trick, which only works for exactly 2 players — for 3+ players, fall back to per-symbol counting per line (still avoidable full scans, but not the same elegant sum trick).
  • Different board shapes (hex grid, Connect Four's gravity-drop columns): Board.place becomes shape-aware (Connect Four: drop(col) finds the lowest empty row in that column instead of taking explicit row/col) — the WinChecker interface stays the same, only Board's placement semantics change.
  • Undo/replay: keep a move history list; undo pops the last move and reverses its effect on rows/cols/diag/anti_diag counters (each move's effect is a simple += delta, so reversal is -= delta) — cheap because of the same running-sum design.

9. Interview Drills

  1. Your naive win-checker is O(N) per move. The interviewer asks for O(1). Walk through the fix. — Maintain running sums per row/column/diagonal with player 1 as +1 and player 2 as -1; a line is won the instant its sum's absolute value hits N. Each move updates only the 2–4 counters the placed cell participates in, and checks those same counters — no scan.
  2. Does the O(1) trick work for "5 in a row on a 15x15 board" (K < N)? — No — a line sum of magnitude 5 on a 15-length row doesn't tell you the 5 marks are consecutive; they could be scattered. For K-in-a-row shorter than the full line, check consecutive-run length outward from the just-placed cell in each of the 4 directions instead.
  3. How would you add a 3-player variant? — The ±1 sum-encoding is specific to exactly 2 players; for 3+, switch to per-symbol run/count tracking per line (e.g., a dict of symbol → count per row/col/diagonal), checking if any symbol's count in a line reaches N — loses the single-sum elegance but keeps the same O(1)-per-move discipline.

Cross-links

[[OOD Design Patterns]] · [[SOLID Principles]] · [[Vending Machine]]