⏱️ 25 min read

Designing Tic-Tac-Toe

Difficulty: Beginner Patterns: Strategy, State, Factory Asked at: Amazon, PhonePe, Flipkart, Adobe, Walmart

Tic-Tac-Toe is a warm-up problem, but interviewers use it to check two things: can you generalise 3×3 to N×N without special-casing, and can you detect a win in O(1) per move instead of re-scanning the board every time? Get those right and the rest — turns, validation, draw detection — is straightforward. The trap is hardcoding “3”, eight win-lines, and an O(N²) scan after each move.

Functional Requirements

Board is N×N (3×3 by default, but the code must not assume 3).
Two players, each with a distinct symbol (X / O), taking turns.
A move places a symbol in an empty cell; occupied or out-of-bounds moves are rejected.
Detect a win: a full row, column, or either diagonal of one symbol.
Detect a draw: board full with no winner.
Win detection should be O(1) per move (no full-board rescans).

Non-Functional Requirements

Extensibility — support more players, bigger boards, or new win rules with minimal change.
Clean separation — the board doesn’t know about turn order; the game doesn’t know how cells are stored.
Robust validation — no move ever corrupts game state.

Core Entities

Entity	Description
`Symbol`	A player’s mark (X, O, …) — value object over a char
`Player`	Name + symbol
`Cell`	One board square; empty or holding a symbol
`Board`	N×N grid; applies moves, exposes cell state
`WinningStrategy`	Decides whether the last move won
`RowColDiagonalStrategy`	O(1) win check via running tallies
`GameState`	Enum: IN_PROGRESS, WIN, DRAW
`Game`	Orchestrates players, turns, the board, and the strategy

The O(1) win-check insight

The naive check rescans the placed cell’s row, column, and diagonals after every move — O(N) per move, and you re-derive the eight lines each time. The clean trick: keep running counts. For each row, column, and the two diagonals, track a signed tally per symbol. When a symbol is placed, increment the relevant tallies; if any reaches N, that line is complete — a win. Each move touches at most 4 counters, so it’s O(1).

💡 This is the same “maintain an aggregate incrementally instead of recomputing it” idea behind running sums and streaming statistics — the interviewer wants to see you avoid the rescan.

classDiagram
    class Symbol {
        -char mark
    }

    class Player {
        -String name
        -Symbol symbol
    }

    class Cell {
        -int row
        -int col
        -Symbol symbol
        +isEmpty() boolean
    }

    class Board {
        -int size
        -Cell[][] grid
        -int filledCells
        +place(int r, int c, Symbol) boolean
        +isFull() boolean
        +isValid(int r, int c) boolean
    }

    class WinningStrategy {
        <<interface>>
        +checkWin(Board, int r, int c, Symbol) boolean
    }

    class RowColDiagonalStrategy {
        -Map counts
        +checkWin(Board, int, int, Symbol) boolean
    }

    class Game {
        -Board board
        -Deque~Player~ players
        -WinningStrategy strategy
        -GameState state
        +move(int r, int c) GameState
    }

    WinningStrategy <|.. RowColDiagonalStrategy
    Game --> Board
    Game --> Player
    Game --> WinningStrategy
    Board --> Cell
    Player --> Symbol
    Cell --> Symbol

Design Patterns

Pattern	Where	Why
Strategy	`WinningStrategy`	Swap win rules — standard lines, or “3-in-a-row on a 5×5” (Gomoku-style) — without touching the game loop.
State	`GameState` enum drives the loop	The game stops accepting moves once it’s WIN or DRAW.
Factory (extension)	Board / player creation	Configure 3×3 two-player or N×N multi-player from one place.
Command (extension)	Moves as objects	Enables undo/redo and replay.

Data Structures

Component	Structure	Why
Grid	`Cell[][]`	Direct O(1) access by (row, col)
Win tallies	`int[] rows`, `int[] cols`, `int diag`, `int antiDiag` per symbol	O(1) win check; increment on place
Turn order	`ArrayDeque<Player>` (rotate)	Poll front, offer back — trivially extends past 2 players
Fill count	single `int filledCells`	O(1) draw detection, no board scan

Using a Deque for players is the small touch that makes “add a third player” a non-event: you rotate the queue instead of flipping a boolean.

Complete Code

Symbol.java

A value object wrapping the player’s mark. Wrapping it (rather than passing raw char) leaves room to attach colour, avatar, or scoring later without changing signatures everywhere.

package tictactoe.model;

public class Symbol {
    private final char mark;

    public Symbol(char mark) { this.mark = mark; }

    public char getMark() { return mark; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Symbol)) return false;
        return mark == ((Symbol) o).mark;
    }

    @Override public int hashCode() { return Character.hashCode(mark); }
    @Override public String toString() { return String.valueOf(mark); }
}

class Symbol:
    def __init__(self, mark: str) -> None:
        self._mark: str = mark

    @property
    def mark(self) -> str:
        return self._mark

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Symbol):
            return False
        return self._mark == other._mark

    def __hash__(self) -> int:
        return hash(self._mark)

    def __repr__(self) -> str:
        return self._mark

#pragma once
#include <string>
#include <functional>

class Symbol {
    char mark_;
public:
    explicit Symbol(char mark) : mark_(mark) {}

    char getMark() const { return mark_; }

    bool operator==(const Symbol& other) const { return mark_ == other.mark_; }
    bool operator!=(const Symbol& other) const { return !(*this == other); }

    std::string toString() const { return std::string(1, mark_); }
};

// Hash support for use in unordered containers
namespace std {
    template<>
    struct hash<Symbol> {
        size_t operator()(const Symbol& s) const {
            return hash<char>{}(s.getMark());
        }
    };
}

class Symbol {
    #mark;

    constructor(mark) {
        this.#mark = mark;
    }

    get mark() {
        return this.#mark;
    }

    equals(other) {
        if (!(other instanceof Symbol)) return false;
        return this.#mark === other.#mark;
    }

    toString() {
        return this.#mark;
    }
}

Player.java

package tictactoe.model;

public class Player {
    private final String name;
    private final Symbol symbol;

    public Player(String name, Symbol symbol) {
        this.name = name;
        this.symbol = symbol;
    }

    public String getName() { return name; }
    public Symbol getSymbol() { return symbol; }

    @Override public String toString() { return name + " (" + symbol + ")"; }
}

class Player:
    def __init__(self, name: str, symbol: Symbol) -> None:
        self._name: str = name
        self._symbol: Symbol = symbol

    @property
    def name(self) -> str:
        return self._name

    @property
    def symbol(self) -> Symbol:
        return self._symbol

    def __repr__(self) -> str:
        return f"{self._name} ({self._symbol})"

#pragma once
#include <string>
#include "Symbol.h"

class Player {
    std::string name_;
    Symbol symbol_;
public:
    Player(std::string name, Symbol symbol)
        : name_(std::move(name)), symbol_(symbol) {}

    const std::string& getName() const { return name_; }
    const Symbol& getSymbol() const { return symbol_; }

    std::string toString() const {
        return name_ + " (" + symbol_.toString() + ")";
    }
};

class Player {
    #name;
    #symbol;

    constructor(name, symbol) {
        this.#name = name;
        this.#symbol = symbol;
    }

    get name() {
        return this.#name;
    }

    get symbol() {
        return this.#symbol;
    }

    toString() {
        return `${this.#name} (${this.#symbol})`;
    }
}

Cell.java

package tictactoe.model;

public class Cell {
    private final int row, col;
    private Symbol symbol; // null = empty

    public Cell(int row, int col) { this.row = row; this.col = col; }

    public boolean isEmpty() { return symbol == null; }
    public Symbol getSymbol() { return symbol; }
    public void setSymbol(Symbol s) { this.symbol = s; }
    public int getRow() { return row; }
    public int getCol() { return col; }
}

from typing import Optional


class Cell:
    def __init__(self, row: int, col: int) -> None:
        self._row: int = row
        self._col: int = col
        self._symbol: Optional[Symbol] = None

    def is_empty(self) -> bool:
        return self._symbol is None

    @property
    def symbol(self) -> Optional[Symbol]:
        return self._symbol

    @symbol.setter
    def symbol(self, s: Symbol) -> None:
        self._symbol = s

    @property
    def row(self) -> int:
        return self._row

    @property
    def col(self) -> int:
        return self._col

#pragma once
#include <optional>
#include "Symbol.h"

class Cell {
    int row_, col_;
    std::optional<Symbol> symbol_;  // nullopt = empty
public:
    Cell() : row_(0), col_(0) {}
    Cell(int row, int col) : row_(row), col_(col) {}

    bool isEmpty() const { return !symbol_.has_value(); }
    const std::optional<Symbol>& getSymbol() const { return symbol_; }
    void setSymbol(Symbol s) { symbol_ = s; }
    int getRow() const { return row_; }
    int getCol() const { return col_; }
};

class Cell {
    #row;
    #col;
    #symbol;

    constructor(row, col) {
        this.#row = row;
        this.#col = col;
        this.#symbol = null; // null = empty
    }

    isEmpty() {
        return this.#symbol === null;
    }

    get symbol() {
        return this.#symbol;
    }

    set symbol(s) {
        this.#symbol = s;
    }

    get row() {
        return this.#row;
    }

    get col() {
        return this.#col;
    }
}

Board.java

Owns the grid and the only mutation path (place). It validates bounds and emptiness, tracks a filledCells counter for O(1) draw detection, and prints itself — but it knows nothing about turns or winning. Single responsibility: hold and mutate the grid.

package tictactoe.model;

public class Board {
    private final int size;
    private final Cell[][] grid;
    private int filledCells = 0;

    public Board(int size) {
        this.size = size;
        this.grid = new Cell[size][size];
        for (int r = 0; r < size; r++)
            for (int c = 0; c < size; c++)
                grid[r][c] = new Cell(r, c);
    }

    public boolean isValid(int r, int c) {
        return r >= 0 && r < size && c >= 0 && c < size && grid[r][c].isEmpty();
    }

    /** Place a symbol. Returns false if the move is illegal (caller decides what to do). */
    public boolean place(int r, int c, Symbol symbol) {
        if (!isValid(r, c)) return false;
        grid[r][c].setSymbol(symbol);
        filledCells++;
        return true;
    }

    public boolean isFull() { return filledCells == size * size; }
    public int getSize() { return size; }
    public Cell getCell(int r, int c) { return grid[r][c]; }

    public void print() {
        for (int r = 0; r < size; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < size; c++) {
                sb.append(grid[r][c].isEmpty() ? "." : grid[r][c].getSymbol());
                if (c < size - 1) sb.append(" | ");
            }
            System.out.println("  " + sb);
        }
        System.out.println();
    }
}

class Board:
    def __init__(self, size: int) -> None:
        self._size: int = size
        self._grid: list[list[Cell]] = [
            [Cell(r, c) for c in range(size)] for r in range(size)
        ]
        self._filled_cells: int = 0

    def is_valid(self, r: int, c: int) -> bool:
        return 0 <= r < self._size and 0 <= c < self._size and self._grid[r][c].is_empty()

    def place(self, r: int, c: int, symbol: Symbol) -> bool:
        """Place a symbol. Returns False if the move is illegal."""
        if not self.is_valid(r, c):
            return False
        self._grid[r][c].symbol = symbol
        self._filled_cells += 1
        return True

    def is_full(self) -> bool:
        return self._filled_cells == self._size * self._size

    @property
    def size(self) -> int:
        return self._size

    def get_cell(self, r: int, c: int) -> Cell:
        return self._grid[r][c]

    def print_board(self) -> None:
        for r in range(self._size):
            row_str = " | ".join(
                "." if self._grid[r][c].is_empty() else str(self._grid[r][c].symbol)
                for c in range(self._size)
            )
            print(f"  {row_str}")
        print()

#pragma once
#include <vector>
#include <iostream>
#include "Cell.h"

class Board {
    int size_;
    std::vector<std::vector<Cell>> grid_;
    int filledCells_ = 0;

public:
    explicit Board(int size) : size_(size), grid_(size, std::vector<Cell>(size)) {
        for (int r = 0; r < size; ++r)
            for (int c = 0; c < size; ++c)
                grid_[r][c] = Cell(r, c);
    }

    bool isValid(int r, int c) const {
        return r >= 0 && r < size_ && c >= 0 && c < size_ && grid_[r][c].isEmpty();
    }

    /** Place a symbol. Returns false if the move is illegal. */
    bool place(int r, int c, Symbol symbol) {
        if (!isValid(r, c)) return false;
        grid_[r][c].setSymbol(symbol);
        filledCells_++;
        return true;
    }

    bool isFull() const { return filledCells_ == size_ * size_; }
    int getSize() const { return size_; }
    const Cell& getCell(int r, int c) const { return grid_[r][c]; }

    void print() const {
        for (int r = 0; r < size_; ++r) {
            std::cout << "  ";
            for (int c = 0; c < size_; ++c) {
                if (grid_[r][c].isEmpty()) std::cout << ".";
                else std::cout << grid_[r][c].getSymbol()->toString();
                if (c < size_ - 1) std::cout << " | ";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
    }
};

class Board {
    #size;
    #grid;
    #filledCells;

    constructor(size) {
        this.#size = size;
        this.#filledCells = 0;
        this.#grid = Array.from({ length: size }, (_, r) =>
            Array.from({ length: size }, (_, c) => new Cell(r, c))
        );
    }

    isValid(r, c) {
        return r >= 0 && r < this.#size && c >= 0 && c < this.#size && this.#grid[r][c].isEmpty();
    }

    /** Place a symbol. Returns false if the move is illegal. */
    place(r, c, symbol) {
        if (!this.isValid(r, c)) return false;
        this.#grid[r][c].symbol = symbol;
        this.#filledCells++;
        return true;
    }

    isFull() {
        return this.#filledCells === this.#size * this.#size;
    }

    get size() {
        return this.#size;
    }

    getCell(r, c) {
        return this.#grid[r][c];
    }

    print() {
        for (let r = 0; r < this.#size; r++) {
            const row = Array.from({ length: this.#size }, (_, c) =>
                this.#grid[r][c].isEmpty() ? "." : this.#grid[r][c].symbol.toString()
            ).join(" | ");
            console.log(`  ${row}`);
        }
        console.log();
    }
}

WinningStrategy.java (Strategy interface)

package tictactoe.strategy;

import tictactoe.model.Board;
import tictactoe.model.Symbol;

public interface WinningStrategy {
    /** Called right after (r,c) was set to `symbol`. Return true if that move wins. */
    boolean checkWin(Board board, int r, int c, Symbol symbol);
}

from abc import ABC, abstractmethod


class WinningStrategy(ABC):
    """Called right after (r,c) was set to symbol. Return True if that move wins."""

    @abstractmethod
    def check_win(self, board: "Board", r: int, c: int, symbol: Symbol) -> bool:
        ...

#pragma once
#include "Board.h"
#include "Symbol.h"

class WinningStrategy {
public:
    virtual ~WinningStrategy() = default;

    /** Called right after (r,c) was set to symbol. Return true if that move wins. */
    virtual bool checkWin(const Board& board, int r, int c, const Symbol& symbol) = 0;
};

/** @abstract */
class WinningStrategy {
    /** Called right after (r,c) was set to symbol. Return true if that move wins. */
    checkWin(board, r, c, symbol) {
        throw new Error("checkWin() must be implemented by subclass");
    }
}

RowColDiagonalStrategy.java

The O(1) heart of the design. It keeps per-symbol tallies for every row, every column, and the two diagonals. Placing a symbol bumps at most four counters; if any hits N, that line is full and the move wins — no board rescan.

package tictactoe.strategy;

import tictactoe.model.Board;
import tictactoe.model.Symbol;

import java.util.HashMap;
import java.util.Map;

public class RowColDiagonalStrategy implements WinningStrategy {
    private final int size;

    // Per-symbol running tallies.
    private final Map<Symbol, int[]> rowCounts = new HashMap<>();
    private final Map<Symbol, int[]> colCounts = new HashMap<>();
    private final Map<Symbol, Integer> diagCounts = new HashMap<>();
    private final Map<Symbol, Integer> antiDiagCounts = new HashMap<>();

    public RowColDiagonalStrategy(int size) { this.size = size; }

    @Override
    public boolean checkWin(Board board, int r, int c, Symbol symbol) {
        rowCounts.putIfAbsent(symbol, new int[size]);
        colCounts.putIfAbsent(symbol, new int[size]);

        int[] rows = rowCounts.get(symbol);
        int[] cols = colCounts.get(symbol);

        if (++rows[r] == size) return true;
        if (++cols[c] == size) return true;

        if (r == c) { // main diagonal
            int d = diagCounts.merge(symbol, 1, Integer::sum);
            if (d == size) return true;
        }
        if (r + c == size - 1) { // anti-diagonal
            int a = antiDiagCounts.merge(symbol, 1, Integer::sum);
            if (a == size) return true;
        }
        return false;
    }
}

from collections import defaultdict


class RowColDiagonalStrategy(WinningStrategy):
    def __init__(self, size: int) -> None:
        self._size: int = size
        # Per-symbol running tallies
        self._row_counts: dict[Symbol, list[int]] = defaultdict(lambda: [0] * size)
        self._col_counts: dict[Symbol, list[int]] = defaultdict(lambda: [0] * size)
        self._diag_counts: dict[Symbol, int] = defaultdict(int)
        self._anti_diag_counts: dict[Symbol, int] = defaultdict(int)

    def check_win(self, board: "Board", r: int, c: int, symbol: Symbol) -> bool:
        rows = self._row_counts[symbol]
        cols = self._col_counts[symbol]

        rows[r] += 1
        if rows[r] == self._size:
            return True

        cols[c] += 1
        if cols[c] == self._size:
            return True

        if r == c:  # main diagonal
            self._diag_counts[symbol] += 1
            if self._diag_counts[symbol] == self._size:
                return True

        if r + c == self._size - 1:  # anti-diagonal
            self._anti_diag_counts[symbol] += 1
            if self._anti_diag_counts[symbol] == self._size:
                return True

        return False

#pragma once
#include <unordered_map>
#include <vector>
#include "WinningStrategy.h"

class RowColDiagonalStrategy : public WinningStrategy {
    int size_;

    // Per-symbol running tallies
    std::unordered_map<Symbol, std::vector<int>> rowCounts_;
    std::unordered_map<Symbol, std::vector<int>> colCounts_;
    std::unordered_map<Symbol, int> diagCounts_;
    std::unordered_map<Symbol, int> antiDiagCounts_;

public:
    explicit RowColDiagonalStrategy(int size) : size_(size) {}

    bool checkWin(const Board& board, int r, int c, const Symbol& symbol) override {
        auto& rows = rowCounts_.try_emplace(symbol, size_, 0).first->second;
        auto& cols = colCounts_.try_emplace(symbol, size_, 0).first->second;

        if (++rows[r] == size_) return true;
        if (++cols[c] == size_) return true;

        if (r == c) { // main diagonal
            if (++diagCounts_[symbol] == size_) return true;
        }
        if (r + c == size_ - 1) { // anti-diagonal
            if (++antiDiagCounts_[symbol] == size_) return true;
        }
        return false;
    }
};

class RowColDiagonalStrategy extends WinningStrategy {
    #size;
    #rowCounts;
    #colCounts;
    #diagCounts;
    #antiDiagCounts;

    constructor(size) {
        super();
        this.#size = size;
        // Per-symbol running tallies (keyed by symbol's mark character)
        this.#rowCounts = new Map();
        this.#colCounts = new Map();
        this.#diagCounts = new Map();
        this.#antiDiagCounts = new Map();
    }

    checkWin(board, r, c, symbol) {
        const key = symbol.mark;

        if (!this.#rowCounts.has(key)) this.#rowCounts.set(key, new Array(this.#size).fill(0));
        if (!this.#colCounts.has(key)) this.#colCounts.set(key, new Array(this.#size).fill(0));

        const rows = this.#rowCounts.get(key);
        const cols = this.#colCounts.get(key);

        if (++rows[r] === this.#size) return true;
        if (++cols[c] === this.#size) return true;

        if (r === c) { // main diagonal
            const d = (this.#diagCounts.get(key) || 0) + 1;
            this.#diagCounts.set(key, d);
            if (d === this.#size) return true;
        }
        if (r + c === this.#size - 1) { // anti-diagonal
            const a = (this.#antiDiagCounts.get(key) || 0) + 1;
            this.#antiDiagCounts.set(key, a);
            if (a === this.#size) return true;
        }
        return false;
    }
}

GameState.java

package tictactoe.model;

public enum GameState {
    IN_PROGRESS, WIN, DRAW
}

from enum import Enum


class GameState(Enum):
    IN_PROGRESS = "IN_PROGRESS"
    WIN = "WIN"
    DRAW = "DRAW"

#pragma once

enum class GameState {
    IN_PROGRESS,
    WIN,
    DRAW
};

const GameState = Object.freeze({
    IN_PROGRESS: "IN_PROGRESS",
    WIN: "WIN",
    DRAW: "DRAW",
});

Game.java (Orchestrator)

Ties it together: rotates players via a Deque, applies each move through the board, asks the strategy whether it won, and flips to WIN/DRAW when appropriate. Once the game is over it refuses further moves — the GameState acts as the guard.

package tictactoe;

import tictactoe.model.*;
import tictactoe.strategy.RowColDiagonalStrategy;
import tictactoe.strategy.WinningStrategy;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Game {
    private final Board board;
    private final Deque<Player> players = new ArrayDeque<>();
    private final WinningStrategy strategy;
    private GameState state = GameState.IN_PROGRESS;
    private Player winner;

    public Game(int size, List<Player> playerList) {
        this.board = new Board(size);
        this.players.addAll(playerList);
        this.strategy = new RowColDiagonalStrategy(size);
    }

    /** Play the current player's move at (r,c). Returns the new game state. */
    public GameState move(int r, int c) {
        if (state != GameState.IN_PROGRESS) {
            System.out.println("✗ Game is over.");
            return state;
        }

        Player current = players.peekFirst();
        if (!board.place(r, c, current.getSymbol())) {
            System.out.println("✗ Illegal move at (" + r + "," + c + ") by " + current.getName());
            return state; // same player retries; turn not consumed
        }

        System.out.println(current.getName() + " → (" + r + "," + c + ")");

        if (strategy.checkWin(board, r, c, current.getSymbol())) {
            state = GameState.WIN;
            winner = current;
        } else if (board.isFull()) {
            state = GameState.DRAW;
        } else {
            players.addLast(players.pollFirst()); // rotate turn
        }
        return state;
    }

    public GameState getState() { return state; }
    public Player getWinner() { return winner; }
    public void print() { board.print(); }
}

from collections import deque


class Game:
    def __init__(self, size: int, player_list: list[Player]) -> None:
        self._board = Board(size)
        self._players: deque[Player] = deque(player_list)
        self._strategy: WinningStrategy = RowColDiagonalStrategy(size)
        self._state: GameState = GameState.IN_PROGRESS
        self._winner: Player | None = None

    def move(self, r: int, c: int) -> GameState:
        """Play the current player's move at (r,c). Returns the new game state."""
        if self._state != GameState.IN_PROGRESS:
            print("✗ Game is over.")
            return self._state

        current = self._players[0]
        if not self._board.place(r, c, current.symbol):
            print(f"✗ Illegal move at ({r},{c}) by {current.name}")
            return self._state  # same player retries; turn not consumed

        print(f"{current.name} → ({r},{c})")

        if self._strategy.check_win(self._board, r, c, current.symbol):
            self._state = GameState.WIN
            self._winner = current
        elif self._board.is_full():
            self._state = GameState.DRAW
        else:
            self._players.append(self._players.popleft())  # rotate turn

        return self._state

    @property
    def state(self) -> GameState:
        return self._state

    @property
    def winner(self) -> Player | None:
        return self._winner

    def print_board(self) -> None:
        self._board.print_board()

#pragma once
#include <deque>
#include <vector>
#include <iostream>
#include <memory>
#include "Board.h"
#include "Player.h"
#include "RowColDiagonalStrategy.h"

class Game {
    Board board_;
    std::deque<Player> players_;
    std::unique_ptr<WinningStrategy> strategy_;
    GameState state_ = GameState::IN_PROGRESS;
    const Player* winner_ = nullptr;

public:
    Game(int size, const std::vector<Player>& playerList)
        : board_(size),
          players_(playerList.begin(), playerList.end()),
          strategy_(std::make_unique<RowColDiagonalStrategy>(size)) {}

    /** Play the current player's move at (r,c). Returns the new game state. */
    GameState move(int r, int c) {
        if (state_ != GameState::IN_PROGRESS) {
            std::cout << "✗ Game is over.\n";
            return state_;
        }

        Player& current = players_.front();
        if (!board_.place(r, c, current.getSymbol())) {
            std::cout << "✗ Illegal move at (" << r << "," << c
                      << ") by " << current.getName() << "\n";
            return state_;
        }

        std::cout << current.getName() << " → (" << r << "," << c << ")\n";

        if (strategy_->checkWin(board_, r, c, current.getSymbol())) {
            state_ = GameState::WIN;
            winner_ = &current;
        } else if (board_.isFull()) {
            state_ = GameState::DRAW;
        } else {
            players_.push_back(players_.front());
            players_.pop_front();  // rotate turn
        }
        return state_;
    }

    GameState getState() const { return state_; }
    const Player* getWinner() const { return winner_; }
    void print() const { board_.print(); }
};

class Game {
    #board;
    #players;
    #strategy;
    #state;
    #winner;

    constructor(size, playerList) {
        this.#board = new Board(size);
        this.#players = [...playerList];
        this.#strategy = new RowColDiagonalStrategy(size);
        this.#state = GameState.IN_PROGRESS;
        this.#winner = null;
    }

    /** Play the current player's move at (r,c). Returns the new game state. */
    move(r, c) {
        if (this.#state !== GameState.IN_PROGRESS) {
            console.log("✗ Game is over.");
            return this.#state;
        }

        const current = this.#players[0];
        if (!this.#board.place(r, c, current.symbol)) {
            console.log(`✗ Illegal move at (${r},${c}) by ${current.name}`);
            return this.#state; // same player retries; turn not consumed
        }

        console.log(`${current.name} → (${r},${c})`);

        if (this.#strategy.checkWin(this.#board, r, c, current.symbol)) {
            this.#state = GameState.WIN;
            this.#winner = current;
        } else if (this.#board.isFull()) {
            this.#state = GameState.DRAW;
        } else {
            this.#players.push(this.#players.shift()); // rotate turn
        }
        return this.#state;
    }

    get state() {
        return this.#state;
    }

    get winner() {
        return this.#winner;
    }

    print() {
        this.#board.print();
    }
}

Demo.java (Runnable end-to-end)

Plays a full 3×3 game to a win, prints the board after each move, then re-uses the exact same classes for a 4×4 board — demonstrating that nothing was hardcoded to 3.

package tictactoe;

import tictactoe.model.*;

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        Player alice = new Player("Alice", new Symbol('X'));
        Player bob   = new Player("Bob",   new Symbol('O'));

        System.out.println("=== 3×3 game ===");
        Game game = new Game(3, Arrays.asList(alice, bob));

        // X wins on the top row.
        game.move(0, 0); // X
        game.move(1, 0); // O
        game.move(0, 1); // X
        game.move(1, 1); // O
        game.move(0, 2); // X → completes top row
        game.print();

        if (game.getState() == GameState.WIN)
            System.out.println("🏆 Winner: " + game.getWinner());
        else if (game.getState() == GameState.DRAW)
            System.out.println("🤝 Draw");

        System.out.println("\n=== Illegal move + same classes on a 4×4 board ===");
        Game big = new Game(4, Arrays.asList(alice, bob));
        big.move(0, 0);   // X
        big.move(0, 0);   // O tries an occupied cell → rejected, O retries
        big.move(1, 1);   // O
        big.print();
        System.out.println("State: " + big.getState());
    }
}

def main() -> None:
    alice = Player("Alice", Symbol("X"))
    bob = Player("Bob", Symbol("O"))

    print("=== 3×3 game ===")
    game = Game(3, [alice, bob])

    # X wins on the top row.
    game.move(0, 0)  # X
    game.move(1, 0)  # O
    game.move(0, 1)  # X
    game.move(1, 1)  # O
    game.move(0, 2)  # X → completes top row
    game.print_board()

    if game.state == GameState.WIN:
        print(f"🏆 Winner: {game.winner}")
    elif game.state == GameState.DRAW:
        print("🤝 Draw")

    print("\n=== Illegal move + same classes on a 4×4 board ===")
    big = Game(4, [alice, bob])
    big.move(0, 0)   # X
    big.move(0, 0)   # O tries an occupied cell → rejected, O retries
    big.move(1, 1)   # O
    big.print_board()
    print(f"State: {big.state}")


if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include "Game.h"

int main() {
    Player alice("Alice", Symbol('X'));
    Player bob("Bob", Symbol('O'));

    std::cout << "=== 3×3 game ===\n";
    Game game(3, {alice, bob});

    // X wins on the top row.
    game.move(0, 0); // X
    game.move(1, 0); // O
    game.move(0, 1); // X
    game.move(1, 1); // O
    game.move(0, 2); // X → completes top row
    game.print();

    if (game.getState() == GameState::WIN)
        std::cout << "🏆 Winner: " << game.getWinner()->toString() << "\n";
    else if (game.getState() == GameState::DRAW)
        std::cout << "🤝 Draw\n";

    std::cout << "\n=== Illegal move + same classes on a 4×4 board ===\n";
    Game big(4, {alice, bob});
    big.move(0, 0);   // X
    big.move(0, 0);   // O tries an occupied cell → rejected, O retries
    big.move(1, 1);   // O
    big.print();
    std::cout << "State: "
              << (big.getState() == GameState::IN_PROGRESS ? "IN_PROGRESS" :
                  big.getState() == GameState::WIN ? "WIN" : "DRAW") << "\n";
    return 0;
}

function main() {
    const alice = new Player("Alice", new Symbol("X"));
    const bob = new Player("Bob", new Symbol("O"));

    console.log("=== 3×3 game ===");
    const game = new Game(3, [alice, bob]);

    // X wins on the top row.
    game.move(0, 0); // X
    game.move(1, 0); // O
    game.move(0, 1); // X
    game.move(1, 1); // O
    game.move(0, 2); // X → completes top row
    game.print();

    if (game.state === GameState.WIN)
        console.log(`🏆 Winner: ${game.winner}`);
    else if (game.state === GameState.DRAW)
        console.log("🤝 Draw");

    console.log("\n=== Illegal move + same classes on a 4×4 board ===");
    const big = new Game(4, [alice, bob]);
    big.move(0, 0);   // X
    big.move(0, 0);   // O tries an occupied cell → rejected, O retries
    big.move(1, 1);   // O
    big.print();
    console.log(`State: ${big.state}`);
}

main();

Sequence Diagram — A Move

sequenceDiagram
    participant P as Player
    participant G as Game
    participant B as Board
    participant W as WinningStrategy

    P->>G: move(r, c)
    G->>B: place(r, c, symbol)
    B-->>G: true (valid)
    G->>W: checkWin(board, r, c, symbol)
    W->>W: bump row/col/diag tallies
    W-->>G: win? (tally == N)
    alt win
        G->>G: state = WIN
    else board full
        G->>G: state = DRAW
    else
        G->>G: rotate players
    end
    G-->>P: GameState

How to Extend

Extension	Implementation
N players	Add more `Player`s to the list — the `Deque` rotation already handles it
Gomoku (K-in-a-row)	New `KInARowStrategy implements WinningStrategy`
Undo/redo	Wrap moves as Command objects on a stack; reverse the tally increments
AI opponent	A `Player` subtype whose move is chosen by minimax over the board
Custom symbols	`Symbol` already abstracts the mark — pass any char
Persistence / replay	Log each `move()`; replay by re-applying in order

What Interviewers Look For

✅ Generalised to N×N — no hardcoded 3 or hardcoded win-lines
✅ O(1) win check — running tallies, not an O(N) rescan every move
✅ Strategy for win rules — swappable, so Gomoku is a new class
✅ Clean responsibilities — Board mutates the grid, Game runs turns, Strategy judges wins
✅ Deque for turns — extends past two players for free
✅ Illegal moves rejected without corrupting state — turn isn’t consumed on a bad move
✅ Runnable demo — a full win, an illegal move, and a different board size

Snake & Ladder — turn-based board game loop
Vending Machine — State pattern for action handling
Parking Lot — Strategy pattern for swappable behaviour

Scale this design past a single process and these are the concepts it runs into:

Performance Metrics → — the O(1) running-tally trick is the same maintain-an-aggregate-incrementally idea behind streaming percentiles
WebSockets vs SSE → — online play needs each move pushed to the opponent as it happens
Idempotency → — a move resent after a client timeout must not be applied twice

Designing Tic-Tac-Toe

Functional Requirements

Non-Functional Requirements

Core Entities

The O(1) win-check insight

Design Patterns

Data Structures

Complete Code

Symbol.java

Player.java

Cell.java

Board.java

WinningStrategy.java (Strategy interface)

RowColDiagonalStrategy.java

GameState.java

Game.java (Orchestrator)

Demo.java (Runnable end-to-end)

Sequence Diagram — A Move

How to Extend

What Interviewers Look For

Discussion

Install SystemCraft

Designing Tic-Tac-Toe

Functional Requirements

Non-Functional Requirements

Core Entities

The O(1) win-check insight

Design Patterns

Data Structures

Complete Code

Symbol.java

Player.java

Cell.java

Board.java

WinningStrategy.java (Strategy interface)

RowColDiagonalStrategy.java

GameState.java

Game.java (Orchestrator)

Demo.java (Runnable end-to-end)

Sequence Diagram — A Move

How to Extend

What Interviewers Look For

Related Designs

Related Concepts

Discussion

Shape what we build next

Install SystemCraft

Unlock AI Features