Design a Tic-Tac-Toe Game

Description

Tic-Tac-Toe is an object-oriented design favorite precisely because everyone knows the rules: the round is graded on whether your classes enforce them - whose turn it is, which moves are legal, when the game is won or drawn - and on how cheaply you detect a win and undo a move. This skill builds a game object that owns its rules, an O(1) win check with signed tallies, and exact undo from a move history.

Everyone knows the rules of Tic-Tac-Toe, which is exactly why it's an object-oriented design favorite: the grading is entirely about whether your classes enforce them. A typical first attempt:

class TicTacToe {
    char[][] board = new char[3][3];

    int move(int row, int col, char player) {
        board[row][col] = player;
        for (int i = 0; i < 3; i++) {                                     // rescan everything
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return 1;
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return 1;
        }
        return 0;
    }
}

class TicTacToe:
    def __init__(self):
        self.board = [[""] * 3 for _ in range(3)]

    def move(self, row: int, col: int, player: str) -> int:
        self.board[row][col] = player
        for i in range(3):                                                  # rescan everything
            if self.board[i][0] == self.board[i][1] == self.board[i][2] == player:
                return 1
            if self.board[0][i] == self.board[1][i] == self.board[2][i] == player:
                return 1
        return 0

It trusts the caller for everything: the same player can move twice, a move can overwrite a mark or land off the board (an ArrayIndexOutOfBoundsException from deep inside - and in Python, -1 is silently the last row), play continues after a win, and there's no draw. It forgets the diagonals, hard-codes 3, and rescans lines the move didn't touch. None of that shows in a happy-path demo - all of it shows in a test suite.

We'll go from simple to more technical:

1. Clarify, model and define the API - and why the game, not the caller, owns the turn.
2. The core: validate first, then update signed tallies per line.
3. Undo by reversing the last move exactly.
4. The bugs that come from changing state in the wrong order.

The approach

Same four steps as every object-oriented design round - clarify, model, define the API, build the core:

1. Clarify. Board size - always 3, or n? Does a win need the whole line, or k in a row? Who moves first? What does an illegal move do: return a code or throw? Is undo in scope?
2. Model. Two closed sets become enums: Player (X, O, with other()) and GameState (IN_PROGRESS, X_WON, O_WON, DRAW). One Game object owns the board, whose turn it is, the state, and the bookkeeping that makes win checks cheap.
3. API. play(row, col) - no player argument, because the game knows whose turn it is - returning the new state; state(), currentPlayer(), cellAt(row, col); undo().
4. Core. One running tally per row, per column and per diagonal, so a move checks only the lines through its own cell; and a stack of moves, so undo can reverse exactly what a move did.

The pieces in code

public GameState play(int row, int col) {
    if (state != GameState.IN_PROGRESS) throw new IllegalStateException("The game is over");
    if (row < 0 || row >= n || col < 0 || col >= n) throw new IllegalArgumentException("Off the board");
    if (board[row][col] != null) throw new IllegalArgumentException("Cell taken");

    Player player = current;
    board[row][col] = player;
    history.push(new int[] {row, col});
    if (addToLines(row, col, player == Player.X ? 1 : -1)) state = GameState.wonBy(player);
    else if (history.size() == n * n) state = GameState.DRAW;
    current = player.other();
    return state;
}

/** Adds delta to every line through (row, col); true if one of them is now full of one player's marks. */
private boolean addToLines(int row, int col, int delta) {
    rows[row] += delta;
    cols[col] += delta;
    if (row == col) diagonal += delta;
    if (row + col == n - 1) antiDiagonal += delta;
    return Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
            || (row == col && Math.abs(diagonal) == n)
            || (row + col == n - 1 && Math.abs(antiDiagonal) == n);
}

def play(self, row: int, col: int) -> GameState:
    if self._state is not GameState.IN_PROGRESS:
        raise RuntimeError("The game is over")
    if not (0 <= row < self._n and 0 <= col < self._n):
        raise ValueError("Off the board")
    if self._board[row][col] is not None:
        raise ValueError("Cell taken")

    player = self._current
    self._board[row][col] = player
    self._history.append((row, col))
    if self._add_to_lines(row, col, 1 if player is Player.X else -1):
        self._state = GameState.won_by(player)
    elif len(self._history) == self._n * self._n:
        self._state = GameState.DRAW
    self._current = player.other()
    return self._state

def _add_to_lines(self, row: int, col: int, delta: int) -> bool:
    """Adds delta to every line through (row, col); True if one of them is now full of one player's marks."""
    n = self._n
    self._rows[row] += delta
    self._cols[col] += delta
    if row == col:
        self._diagonal += delta
    if row + col == n - 1:
        self._anti_diagonal += delta
    return (abs(self._rows[row]) == n or abs(self._cols[col]) == n
            or (row == col and abs(self._diagonal) == n)
            or (row + col == n - 1 and abs(self._anti_diagonal) == n))

• Every check comes before the first change. A rejected move throws while the board, the turn and the history are untouched, so it changes nothing.
• The win check runs before the draw check. The last free cell can complete a line; that's a win, not a draw.
• Opposite signs are what make a tally mean "all one player's": with +1 for everyone, a full line of X X O reaches n and looks like a win.
• A cell is on the anti-diagonal when row + col == n - 1; forgetting that line is the classic bug, along with hard-coding 3 instead of n. (Python adds one more: [[None] * n] * n is n references to one row list, so every mark lands in every row - build the board with [[None] * n for _ in range(n)].)
• The illegal-state case gets IllegalStateException, not IllegalArgumentException (in Python, RuntimeError, not ValueError): the arguments are fine, but the game's state forbids the call.

Undo from a move history

The history stack makes undo exact: pop the last move, and run the same bookkeeping backwards.

public boolean undo() {
    if (history.isEmpty()) return false;
    int[] last = history.pop();
    Player player = board[last[0]][last[1]];
    board[last[0]][last[1]] = null;
    addToLines(last[0], last[1], player == Player.X ? -1 : 1);   // the opposite sign
    current = player;                       // that player's turn again
    state = GameState.IN_PROGRESS;          // safe: a finished game accepts no moves
    return true;
}

def undo(self) -> bool:
    if not self._history:
        return False
    row, col = self._history.pop()
    player = self._board[row][col]
    self._board[row][col] = None
    self._add_to_lines(row, col, -1 if player is Player.X else 1)   # the opposite sign
    self._current = player                    # that player's turn again
    self._state = GameState.IN_PROGRESS       # safe: a finished game accepts no moves
    return True

Setting the state to IN_PROGRESS unconditionally is correct for a reason worth saying out loud: moves are only accepted while the game is in progress, so the state before any move - including a winning one - was IN_PROGRESS. Clearing the cell and handing back the turn but forgetting the tallies is the typical bug: the lines still count the undone mark, and a later move "wins" a line that holds one mark too few.

Where you'll see it

In an online game the same Game lives on the server, which is the only authority: clients send intents ("X wants (1, 2)"), the server validates them exactly as play does, and broadcasts the result. The move history doubles as an event log - it's what makes replays, spectators joining late, and reconnecting clients possible (replay the moves to rebuild the board). Chess and Go servers work this way.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does play take only (row, col) and not the player?

2. On a 3 × 3 board X plays (0, 0), O plays (2, 0), X plays (0, 1), then X's move is undone and X plays (0, 2). An undo that forgot the tallies reports what, and why?

3. The ninth move on a 3 × 3 board completes a row. Which state should play return, and what ordering bug gets it wrong?

Key takeaways

• The game object owns its rules: whose turn it is, which moves are legal, when it's over. Callers ask; they don't pass the player or set the state.
• Validate completely, then change - a rejected move must leave everything as it was. Moves after the end are an IllegalStateException.
• Signed tallies per row, column and diagonal find a win in O(1) per move; the anti-diagonal is row + col == n - 1; check for a win before a draw.
• Undo pops the last move from a history and reverses exactly what it did - cell, tallies, turn and state.
• Tallies need whole-line wins; for k in a row, count the run outward from the new stone instead.