TLDR: Tic-Tac-Toe looks trivial — until the interviewer says "make it N×N with P players and pluggable winning rules." The key design decisions: a Board abstracted from piece identity, a Strategy Pattern for win conditions, and a Factory for player creation. Getting these right is the interview objective.

---

🔍 The Basics: Object-Oriented Design for Games

A common interview mistake is designing Tic-Tac-Toe as a 3×3 hardcoded grid. The interviewer immediately asks: "What if I want a 10×10 board? Or 4-in-a-row instead of 3?" The design that handles this is what we're building.

Low-level design interviews test whether you can decompose a system into clean, extensible objects. The naive solution to Tic-Tac-Toe is always obvious — a fixed 3×3 array and two hardcoded players. The interview value lies entirely in the extensions.

OOP principles that matter for this design:

The interview trap: Interviewers will extend the requirements immediately. Expect:

• "Now support N×N boards"
• "Add a third player"
• "Support different winning conditions — like needing 4 in a row"
• "How would you add an undo feature?"

Each of these requirements is handled cleanly by a different design decision. Understanding why each design choice was made helps you answer extension questions confidently.

---

📖 From 3×3 Toy to OOP Interview Test

Every LLD interview question hides the same trap: the naive solution is obvious, so the interviewer immediately extends it. Tic-Tac-Toe is no different.

Naive version: a fixed 3×3 grid, two hardcoded players, if-else win check. Works in 30 lines.

Extended version: N×N board, P players with distinct symbols, swappable winning strategies (row, column, diagonal, custom), and clean state transitions. Requires deliberate OOP.

This post builds the extensible version step by step.

---

🔢 Core Entities — Board, Piece, Player, Game

A clean OOP model needs exactly four entities:

classDiagram
    class PlayingPiece {
        +PieceType type
    }
    class Player {
        +String name
        +PlayingPiece piece
    }
    class Board {
        +int size
        +PlayingPiece[][] grid
        +placePiece(row, col, piece)
        +isFull()
    }
    class Game {
        +Board board
        +Deque players
        +WinningStrategy strategy
        +startGame()
        +checkWinner(row, col, piece)
    }
    Player --> PlayingPiece
    Game --> Board
    Game --> Player
    Game --> WinningStrategy

Enums and value objects first:

enum PieceType { X, O, STAR, HASH }  // extensible — add symbols without changing Board

class PlayingPiece {
    final PieceType type;
    PlayingPiece(PieceType t) { this.type = t; }
}

class Player {
    final String name;
    final PlayingPiece piece;
    Player(String name, PlayingPiece piece) {
        this.name  = name;
        this.piece = piece;
    }
}

---

⚙️ Extending to N×N: Board with Variable Size

The Board must not hardcode 3. Size is a constructor parameter; the grid is a 2D array of nullable PlayingPiece.

class Board {
    final int size;
    private final PlayingPiece[][] grid;

    Board(int size) {
        this.size = size;
        this.grid = new PlayingPiece[size][size];
    }

    public boolean placePiece(int row, int col, PlayingPiece piece) {
        if (row < 0 || row >= size || col < 0 || col >= size) return false;
        if (grid[row][col] != null) return false;   // cell occupied
        grid[row][col] = piece;
        return true;
    }

    public PlayingPiece getPiece(int row, int col) { return grid[row][col]; }

    public boolean isFull() {
        for (PlayingPiece[] row : grid)
            for (PlayingPiece p : row)
                if (p == null) return false;
        return true;
    }
}

Multiple player support — use a Deque for round-robin turns, regardless of player count:

Deque<Player> players = new LinkedList<>();
players.add(new Player("Alice", new PlayingPiece(PieceType.X)));
players.add(new Player("Bob",   new PlayingPiece(PieceType.O)));
players.add(new Player("Carol", new PlayingPiece(PieceType.STAR)));

Each turn: poll() from front, play, then offerLast() to back.

---

🧱 OOP Pillars Applied in the Game Design

Each of the four OOP pillars maps directly onto a specific class or interface in this design — not as a textbook exercise, but as a concrete decision that makes the code extensible.

classDiagram
    direction LR
    class Player {
        <>
        +Piece piece
        +makeMove(Board) Move*
    }
    class HumanPlayer {
        +makeMove(Board) Move
    }
    class AiPlayer {
        +makeMove(Board) Move
    }
    class WinStrategy {
        <>
        +checkWin(Board, Piece) bool
    }
    class RowColWinStrategy
    class DiagonalWinStrategy
    HumanPlayer --|> Player : extends
    AiPlayer --|> Player : extends
    RowColWinStrategy ..|> WinStrategy : implements
    DiagonalWinStrategy ..|> WinStrategy : implements
    Game --> Player : uses
    Game --> WinStrategy : depends on

Encapsulation in practice: Board's constructor allocates grid as a private field. The only public surface is placePiece(row, col, piece), getPiece(row, col), and isFull(). If the internal representation changes from a 2D array to a Map<Position, Piece>, no external class breaks — callers never touch grid[row][col] directly.

Polymorphism in practice: the turn loop calls current.makeMove(board) on whichever Player is at the front of the deque. Whether that player reads from stdin, calls a REST endpoint, or runs a minimax tree search is completely invisible to Game.

---

✅ SOLID Principles in the Tic-Tac-Toe Design

Every SOLID principle surfaces in a specific, traceable design decision here — not as abstract advice:

OCP in practice: the product team wants a "diagonal-only" win rule for a new game variant. You write DiagonalOnlyWinStrategy implements WinStrategy. Existing Game, Board, and RowColWinStrategy are untouched. The open/closed boundary is the WinStrategy interface.

DIP in practice:

// Game depends on the abstraction — never on a concrete class
class Game {
    private final WinStrategy strategy;

    Game(Board board, List<Player> players, WinStrategy strategy) {
        this.strategy = strategy;   // injected — any WinStrategy works here
    }
}

// The call site decides which concrete strategy is used — Game never knows
Game standard = new Game(board, players, new RowColWinStrategy());
Game variant  = new Game(board, players, new DiagonalOnlyWinStrategy());

---

📐 Interface Contracts and the Extension Model

Three interfaces define the extension seams of the design. Each is narrow by design — a single responsibility, a single method:

// Win condition — injectable; Game calls this, never implements it
interface WinStrategy {
    boolean checkWin(Board board, Piece piece);
}

// Move validation — composable into Board or Game
interface MoveValidator {
    boolean isValid(Board board, int row, int col);
}

// Player contract — template method pattern; subclasses override the decision hook
abstract class Player {
    final Piece piece;
    Player(Piece piece) { this.piece = piece; }
    abstract Move makeMove(Board board);   // subclasses provide the decision algorithm
}

WinStrategy is the Strategy Pattern's policy interface. Game is the Context; RowColWinStrategy and DiagonalOnlyWinStrategy are ConcreteStrategy objects. Passing a different implementation at construction time changes the win rules — no other class is aware of the swap.

MoveValidator is intentionally separate from WinStrategy (ISP). An AI player that screens all candidate moves before picking the best one needs MoveValidator, but has no reason to implement win detection. Merging the two interfaces would force a no-op checkWin on any class that only validates moves.

Player as a Template Method: final Piece piece is set once at construction — no subclass can change which symbol a player owns. The abstract makeMove(Board) hook is the only variation point: HumanPlayer reads input; AiPlayer runs minimax.

Adding an AI player in pure OOP terms — no changes to Game needed:

// MinimaxPlayer extends Player and overrides only makeMove()
Player ai = new MinimaxPlayer(Piece.O, /* depth= */ 5);

// Drop into the existing Deque — polymorphism dispatches correctly
Deque<Player> players = new LinkedList<>();
players.add(new HumanPlayer("Alice", Piece.X));
players.add(ai);

// Game loop is identical — current.makeMove(board) works for both

MinimaxPlayer.makeMove(Board board) internally scores all legal moves, builds the minimax tree to the given depth, and returns the optimal Move. The Game class calls current.makeMove(board) — the same single-line dispatch it uses for a human player.

---

📊 Complete Tic-Tac-Toe Class Diagram

classDiagram
    class Game {
        -Board board
        -Deque~Player~ players
        -WinStrategy strategy
        +startGame(Scanner) String
        +checkWinner(Board, int, int, PlayingPiece) boolean
    }
    class Board {
        +int size
        -PlayingPiece[][] grid
        +placePiece(int, int, PlayingPiece) boolean
        +getPiece(int, int) PlayingPiece
        +isFull() boolean
    }
    class Player {
        <>
        +String name
        +PlayingPiece piece
        +makeMove(Board) Move*
    }
    class HumanPlayer {
        +makeMove(Board) Move
    }
    class AiPlayer {
        +makeMove(Board) Move
    }
    class PlayingPiece {
        +PieceType type
    }
    class PieceType {
        <>
        X
        O
        STAR
        HASH
    }
    class WinStrategy {
        <>
        +checkWin(Board, PlayingPiece) boolean
    }
    class MoveValidator {
        <>
        +isValid(Board, int, int) boolean
    }
    class RowColWinStrategy {
        +checkWin(Board, PlayingPiece) boolean
    }
    class DiagonalWinStrategy {
        +checkWin(Board, PlayingPiece) boolean
    }
    Game --> Board : owns
    Game --> Player : manages via Deque
    Game --> WinStrategy : uses (injected)
    Player --> PlayingPiece : has
    PlayingPiece --> PieceType : uses
    HumanPlayer --|> Player : extends
    AiPlayer --|> Player : extends
    RowColWinStrategy ..|> WinStrategy : implements
    DiagonalWinStrategy ..|> WinStrategy : implements
    Game --> MoveValidator : optional

---

🧠 Deep Dive: Why the Deque Is the Right Structure for Turn Management

A fixed two-player array breaks the moment a third player is added. A Deque<Player> implements round-robin rotation with two operations: pollFirst() takes the current player and offerLast() returns them after their turn. This scales to N players without index arithmetic. The same pattern applies to scheduler queues, connection pools, and multiplayer server loops — recognizing it is a transferable skill beyond this problem.

📊 Deque-Based Turn Rotation

sequenceDiagram
    participant G as Game
    participant Q as Deque~Player~
    participant B as Board
    participant W as WinStrategy
    G->>Q: pollFirst() → currentPlayer
    G->>B: placePiece(row, col, piece)
    B-->>G: true (valid move)
    G->>W: checkWin(board, piece)
    W-->>G: false (game continues)
    G->>B: isFull()
    B-->>G: false
    G->>Q: offerLast(currentPlayer)
    Note over Q: Player rejoins queue tail — round-robin continues

---

🎯 Win Detection: O(N) Check Without Scanning the Whole Board

Naively rechecking every cell after each move is wasteful. A smarter pattern: only check the row, column, and (if applicable) diagonals that the most recent move touched.

public boolean checkWinner(Board board, int row, int col, PlayingPiece piece) {
    int N = board.size;
    PieceType t = piece.type;

    // Check row
    boolean rowWin = true;
    for (int c = 0; c < N; c++) {
        PlayingPiece p = board.getPiece(row, c);
        if (p == null || p.type != t) { rowWin = false; break; }
    }
    if (rowWin) return true;

    // Check column
    boolean colWin = true;
    for (int r = 0; r < N; r++) {
        PlayingPiece p = board.getPiece(r, col);
        if (p == null || p.type != t) { colWin = false; break; }
    }
    if (colWin) return true;

    // Check main diagonal (only if on it)
    if (row == col) {
        boolean diagWin = true;
        for (int i = 0; i < N; i++) {
            PlayingPiece p = board.getPiece(i, i);
            if (p == null || p.type != t) { diagWin = false; break; }
        }
        if (diagWin) return true;
    }

    // Check anti-diagonal
    if (row + col == N - 1) {
        boolean antiWin = true;
        for (int i = 0; i < N; i++) {
            PlayingPiece p = board.getPiece(i, N - 1 - i);
            if (p == null || p.type != t) { antiWin = false; break; }
        }
        if (antiWin) return true;
    }

    return false;
}

Complexity: O(N) per move (not O(N²)).

---

📊 Game Turn: Player Move Sequence

sequenceDiagram
    participant G as Game
    participant P as Player
    participant B as Board
    participant W as WinStrategy
    G->>G: pollFirst() — dequeue current player
    G->>P: prompt for row, col
    P-->>G: row=1, col=2
    G->>B: placePiece(1, 2, piece)
    B-->>G: true (cell was empty)
    G->>W: checkWin(board, piece)
    W->>W: scan row, col, diagonals O(N)
    W-->>G: false (no winner yet)
    G->>B: isFull()
    B-->>G: false
    G->>G: offerLast(player) — requeue
    Note over G: next iteration — next player's turn

---

🔄 Game Loop: Turns, Validation, and Termination

class Game {
    private final Board board;
    private final Deque<Player> players;

    Game(int boardSize, List<Player> playerList) {
        this.board   = new Board(boardSize);
        this.players = new LinkedList<>(playerList);
    }

    public String startGame(Scanner scanner) {
        while (true) {
            Player current = players.pollFirst();
            System.out.println(current.name + "'s turn (piece: " + current.piece.type + ")");

            int row, col;
            do {
                System.out.print("Enter row and col: ");
                row = scanner.nextInt();
                col = scanner.nextInt();
            } while (!board.placePiece(row, col, current.piece));

            if (checkWinner(board, row, col, current.piece)) {
                return current.name + " wins!";
            }
            if (board.isFull()) {
                return "Draw!";
            }

            players.offerLast(current);  // send to back of queue
        }
    }
}

---

⚖️ Trade-offs & Failure Modes: Trade-offs and Design Decisions

Strategy Pattern for win conditions:

interface WinningStrategy {
    boolean hasWinner(Board board, int lastRow, int lastCol, PlayingPiece piece);
}

class OrderWinningStrategy implements WinningStrategy {
    // standard row/col/diag check
}

class CustomWinningStrategy implements WinningStrategy {
    // any arbitrary win condition
}

Passing WinningStrategy into Game via constructor injection means adding a new win rule is a new class — zero changes to Game.

---

🧭 Decision Guide: When to Apply This OOP Pattern

---

📊 Game State Flow

The game progresses through a well-defined state machine. Representing this flow makes the Game.startGame() logic easy to reason about and test:

flowchart TD
    Start([Game Created]) --> P[Poll next player from Deque]
    P --> Input[Prompt player for row and col]
    Input --> Valid{Cell valid\nand empty?}
    Valid -->|No| Input
    Valid -->|Yes| Place[Place piece on Board]
    Place --> Win{Check row, col,\ndiagonals for win}
    Win -->|Winner found| W([Announce winner — game over])
    Win -->|No winner| Full{Board full?}
    Full -->|Yes| D([Announce draw — game over])
    Full -->|No| Return[OfferLast current player to Deque]
    Return --> P

The deque is the heart of the turn management. pollFirst() takes the current player; offerLast() puts them back at the end. This works for 2, 3, or N players with no code change.

State transitions summary:

---

🌍 Real-World Applications: Where This Design Pattern Applies

The Tic-Tac-Toe OOP model is a template for any turn-based game or system with pluggable rules:

Turn-based game engines: Chess, Checkers, Go, Connect Four all share the same skeleton — Board, Piece, Player, turn loop, win condition. The WinStrategy interface and Deque<Player> turn manager carry across every one of them with minimal adaptation.

Card games: Replace PlayingPiece with Card, Board with Hand/Deck, and WinningStrategy with scoring logic. The Deque<Player> turn management is identical.

Interview follow-ups you can answer with this design:

• "How would you support undo?" → Add a MoveHistory stack; undo() calls board.removePiece() and returns the player to the front of the deque.
• "How would you add an AI player?" → Create AIPlayer extends Player with a getMove(Board board) method using minimax. No changes to Game.
• "How would you support online multiplayer?" → Serialize Board state to JSON; store in Redis; accept moves over REST or WebSocket; rerun win check on each move.

---

🧪 Hands-On: Implementing and Testing the Design

Step 1 — Wire up a complete 3×3 game:

public static void main(String[] args) {
    List<Player> players = List.of(
        new Player("Alice", new PlayingPiece(PieceType.X)),
        new Player("Bob",   new PlayingPiece(PieceType.O))
    );
    Game game = new Game(3, players);
    String result = game.startGame(new Scanner(System.in));
    System.out.println(result);
}

Step 2 — Write a unit test for the win checker:

@Test
public void testRowWin() {
    Board board = new Board(3);
    PlayingPiece x = new PlayingPiece(PieceType.X);
    board.placePiece(0, 0, x);
    board.placePiece(0, 1, x);
    board.placePiece(0, 2, x);

    WinningStrategy strategy = new OrderWinningStrategy();
    assertTrue(strategy.hasWinner(board, 0, 2, x));
}

@Test
public void testNoWinWithMixedRow() {
    Board board = new Board(3);
    board.placePiece(0, 0, new PlayingPiece(PieceType.X));
    board.placePiece(0, 1, new PlayingPiece(PieceType.O));
    board.placePiece(0, 2, new PlayingPiece(PieceType.X));

    assertFalse(new OrderWinningStrategy().hasWinner(board, 0, 2, new PlayingPiece(PieceType.X)));
}

Step 3 — Test the deque-based turn rotation:

@Test
public void testThreePlayerRotation() {
    Deque<Player> deque = new LinkedList<>(List.of(alice, bob, carol));
    Player first = deque.pollFirst();   // alice
    deque.offerLast(first);
    assertEquals("Bob", deque.peekFirst().name);
    deque.pollFirst(); deque.offerLast(bob);
    assertEquals("Carol", deque.peekFirst().name);
}

---

🎯 What to Learn Next

• Strategy Design Pattern Explained
• Low-Level Design Guide for Ride Booking
• The Ultimate Data Structures Cheat Sheet

---

🛠️ Spring Boot REST: Exposing the Tic-Tac-Toe Game as a Playable API

Spring Boot is an opinionated Java framework for building standalone REST services; its @RestController, @Service, and dependency injection eliminate HTTP boilerplate so the game logic classes (Board, Player, WinningStrategy) stay clean and the controller only handles HTTP concerns.

The OOP model maps directly to REST: POST /games creates a session, POST /games/{id}/move applies a move and returns the outcome, GET /games/{id} returns current board state. Game state is stored per-session in a ConcurrentHashMap — a production deployment would replace this with Redis.

// ─── DTOs ────────────────────────────────────────────────────────────────────
public record CreateGameRequest(int boardSize, List<PlayerRequest> players) {}
public record PlayerRequest(String name, String piece) {}     // piece: "X" | "O" | "STAR"
public record MoveRequest(int row, int col) {}
public record MoveResponse(String gameId, String outcome, String boardSnapshot) {}

// ─── Game session holder ──────────────────────────────────────────────────────
@Data @AllArgsConstructor
public class GameSession {
    private final String gameId;
    private final Game   game;
    private       String result;  // null while in progress
}

// ─── REST controller ─────────────────────────────────────────────────────────
@RestController
@RequestMapping("/api/games")
@RequiredArgsConstructor
public class GameController {

    // In production: inject a GameSessionRepository backed by Redis
    private final ConcurrentHashMap<String, GameSession> sessions = new ConcurrentHashMap<>();

    /** POST /api/games — creates a new game session */
    @PostMapping
    public ResponseEntity<Map<String, String>> createGame(
            @RequestBody CreateGameRequest req) {

        List<Player> players = req.players().stream()
            .map(p -> new Player(p.name(), new PlayingPiece(PieceType.valueOf(p.piece()))))
            .toList();

        String gameId = UUID.randomUUID().toString();
        Game   game   = new Game(req.boardSize(), players);
        sessions.put(gameId, new GameSession(gameId, game, null));

        return ResponseEntity.ok(Map.of("gameId", gameId, "status", "created"));
    }

    /** POST /api/games/{gameId}/move — applies a player's move */
    @PostMapping("/{gameId}/move")
    public ResponseEntity<MoveResponse> makeMove(
            @PathVariable String gameId,
            @RequestBody  MoveRequest  move) {

        GameSession session = sessions.get(gameId);
        if (session == null) return ResponseEntity.notFound().build();

        String outcome = session.getGame().applyMove(move.row(), move.col());
        if (outcome != null) session.setResult(outcome);   // win or draw detected

        return ResponseEntity.ok(new MoveResponse(
            gameId, outcome != null ? outcome : "continue",
            session.getGame().boardSnapshot()  // simple string representation
        ));
    }

    /** GET /api/games/{gameId} — returns current game state */
    @GetMapping("/{gameId}")
    public ResponseEntity<GameSession> getGame(@PathVariable String gameId) {
        return Optional.ofNullable(sessions.get(gameId))
            .map(ResponseEntity::ok)
            .orElse(ResponseEntity.notFound().build());
    }
}

Game.applyMove(row, col) wraps the validation, Board.placePiece(), checkWinner(), and Deque rotation from the earlier sections — the controller only touches HTTP status codes and JSON serialization. Adding a WebSocket endpoint for real-time multiplayer notifications sits on top of the same GameSession state without modifying the game logic.

For a full deep-dive on Spring Boot WebSocket multiplayer game servers and Redis-backed session storage, a dedicated follow-up post is planned.

---

📚 Design Lessons from the Tic-Tac-Toe Problem

Lesson 1: The Deque pattern scales beyond this problem. Round-robin turn management with pollFirst + offerLast works for any number of players or agents. The same pattern applies to scheduler queues, connection pools, and multiplayer server loops. Recognize it — you will use it repeatedly.

Lesson 2: O(N) win detection is a general technique. The "only check the row, column, and diagonal of the last move" pattern applies to any N×N game. Avoid full-board scans whenever you can localize the check to the affected region. This shows interviewers you think about algorithmic efficiency, not just correctness.

Lesson 3: The Strategy Pattern turns extension requests into new files. Without the Strategy Pattern, adding a "four-in-a-row" win rule requires modifying Game. With it, you create FourInARowStrategy implements WinningStrategy — zero changes to existing code. Every interview extension question answered by "I'd add a new Strategy class" is a strong signal to the interviewer.

Lesson 4: Separate state from UI from rules. Board holds state. WinningStrategy holds rules. Game coordinates the loop. Input/output belongs in main or a separate GameRunner. This separation makes every component independently testable — a sign of professional OOP thinking.

---

📌 TLDR: Summary & Key Takeaways

• Four entities drive the design: PlayingPiece, Player, Board, Game.
• Use a Deque<Player> for round-robin turns — scales to any player count.
• Win detection should check only the row, column, and diagonals touched by the last move — O(N), not O(N²).
• The Strategy Pattern makes win conditions swappable at construction time.
• Factory or Builder patterns handle diverse player configurations cleanly.

---

📝 Practice Quiz

1. Why is Deque<Player> a better choice than a two-element array for managing player turns?

   • A) Arrays are slower than deques in Java
   • B) A deque scales to any number of players using poll/offerLast without index arithmetic
   • C) Players must always be sorted alphabetically
   • D) Arrays cannot store objects in Java

   Correct Answer: B — the deque's poll + offerLast idiom implements round-robin rotation for P players with no changes when the player count changes.

2. After placing a piece at (row=2, col=2) on a 3×3 board, what is the minimum check needed to determine a win?

   • A) Scan all 9 cells
   • B) Check only row 2, column 2, and both diagonals (row==col and row+col==N-1)
   • C) Only check the main diagonal
   • D) Check all rows only

   Correct Answer: B — checking only the row, column, and applicable diagonals of the last move is O(N) per move rather than O(N²) for a full board scan.

3. Which SOLID principle does injecting a WinningStrategy into Game support?

   • A) Single Responsibility
   • B) Open/Closed — new strategies extend without modifying Game
   • C) Liskov Substitution
   • D) Interface Segregation

   Correct Answer: B — the Game class is open for extension (new WinningStrategy implementations) and closed for modification (Game code does not change when new strategies are added).

---

🔗 Related Posts

• Strategy Design Pattern Explained
• Low-Level Design Guide for Ride Booking
• The Ultimate Data Structures Cheat Sheet

---