The 100 problems, solved / Games / 064 · Design tic-tac-toe

Design tic-tac-toe

Board, players and O(1) win detection, then an n×n and an infinite grid.

Problem 064 of 100GamesL32 Nov 2026
Concepts this design leans on

01The design, in the six-step framework

1. Requirements and use cases

Tic-tac-toe is small enough that the design is the whole test. An ex-Google interviewer has described grading it on the board representation the candidate picks, the win-check code, and whether the work finishes inside the hour. So the first choice to say out loud is what the board stores, because the win check and both follow-ups depend on it.

  • Two players take turns placing a mark on an empty cell of an n×n board.
  • After each move the game reports whether that move won, drew, or left the game in progress.
  • A move that is out of turn, out of bounds, on an occupied cell, or after the game ended is rejected with a clear error.
  • A player wins with a full row, column or diagonal.
  • A caller can read a cell to draw the board.

Out of scope: a computer opponent, networking, undo. Constraints: move is O(1) however large n is, because the classic follow-up asks for exactly that; memory is O(n) beyond the cells; the follow-up to an infinite grid with k in a row must not need a rewrite of the player-facing API.

2. Core entities and relationships

  • Mark: an enum of X and O, with other().
  • GameStatus: in progress, X won, O won, draw.
  • Board: the cells and the win counters; it answers "did this placement complete a line".
  • Game: whose turn it is and the status; it enforces the rules and owns the board.

The list stops at four classes on purpose. A Player class with no behaviour, a Cell class wrapping one value and a WinChecker with one caller would all add names without adding meaning. That is KISS and YAGNI applied to a 45-minute round.

RulesStateValuesGameboard: Boardturn: Markstatus: GameStatusmove(row, col) -> GameStatuscell(row, col) -> Mark | NoneBoardn: intcells: dictrows: list[int]cols: list[int]diag: intanti: intplace(row, col, mark) -> boolis_full() -> boolget(row, col)MarkXOother() -> MarkGameStatusIN_PROGRESSX_WONO_WONDRAW

The game composes its board: a board has no life outside a game, and nothing else may reach in and place a mark. That single path for changing state is what makes the invariants below hold.

3. Interfaces and key methods

from enum import Enum
from typing import Optional

class Mark(Enum):
    X = 1
    O = -1
    def other(self) -> "Mark":
        return Mark.O if self is Mark.X else Mark.X

class GameStatus(Enum):
    IN_PROGRESS = "in progress"
    X_WON = "X won"
    O_WON = "O won"
    DRAW = "draw"

class IllegalMove(Exception):
    """Out of bounds, occupied, or the game has ended."""

class Board:
    def __init__(self, n: int) -> None:
        """An empty n by n board."""
    def place(self, row: int, col: int, mark: Mark) -> bool:
        """Store the mark; return True if this placement completes a line."""
    def get(self, row: int, col: int) -> Optional[Mark]:
        """The mark at a cell, or None."""
    def is_full(self) -> bool:
        """True when every cell holds a mark."""

class Game:
    def __init__(self, n: int = 3, first: Mark = Mark.X) -> None:
        """A new game with `first` to move."""
    def move(self, row: int, col: int) -> GameStatus:
        """Play for the current player; raise IllegalMove and change nothing if invalid."""

Invariants: each counter equals the X count minus the O count on its line, so a line is complete exactly when the absolute value reaches n; an illegal move leaves all state untouched; once the status leaves IN_PROGRESS it never changes.

4. Design patterns and the choices behind them

Counters instead of rescanning the board

The force: the obvious win check scans the row, column and diagonals after each move, which is O(n). Because only the lines through the new mark can change, keep one signed counter per row and per column plus two diagonal counters. X adds one, O subtracts one. A count of n or −n means a full line, and a mixed line can never reach it, since any opposing mark pulls the total back. This is the central idea of modeling boards and grids: store what the win question needs, not only the picture.

The trade-off is worth saying. Counters only work when a win means a whole line. Once the rule is k in a row on a bigger board, the check goes back to walking outward from the new mark, as the extension below shows. For a 3×3 board a plain scan is also perfectly good, and saying so shows judgement.

A sparse board

Cells live in a dictionary keyed by (row, col) rather than a 2-D list. Memory then tracks moves rather than area, and the step to an unbounded board keeps the same get and place.

Encapsulated rules and a loud API

The force: a caller must not be able to place out of turn. Game holds the turn and the status and exposes one mutating verb, which is encapsulation doing real work. Illegal moves raise rather than returning a magic number, while a win is a normal return value; that line between outcome and misuse is method design. Names such as place, is_full and other mean the code reads without narration, which is what naming and readability asks for.

5. Core flow and code

  1. The caller invokes Game.move(row, col).
  2. The game refuses the move if the status is final.
  3. It calls Board.place, which validates bounds and emptiness, stores the mark, and updates the row, column and any diagonal counters.
  4. place returns True if a counter reached n in absolute value.
  5. The game sets the status to a win, or to a draw if the board is full, or passes the turn.
class Board:
    def __init__(self, n: int) -> None:
        if n < 1:
            raise ValueError("board size must be positive")
        self.n = n
        self.cells: dict = {}
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti = 0

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

    def is_full(self) -> bool:
        return len(self.cells) == self.n * self.n

    def place(self, row: int, col: int, mark: Mark) -> bool:
        if not (0 <= row < self.n and 0 <= col < self.n):
            raise IllegalMove(f"({row}, {col}) is off the board")
        if (row, col) in self.cells:
            raise IllegalMove(f"({row}, {col}) is taken")
        self.cells[(row, col)] = mark
        delta = mark.value
        self.rows[row] += delta
        self.cols[col] += delta
        if row == col:
            self.diag += delta
        if row + col == self.n - 1:
            self.anti += delta
        return self.n in (abs(self.rows[row]), abs(self.cols[col]), abs(self.diag), abs(self.anti))

class Game:
    def __init__(self, n: int = 3, first: Mark = Mark.X) -> None:
        self.board = Board(n)
        self.turn = first
        self.status = GameStatus.IN_PROGRESS

    def cell(self, row: int, col: int) -> Optional[Mark]:
        return self.board.get(row, col)

    def move(self, row: int, col: int) -> GameStatus:
        if self.status is not GameStatus.IN_PROGRESS:
            raise IllegalMove("the game is over")
        won = self.board.place(row, col, self.turn)
        if won:
            self.status = GameStatus.X_WON if self.turn is Mark.X else GameStatus.O_WON
        elif self.board.is_full():
            self.status = GameStatus.DRAW
        else:
            self.turn = self.turn.other()
        return self.status

class InfiniteBoard:
    """Follow-up: unbounded grid, win with k in a row. Walk outward from the new mark."""
    DIRECTIONS = ((0, 1), (1, 0), (1, 1), (1, -1))

    def __init__(self, k: int = 5) -> None:
        self.k = k
        self.cells: dict = {}

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

    def is_full(self) -> bool:
        return False

    def _run(self, row: int, col: int, dr: int, dc: int, mark: Mark) -> int:
        count = 0
        row, col = row + dr, col + dc
        while self.cells.get((row, col)) is mark and count < self.k:
            count += 1
            row, col = row + dr, col + dc
        return count

    def place(self, row: int, col: int, mark: Mark) -> bool:
        if (row, col) in self.cells:
            raise IllegalMove(f"({row}, {col}) is taken")
        self.cells[(row, col)] = mark
        return any(1 + self._run(row, col, dr, dc, mark) + self._run(row, col, -dr, -dc, mark) >= self.k
                   for dr, dc in self.DIRECTIONS)

InfiniteBoard has the same get, place and is_full methods as Board, so Game barely changes: it needs a constructor that accepts a board. The walk is capped at k steps each way, so a move costs O(k) however many marks are on the grid.

6. Extensions, concurrency and what interviewers probe

  • "Make the win check O(1)." That is the counters. Be ready to explain why a mixed line cannot reach n: every O cancels an X, so the sum reaches n only if all n marks are X.
  • "Infinite grid." Counters are gone because lines have no fixed set; the sparse dictionary and the outward walk replace them, in O(k) per move. This variant was reported from an Application Engineer loop.
  • "Add a computer player." Keep Game as it is and put a player object outside that reads cells and calls move; the rules stay in one place.
  • Concurrency: two clients on one game need one lock around move, because the turn check and the placement must be atomic. In practice a single-threaded game loop is simpler.
  • Test first: as the testing article advises, cover each line type on a 3×3 board, the anti-diagonal on an even board such as 4×4, a draw, a repeat cell that changes nothing, and a move after the game ended.
  • Common mistake: forgetting that a centre cell on an odd board lies on both diagonals (the two ifs must not be elif), and declaring a draw before checking for a win on the last move.

02Where this question was reported