Courses › Low-Level Design › Problem Walkthroughs

Design Tic-Tac-Toe

Board games skeleton, O(1) win detection and generalizing to N×N and other games.

Board games (Tic-Tac-Toe, Connect Four, Snakes and Ladders, Chess) are a family of LLD questions with the same skeleton: a board, players, a turn loop, move validation and a win check. Tic-Tac-Toe is the smallest member of the family, so interviewers expect a clean model and then push on two follow-ups: an O(1) win check and generalizing to N×N or other games.

Requirements

• Two players take turns placing their mark on a 3×3 grid.
• A move must be on an empty cell, made by the player whose turn it is.
• The game ends when a player fills a row, column or diagonal, or when the board is full (a draw).
• Extensions to plan for: an N×N board, K in a row to win, a computer player, undo.

Model

Player (name, symbol)             HumanPlayer / BotPlayer via a MoveStrategy
Board  (n, grid)                  place(r, c, symbol), is_full(), cell(r, c)
WinChecker (interface)            record(r, c, player) -> bool
GameStatus (Enum)                 IN_PROGRESS, WON, DRAW
Game   (board, players, turn, status, winner)   play(r, c)

Keeping rules apart from the board is the key separation. The Board only stores marks. The Game enforces turns and status. Win detection is its own component, so Connect Four can swap in a different one.

O(1) win detection

Re-scanning every line after each move costs O(n²) per move on an N×N board. Instead, keep counters per row, per column and for both diagonals. Player 1 adds +1 and player 2 adds −1. A line belongs to one player when its counter reaches ±n.

from enum import Enum


class GameStatus(Enum):
    IN_PROGRESS = "in_progress"
    WON = "won"
    DRAW = "draw"


class InvalidMove(Exception):
    pass


class Player:
    def __init__(self, name, symbol):
        self.name, self.symbol = name, symbol


class Board:
    def __init__(self, n=3):
        self.n = n
        self.grid = [[None] * n for _ in range(n)]
        self.filled = 0

    def place(self, r, c, symbol):
        if not (0 <= r < self.n and 0 <= c < self.n):
            raise InvalidMove("off the board")
        if self.grid[r][c] is not None:
            raise InvalidMove("cell taken")
        self.grid[r][c] = symbol
        self.filled += 1

    def is_full(self):
        return self.filled == self.n * self.n


class LineCounterWinChecker:
    """Detects n in a row on an n x n board in O(1) per move."""
    def __init__(self, n):
        self.n = n
        self.rows, self.cols = [0] * n, [0] * n
        self.diag = self.anti = 0

    def record(self, r, c, sign):           # sign is +1 or -1
        n = self.n
        self.rows[r] += sign
        self.cols[c] += sign
        if r == c:
            self.diag += sign
        if r + c == n - 1:
            self.anti += sign
        return n * sign in (self.rows[r], self.cols[c], self.diag, self.anti)


class Game:
    def __init__(self, p1, p2, n=3):
        self.board = Board(n)
        self.players = [p1, p2]
        self.turn = 0
        self.checker = LineCounterWinChecker(n)
        self.status = GameStatus.IN_PROGRESS
        self.winner = None

    @property
    def current(self):
        return self.players[self.turn]

    def play(self, r, c):
        if self.status is not GameStatus.IN_PROGRESS:
            raise InvalidMove("game is over")
        self.board.place(r, c, self.current.symbol)
        sign = 1 if self.turn == 0 else -1
        if self.checker.record(r, c, sign):
            self.status, self.winner = GameStatus.WON, self.current
        elif self.board.is_full():
            self.status = GameStatus.DRAW
        else:
            self.turn = 1 - self.turn
        return self.status

g = Game(Player("Ana", "X"), Player("Bo", "O"))
for r, c in [(0, 0), (1, 1), (0, 1), (2, 2), (0, 2)]:
    status = g.play(r, c)
assert status is GameStatus.WON and g.winner.name == "Ana"

[!INTERVIEW] Validate before you mutate play checks the game status, and Board.place checks the bounds and the cell, before any state changes. A failed move leaves the game untouched. Point this out, because it's what makes undo and retries safe.

Generalizing

• K in a row on a larger board (Gomoku, Connect Four): line counters no longer work. After each move, count consecutive marks from the new cell in four directions: horizontal, vertical and the two diagonals. That's O(k) per move. Put it behind the same WinChecker interface.
• Connect Four's gravity: a move takes a column, and the board finds the lowest empty row. That's a place_in_column method. Nothing else changes.
• More than two players: turn = (turn + 1) % len(players). Store the player ID in each cell instead of using ±1 counters.
• Computer player: give Player a MoveStrategy (HumanInput, RandomMove, MinimaxMove). The game loop asks the current player for a move without knowing which kind it is.
• Undo: keep a stack of moves. Undoing clears the cell and reverses the counter changes, which is easy because each move added exactly ±1. This is the Command pattern. See Design a Text Editor (Undo/Redo).

Other games in the family

[!TIP] Practice Tic-Tac-Toe · Connect Four · Snakes and Ladders · Snake Game · Chess · Blackjack