LLD-005 · DESIGN PRACTICE

Tic-Tac-Toe Engine

Build a small complete engine, then defend configurable rules, atomic moves and historical replay.

Local Java 21 reference verified: 10975 checks. Learner drafts are not executed. Author self-review; independent review pending.

Existing introductory lesson · Version 1

Understand the problem

Design a two-player board-game engine with N×N cells and K consecutive marks needed to win. Implement legal turns, occupied-cell validation, terminal outcomes and deterministic replay. Show how the same simple model can expose Senior-level concurrency and Staff-level compatibility decisions without inventing an unnecessary game framework.

Before you start

• Encapsulation and immutable snapshots
• Matrix indexing and directional scans
• Optimistic version checks
• Command logs and deterministic replay

Scope and explicit decisions

• Two fixed marks X/O; X always starts and turns alternate. Board size N is 1..100 and target K is 1..N. Four undirected win axes: horizontal, vertical and both diagonals.
• A win requires at least K consecutive matching marks. Marks elsewhere in the same row do not count toward a disconnected run. A full board without a win is a draw.
• Each call supplies player, row, column and expectedVersion equal to accepted move count. Wrong player, stale version, out-of-bounds, occupied cell or terminal game rejects without mutation.
• Duplicate move requests are rejected via stale expectedVersion, not automatically answered from a deduplication ledger. A caller recovering from timeout must read snapshot/history; the API does not promise idempotent success responses.
• Snapshot returns immutable row strings, status, next mark, version and rule version. next indicates the next scheduled mark; it is actionable only while status=PLAYING.
• History contains accepted commands only. Replay validates every command through the same play method and requires an exact declared rule-version match. A version label is not a full rule registry: production must ensure a label maps to immutable rule semantics.
• No minimax/AI, networking, matchmaking, ranking, undo, draw-by-agreement or persistence is implemented. Authorization that a caller controls X/O is an adapter responsibility, not proved by passing an enum.
• The engine owns one board under one monitor. Independent games can be separate instances. Board snapshots allocate O(N²) data, so even a fast win detector does not make the public play operation O(K).

Worked examples

Try before revealing

Requirements and invariants

R1 — Only the expected player and current version can claim an empty cell. play protects I1.

R2 — Derive win/draw after the accepted move and reject all later moves. wins protects I2.

R3 — External snapshots and histories cannot mutate the authoritative board. snapshot protects I3.

R4 — Replay retains the declared rule identity and validates every transition. replay protects I4.

I1: Accepted move count equals occupied cell count; turns alternate from X and each accepted move advances version exactly once.

I2: Terminal status is stable. PLAYING has no winning run and at least one free cell; win is tested before draw after a move.

I3: Only Game.play mutates board/history; returned snapshots and history lists are immutable copies.

I4: Replaying accepted commands under the same immutable rules produces the same board, status and version.

Derive the design

Scan the whole board first, then exploit the last move

A correct baseline scans every potential K-length line after each move and declares a win if any line is complete. For N×N and four axes a straightforward implementation can inspect O(N²K) cells. The key improvement is that before a legal move there was no winner; therefore any new winning run must pass through the cell just placed. Inspect four axes around that cell rather than rescan unrelated lines.

Alternative: For classic K=N games, row/column/diagonal counters can detect completed lines in O(1), but they do not encode consecutive runs when K<N. The reference uses the more general last-move scan. The test oracle independently scans all rows/columns/diagonals for classic 3×3, avoiding reuse of the production detector.

Responsibilities and ownership

Method contracts

What, when, why and how

Each concept is attached to the requirement it protects, its implementation, an alternative and a test.

Read and run the Java reference

1import java.util.*;
2/** Deterministic N by N, K-in-a-row engine; no network or AI. */
3public final class Solution {
4    private Solution() {}
5    public enum Mark { X, O }
6    public enum Status { PLAYING, X_WON, O_WON, DRAW }
7    public record Rules(String version,int size,int target){public Rules{if(version==null||version.isBlank()||size<1||size>100||target<1||target>size)throw new IllegalArgumentException("rules");}}
8    public record Move(Mark player,int row,int column,int expectedVersion){}
9    public record Snapshot(List<String> rows,Mark next,Status status,int version,String ruleVersion){public Snapshot{rows=List.copyOf(rows);}}
10    public static final class Game {
11        private final Rules rules;
12        private final char[][] board;
13        private final List<Move> history=new ArrayList<>();
14        private Mark next=Mark.X;
15        private Status status=Status.PLAYING;
16        public Game(Rules rules){this.rules=Objects.requireNonNull(rules);board=new char[rules.size()][rules.size()];for(char[] row:board)Arrays.fill(row,'.');}
17        public synchronized Snapshot play(Mark player,int row,int column,int expectedVersion){
18            Objects.requireNonNull(player);
19            if(expectedVersion!=history.size())throw new IllegalStateException("stale version");
20            if(status!=Status.PLAYING||player!=next)throw new IllegalStateException("terminal or wrong turn");
21            if(row<0||row>=rules.size()||column<0||column>=rules.size())throw new IllegalArgumentException("bounds");
22            if(board[row][column]!='.')throw new IllegalStateException("occupied");
23            char token=player.name().charAt(0);board[row][column]=token;history.add(new Move(player,row,column,expectedVersion));
24            if(wins(row,column,token))status=player==Mark.X?Status.X_WON:Status.O_WON;
25            else if(history.size()==rules.size()*rules.size())status=Status.DRAW;
26            next=next==Mark.X?Mark.O:Mark.X;return snapshot();
27        }
28        private boolean wins(int row,int col,char token){
29            int[][] axes={{1,0},{0,1},{1,1},{1,-1}};
30            for(int[] axis:axes)if(1+count(row,col,axis[0],axis[1],token)+count(row,col,-axis[0],-axis[1],token)>=rules.target())return true;
31            return false;
32        }
33        private int count(int row,int col,int dr,int dc,char token){
34            int found=0;
35            for(int step=1;step<rules.target();step++){
36                int r=row+dr*step,c=col+dc*step;
37                if(r<0||c<0||r>=rules.size()||c>=rules.size()||board[r][c]!=token)break;found++;
38            }
39            return found;
40        }
41        public synchronized Snapshot snapshot(){var rows=new ArrayList<String>();for(char[] row:board)rows.add(new String(row));return new Snapshot(rows,next,status,history.size(),rules.version());}
42        public synchronized List<Move> history(){return List.copyOf(history);}
43        public static Game replay(Rules rules,String recordedRuleVersion,List<Move> moves){
44            if(!rules.version().equals(recordedRuleVersion))throw new IllegalArgumentException("rule version mismatch");
45            var game=new Game(rules);for(var m:List.copyOf(moves))game.play(m.player(),m.row(),m.column(),m.expectedVersion());return game;
46        }
47    }
48}
49

Complexity and limits

• Win detection scans at most four pairs of K-1 rays: O(K) time and O(1) extra detection space.
• play returns a full snapshot, so total time and returned space are O(N²+K), normally O(N²) because K<=N. Accepted history append is amortized O(1).
• Game storage is O(N²+M), with M<=N² accepted moves. history() copies O(M) records by reference; records themselves are immutable.
• Replay of M accepted moves currently calls play M times and therefore costs O(M×N²+M×K), with transient snapshots. An internal validated delta path could avoid this cost but needs equivalence tests.
• The exhaustive test traverses 5,478 reachable classic board states and compares an independent evaluator. It validates classic rules extensively; it is not an exhaustive proof for all N<=100/K variants.

Walk through the actual reference

These walkthrough fixtures are emitted only after the Java harness verifies their operations and expected state. Concurrency tests additionally exercise competing callers.

Mistakes and counterexamples

Engineer → Senior → Staff

Return to the lesson →

Provenance and scope of evidence

Original teaching material. The local contract is implemented by Solution.java and tested by Test.java on Java 21. Distributed persistence, real provider/device adapters and deployment are not claimed.

Reference verification is not independent editorial review, production deployment verification or a claim that distributed adapters are implemented.