Design Tic-Tac-Toe
A clean two-player game engine — board, moves, win detection, and an extensible rules/strategy seam.
Problem Statement
Design the object model for a generic N×N Tic-Tac-Toe engine. Two players take turns placing their piece type on an empty cell, the game rejects illegal moves, detects wins efficiently, and ends in either a win or a draw.
The design should be reusable beyond the classic 3×3 board. The board size and target line length are configurable, the win rule is pluggable, and the core model stays independent of UI, networking, storage, or bots.
Business context
Tic-Tac-Toe is a favorite beginner LLD interview problem in Amazon, Google, and Adobe style rounds because it looks small but exposes the fundamentals: entity boundaries, turn management, state transitions, validation, and algorithmic win detection. Strong answers avoid scanning the whole board after every move and instead update row, column, and diagonal counters from the last move.
Interviewers use this problem to check whether you can keep the game engine clean while leaving seams for other grid games such as Connect Four, Gomoku, or configurable tournament modes.
Functional Requirements
Create an N×N board where N is at least 3.
Support exactly two players, each with a distinct piece type such as X or O.
Allow only the current player to place a piece on an empty, in-bounds cell.
Reject moves outside the board, moves on occupied cells, and moves after the game is complete.
Detect a win across a row, column, main diagonal, anti-diagonal, or configurable target-length run.
Detect a draw when all cells are filled and no winning move has occurred.
Expose the current player, game state, winner, and board marks for a UI or API layer.
Non-Functional Requirements
Efficient win detection
For the classic target equals board size case, a move updates row, column, and diagonal counters in O(1) instead of rescanning the board.
Correct state transitions
The game must move from IN_PROGRESS to exactly one terminal state, WIN or DRAW, and must never accept another move afterward.
Encapsulation
Board bounds, cell occupancy, player marks, and move ordering are guarded inside domain objects rather than trusted to callers.
Extensibility
Win rules, player creation, and piece creation should be replaceable without rewriting the main game loop.
Thread safety per game
A single game can serialize play calls so two clients cannot place into the same turn concurrently.
Requirement Clarification
QIs the board always 3×3?
No. Model a square board of size N where N is at least 3. The default interview version can use target N, and the implementation also accepts any target from 3 through N.
QHow many players and piece types are required?
Exactly two players in the base design. Each player must have a distinct non-empty mark. X and O are the default piece types.
QShould the engine include a UI, command line loop, or network API?
No. The LLD focus is the in-memory game engine. UI, API, and persistence layers should call the game model through a small adapter.
QDo we need undo or move history?
Not in the base requirements. The current counting strategy is one-way; undo can be added by storing moves and making the strategy support rollback.
QCan the last move both fill the board and win?
Yes. Always check the win condition before declaring a draw, because the final empty cell might complete a line.
UML Class Diagram
Sequence Diagram
Entity Identification
Game
Aggregate root for one match. It owns the board, players, current turn, move count, state, winner, and the injected win strategy.
Board
Owns the square cell matrix, validates coordinates, delegates placement to the correct cell, and exposes mark reads for strategies.
Cell
Stores immutable coordinates and the current mark. It rejects overwrites and rejects the EMPTY mark as a playable piece.
Player
Represents a participant with id, display name, and a non-empty mark. Game uses players only for turn order and marks.
Mark
Piece type enum. X contributes +1, O contributes -1, and EMPTY contributes 0 so counting-based win detection stays compact.
GameState
Explicit lifecycle state for the match: IN_PROGRESS while moves are allowed, WIN after a winner is found, and DRAW when the board fills.
WinningStrategy
Rule interface that decides whether the latest move has ended the game. Game depends on this abstraction rather than a hard-coded algorithm.
CountingWinningStrategy
Default rule implementation. It maintains row, column, and diagonal counters and can also scan from the last move for target lengths smaller than the board.
Design Patterns Used
WinningStrategy isolates the rule for deciding a winning move. Game stays unchanged whether the rule is classic Tic-Tac-Toe, target K in a row, or another grid-game policy.
GameState makes the lifecycle explicit. Game checks IN_PROGRESS before every move and transitions once to WIN or DRAW, preventing illegal moves after completion.
Player and piece creation belong at the setup boundary. A factory method can map request data to validated Player objects and Mark values, while Game receives already-valid participants and never parses input formats.
Step-by-Step Design
1Model piece types with scores
The Mark enum is more than a label. X is +1 and O is -1, which lets the counting strategy detect a full line by checking the absolute counter value.
public enum Mark { X(1), O(-1), EMPTY(0); private final int score; Mark(int score) { this.score = score; } public int score() { return score; } }2Let cells and board guard placement
Board validates coordinates and Cell validates occupancy. The caller cannot overwrite a move or place EMPTY because the invariant is protected at the object that owns the state.
public void place(Mark nextMark) { if (!isEmpty()) { throw new IllegalStateException("Cell is already occupied"); } if (nextMark == Mark.EMPTY) { throw new IllegalArgumentException("Cannot place EMPTY"); } mark = nextMark; }3Make the game loop the single turn boundary
Game.play is synchronized, checks that the match is still active, places the current player's mark, and updates either winner, draw, or next player. Turn rotation never leaks to the UI.
4Put win detection behind a strategy
Game delegates to WinningStrategy after each accepted move. This is the key seam for variants: standard rows and diagonals, target K runs, forbidden moves, or a completely different grid game.
5Use counters for the classic efficient check
CountingWinningStrategy updates only the row, column, and diagonals touched by the latest move. When target equals board size, a win check is constant time.
rows[row] += value; cols[col] += value; if (row == col) diagonal += value; if (row + col == size - 1) antiDiagonal += value; return Math.abs(rows[row]) == target || Math.abs(cols[col]) == target || Math.abs(diagonal) == target || Math.abs(antiDiagonal) == target;6Check win before draw
After placement, increment move count and ask the strategy first. Only when there is no winner and move count equals N×N should the state become DRAW.
7Keep construction outside the game engine
A controller or factory method should create players and marks from request data before Game starts. That keeps parsing, validation messages, bot selection, and alternate pieces out of the core match logic.
Complete Java Implementation
Explanation of Every Class
Mark
Enum for playable and empty piece values. Its score method powers the counter algorithm: X adds +1, O adds -1, and EMPTY is never accepted for a player move.
Cell
Represents one board coordinate. Row and column are immutable, while mark changes from EMPTY to a player mark exactly once through the validated place method.
Board
Owns the N×N Cell matrix. It enforces the minimum size, validates coordinates, delegates placement to Cell, exposes markAt for strategies, and offers isInside for directional scans.
Player
Immutable player value object with id, name, and mark. The constructor rejects EMPTY and null fields so Game can assume both participants are valid.
GameState
Small enum that models the match lifecycle. IN_PROGRESS allows moves; WIN and DRAW are terminal states enforced by Game.play.
WinningStrategy
Interface for rule evaluation. It receives the board, latest row and column, and latest mark, allowing Game to delegate win detection without knowing the algorithm.
CountingWinningStrategy
Stateful strategy bound to one game. It stores row and column arrays plus diagonal counters. For target equal to board size it checks counters in O(1); for smaller targets it scans four lines from the last move.
Game
Coordinates the match. Its synchronized play method rejects completed games, places the current mark, increments move count, asks the strategy for a win, sets WIN or DRAW, otherwise rotates to the next player.
Dry Run
Sample input
3×3 board with target 3. Player A uses X and Player B uses O. Moves: A at (0,0), B at (0,1), A at (1,1), B at (0,2), A at (2,2).
| Step | Current player | Move | Counter impact | Result |
|---|---|---|---|---|
| 1 | A with X | (0,0) | row 0 +1, col 0 +1, diagonal +1 | IN_PROGRESS; next B |
| 2 | B with O | (0,1) | row 0 -1, col 1 -1 | IN_PROGRESS; next A |
| 3 | A with X | (1,1) | row 1 +1, col 1 +1, diagonal +1 | IN_PROGRESS; next B |
| 4 | B with O | (0,2) | row 0 -1, col 2 -1, anti-diagonal -1 | IN_PROGRESS; next A |
| 5 | A with X | (2,2) | row 2 +1, col 2 +1, diagonal +1 | WIN; winner A |
The diagonal counter reaches +3 on step 5, so the strategy returns true. Game sets the winner before checking whether the board is full.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| Create board | O(N^2) | O(N^2) | The board materializes every Cell in the N×N grid. |
| play with target equal to N | O(1) | O(1) | Placement, counter updates, state transition, and turn rotation are constant-time after board setup. |
| play with target less than N | O(N) | O(1) | The strategy scans up to four lines from the latest move to find a target-length run. |
| Strategy storage | O(1) | O(N) | Rows and columns require two arrays of length N plus two diagonal counters. |
The board itself is O(N^2). The important interview optimization is avoiding an O(N^2) scan after every move; the latest move contains enough information to check only affected lines.
Extensibility
Alternate win rules
Implement a new WinningStrategy for Gomoku, misere rules, blocked cells, or tournament-specific winning conditions.
Different player types
Create human, bot, or remote players through a factory at setup time while keeping Game dependent only on Player and Mark.
Move history and undo
Add a Move value object and an undo-aware strategy that can subtract the same counter values it added during play.
Other grid games
Reuse Board, Cell, turn state, and strategy seams for games like Connect Four by changing placement rules and win strategy.
Persistence and replay
Store accepted moves as an append-only log so games can be resumed, audited, or replayed without exposing mutable board internals.
Alternative Designs
Full-board scan after every move
After each placement, inspect every row, column, and diagonal to decide whether someone won.
Tradeoffs
Simpler to explain for 3×3, but it does unnecessary work and does not scale cleanly to larger boards.
Immutable board snapshots
Represent each move as a new Board instance and keep the previous boards for undo, replay, or concurrent reads.
Tradeoffs
Great for history and debugging, but creates more objects and requires careful sharing to avoid O(N^2) copying per move.
External rule engine
Move all state transitions and win rules into a GameRules service while Game stores only the current state.
Tradeoffs
Useful for a large multi-game platform, but over-engineered for a single interview problem and can make ownership blurry.
Bitboard representation
Store each player's occupied cells as bits and use bit operations to test wins.
Tradeoffs
Very fast for fixed small boards, but harder to read, harder to generalize to arbitrary N, and less suitable for beginner LLD.
Common Mistakes
- ×
Scanning the whole board after every move instead of checking only affected row, column, and diagonals.
- ×
Letting the UI decide whose turn it is, which splits game authority across layers.
- ×
Checking draw before win and missing a final-move victory.
- ×
Allowing a player to use EMPTY or allowing both players to share the same mark.
- ×
Forgetting anti-diagonal detection where row plus column equals N minus 1.
- ×
Allowing moves after WIN or DRAW because the state guard is missing.
- ×
Sharing one stateful CountingWinningStrategy across multiple games, causing counters to leak between matches.
Follow-up Interview Questions
QHow would you support Connect Four?
Keep the turn and state model, replace placement with gravity-based column placement, and inject a strategy that checks vertical, horizontal, and diagonal runs from the dropped piece.
QHow would you add undo?
Store a stack of Move objects. Undo must clear the board cell, decrement move count, restore state to IN_PROGRESS, and roll back the strategy counters or rebuild them from history.
QCan the same strategy support target 4 on a 10×10 board?
Yes. Counters alone work when target equals board size. For smaller targets, scan outward from the latest move in four directions and count a continuous run.
QWhat happens if two clients submit moves at the same time?
The game should serialize play calls with a per-game lock. The reference Game.play method is synchronized, so only one move can update the board and turn state at a time.
QHow would you run many games at once?
Create one Game instance per match and store them in a repository keyed by game id. Do not share mutable Board or CountingWinningStrategy instances across games.
Production Considerations
Persistence
Persist game metadata and accepted moves, not just the final board. A move log enables replay, recovery, auditing, and dispute resolution.
API concurrency
Use per-game locking or optimistic version checks so duplicate requests and racing clients cannot skip turns or place two marks at once.
Validation and abuse handling
Return clear errors for invalid turns, occupied cells, out-of-range coordinates, and completed games. Rate-limit automated clients in multiplayer settings.
Observability
Track active games, invalid move rate, average game length, draw rate, and strategy errors so production issues are visible.
Bot and matchmaking boundaries
Keep AI and matchmaking outside Game. They choose a legal move, then submit it through the same play method as a human player.
What Interviewers Look For
Did you make Game the single authority for turns and terminal states?
Did you check win before draw on the final move?
Did you use row, column, and diagonal counters instead of scanning the whole board?
Did you put win detection behind a Strategy interface so variants are additive?
Did you call out the stateful nature of CountingWinningStrategy and keep one instance per game?
Did you keep player and piece creation at the setup boundary rather than inside the move loop?
Quiz
0/5 answered
1.Why does Mark assign X a score of +1 and O a score of -1?
2.Why should Game check for a win before checking for a draw?
3.What is the main benefit of WinningStrategy?
4.Which state transition is valid after a non-winning move that does not fill the board?
5.Which data structure makes classic N-in-a-row checking efficient?
Practice Variants
Add undo and replay
IntermediateIntroduce a Move class, store move history, and make the board plus winning strategy support rollback.
Add a bot player
IntermediateCreate players through a factory and allow one player to choose moves through a BotStrategy while Game still validates every move.
Design Connect Four
AdvancedReuse the turn and state model, but change placement to drop into a column and update the winning strategy for runs of four.
Support best-of-three matches
BeginnerAdd a Match aggregate that creates Games, tracks round winners, and declares an overall winner without bloating the Game class.
Flashcards
Cheat Sheet
Entities: Game, Board, Cell, Player, Mark, GameState, WinningStrategy, CountingWinningStrategy.
Flow: client calls play → Game verifies active state → Board places current mark → strategy checks latest move → Game sets WIN, DRAW, or rotates turn.
Win check: for target N, update row, column, main diagonal, and anti-diagonal counters. A counter absolute value equal to N means the latest player won.
State: IN_PROGRESS allows moves; WIN and DRAW are terminal. Always check win before draw.
Patterns: Strategy for win rules, State for lifecycle, Factory Method at setup for player and piece creation.
Complexity: board setup O(N^2), classic play O(1), target less than N play O(N), strategy storage O(N).
Pitfalls: shared strategy instances, UI-managed turns, missing anti-diagonal, accepting EMPTY, moves after terminal state.
References
- BookHead First Design Patterns — Freeman & Robson
- BookEffective Java — Item 34, Use enums instead of int constants — Joshua Bloch
- DocsRefactoring Guru — Strategy Pattern
- DocsRefactoring Guru — State Pattern