12. Tic-Tac-Toe / Board Game Engine Beginner → Intermediate (Pattern Showcase)

Jump to section:

A. Realistic Interview Prompt

"Design a Tic-Tac-Toe game for two players. Then generalize it: support an arbitrary board size and an arbitrary number of symbols in a row to win, and support both human and computer-controlled players."

B. Difficulty

Beginner → Intermediate. Trivial if hardcoded to a 3×3 board with 8 fixed win-lines; the entire value of this problem, as an interview signal, is in the generalization the interviewer almost always asks for next.

C. What This Problem Tests

Whether the win-check is a generic algorithm over rows/columns/diagonals of any size, or 8 hardcoded coordinate triples
Cleanly polymorphic players (human vs. AI) via Strategy, rather than an isAI boolean with branching move logic
Recognizing the turn-based game loop itself as a reusable skeleton (Template Method) across an entire family of board games, not something specific to Tic-Tac-Toe
Resisting over-engineering — this problem rewards clean simplicity, not pattern-stacking for its own sake

D. Requirements

Functional

Support an N×N board (default 3×3)
Support K-in-a-row win condition (default 3), checked across rows, columns, and both diagonal directions
Support 2+ players, each assigned a distinct symbol
Support both human players (external move input) and computer players (internally decided moves)
Detect a win, a draw (board full, no winner), and reject illegal moves (occupied cell, out-of-turn, out-of-bounds)

Non-Functional

Adding a new board size or win-length must require zero changes to the win-checking algorithm's code, only its parameters
Adding a new AI difficulty must not require changes to the game loop or board

E. Clarifying Questions

#	Question	Why It Matters	Design Decision Affected
1	Fixed 3×3, or should the board size and win-length be generalized?	Determines whether a generic line-scan win checker is required from the start or can be added later	Design of `WinningStrategy`
2	Should the engine support other turn-based grid games (Connect Four, Gomoku) later?	Determines whether the game loop should be a reusable Template Method now	Scope of `TurnBasedGame` base class
3	Does the computer player need real strategy (minimax) or just legal random moves?	Affects how much of the AI Strategy hierarchy is worth building out	Depth of `MoveStrategy` implementations
4	More than 2 players?	Some generalized variants support 3+ symbols on a larger board	Whether `Player` collection is fixed-size or a list

F. Assumptions

Confirmed: N×N board, K-in-a-row win, human and computer players, turn-based.
Assumption: default 2 players unless asked for more — the design supports a list of players either way, so this is a configuration detail, not a structural one.
Assumption: "computer player" means at least a legal-random-move strategy; a full minimax/alpha-beta implementation is discussed as a swappable MoveStrategy but not required to be exhaustive.

G. Actors

Actor	Responsibility
Player (human or AI)	Produces a move each turn
GameController (facade)	Runs the game loop, enforces turn order and legality

H. Core Domain Entities

Class	Responsibility	Key Attributes	Key Methods	Does NOT Handle
`Board`	Owns the grid and cell occupancy	N×N grid of `Symbol`	`placeMark(row, col, symbol)`, `isFull()`, `isValidMove()`	Deciding whether a placement wins — that's `WinningStrategy`'s job
`Symbol` (value)	A player's mark (X, O, or generalized)	—	—	—
`Player` (abstract)	Common identity for anything that produces a move	id, symbol	`getMove(board)`	How the move is decided — delegated to subclass/strategy
`HumanPlayer`	Returns externally-supplied input as the move	—	`getMove(board)`	Any move computation
`AIPlayer`	Delegates move selection to a `MoveStrategy`	MoveStrategy	`getMove(board)`	The algorithm itself
`MoveStrategy` (interface)	One algorithm for choosing the AI's next move	—	`decideMove(board, symbol)`	—
`WinningStrategy` (interface)	Generic K-in-a-row check over the current board	—	`checkWinner(board, lastMove)`	Anything about turn order
`TurnBasedGame` (abstract, Template Method)	The shared skeleton of any turn-based grid game	board, players, winningStrategy	`play()` (template), hooks: `setupBoard()`, `declareResult()`	Game-specific win rules — a hook, not hardcoded
`GameController` (facade)	Public API to start/query a game	TurnBasedGame instance	`startGame()`, `makeMove()`	—

I. Class Relationships

Strategy for both AI move selection and win-checking: both are algorithms an interviewer expects generalized or swapped — "make the AI harder" is a new MoveStrategy; "support Connect Four's 4-in-a-row on a taller board" is a parameterized WinningStrategy, not new code.
Why win-checking must not be 8 hardcoded coordinate triples: the single most common naive shape for this exact problem is a literal list of the 3×3 board's 8 winning lines. It works for the demo and breaks the instant the board size changes. A generic WinningStrategy scans every row, column, and both diagonal directions through the just-played cell, checking for K consecutive matching symbols — this is the direct generalization interviewers are testing for.
Why Template Method for the game loop: "initialize board → loop (get move → validate → place → check win/draw → switch turn) → declare result" is the same skeleton for Tic-Tac-Toe, Connect Four, and Gomoku — only setupBoard() (board dimensions) and the winning strategy actually differ. This is the genuine case for Template Method that Coffee Vending Machine's brewing steps (Problem 8) explicitly were not — there, "the recipe" was just varying data over one fixed algorithm; here, subclasses truly do plug in different structural pieces (board shape, win rule) into a shared control flow.
Player as abstract base, not a boolean flag: HumanPlayer vs. AIPlayer as real polymorphic types (rather than one Player class with an isAI flag and an if in getMove()) is what lets a new player type (e.g. a remote/networked player) slot in with zero changes to TurnBasedGame.

J. Class Diagram

View Mermaid source

classDiagram
  class TurnBasedGame {
    board
    players
    winningStrategy
    +play()
    +setupBoard()
  }
  class Board {
    grid
    +placeMark()
    +isValidMove()
    +isFull()
  }
  class WinningStrategy {
    <<interface>>
    +checkWinner(board, lastMove)
  }
  class Player {
    <<abstract>>
    id
    symbol
    +getMove(board)
  }
  class AIPlayer {
    moveStrategy
    +getMove(board)
  }
  class MoveStrategy {
    <<interface>>
    +decideMove(board, symbol)
  }
  TurnBasedGame --> Board
  TurnBasedGame --> WinningStrategy
  Player <|-- HumanPlayer
  Player <|-- AIPlayer
  AIPlayer --> MoveStrategy
  TurnBasedGame --> "*" Player

K. Responsibility Mapping

Class	Responsibility	Does NOT Handle
Board	Grid state, cell validity	Win detection, turn order
WinningStrategy implementations	K-in-a-row detection for any board size	Placing marks, turn order
Player implementations	Producing one move given the current board	Validating or applying that move
TurnBasedGame	Loop skeleton: turn order, validation, win/draw checks	Board-specific win rules (hook, not hardcoded)

L. SOLID Analysis

Principle	How It's Applied	Naive Violation
SRP	`Board` owns grid state; `WinningStrategy` owns win logic; `Player` owns move production	One `Game` class owning the grid, the win-check, and the turn loop inline
OCP	A new AI difficulty is a new `MoveStrategy`; a new board game reusing the loop is a new `TurnBasedGame` subclass	Branching on a difficulty enum inside one giant `getAIMove()` method
LSP	`HumanPlayer` and `AIPlayer` both honestly return a legal move from `getMove()`; callers never care which	An `AIPlayer.getMove()` that occasionally blocks waiting for console input it doesn't actually have
ISP	`MoveStrategy` and `WinningStrategy` stay single-method interfaces	A combined "GameRules" interface mixing win-checking with move validation and scoring
DIP	`TurnBasedGame` depends on the `WinningStrategy` abstraction, not a concrete 3×3 checker	`TurnBasedGame.checkWin()` hardcoding 8 coordinate triples inline

M. Design Patterns

Pattern	Problem It Solves	Where It Appears	When NOT to Use
Strategy	AI move selection and win-checking are both algorithms expected to vary/generalize	`MoveStrategy`, `WinningStrategy`	Skip `MoveStrategy` variety if the round only ever needs "legal random move"
Template Method	The turn-based loop skeleton is identical across a family of grid games; only specific steps differ	`TurnBasedGame.play()`	Skip entirely if only one single game will ever exist — then a plain loop in `GameController` is simpler and this is a real case where Template Method is not needed (contrast with the reasoning in I)

Explicitly avoided: hardcoded win-line enumeration — the most common shortcut for exactly this problem, and precisely what a generic line-scan WinningStrategy replaces.

N. What Is Likely to Change?

Behavior	Current Design	Anticipated Change	Protecting Abstraction
Board size / win length	3×3, 3-in-a-row	Any N×N, any K-in-a-row (Gomoku-style)	`WinningStrategy` parameterized by K, scans generically
AI difficulty	Random legal move	Minimax/alpha-beta lookahead	New `MoveStrategy` implementation, zero change to `AIPlayer`
Game family	Tic-Tac-Toe only	Connect Four (gravity-constrained drops), Gomoku	New `TurnBasedGame` subclass reusing the same loop

O. Design Evolution

V1: 3×3 board, 8 hardcoded win-line checks, two hardcoded players.
V2: replace hardcoded lines with a generic line-scan WinningStrategy the moment board size is generalized — the central lesson of this problem.
V3: extract Player as an abstract base once a computer opponent is requested, avoiding an isAI flag.
V4: extract MoveStrategy once a second AI difficulty is requested.
V5: extract TurnBasedGame as a Template Method only if a second game (Connect Four) is actually requested — not preemptively.

What stays stable: Board's cell-level API. Generalizing size/win-length/game-family are all additive changes behind existing interfaces.

P. API / Interface Design

interface WinningStrategy {
  boolean checkWinner(Board board, Move lastMove);
}

interface MoveStrategy {
  Move decideMove(Board board, Symbol symbol);
}

abstract class TurnBasedGame {
  void play();                       // template method
  protected abstract void setupBoard();
}

class GameController {
  void startGame();
  MoveResult makeMove(String playerId, int row, int col);
}

interface WinningStrategy {
  boolean checkWinner(Board board, Move lastMove);
}

interface MoveStrategy {
  Move decideMove(Board board, Symbol symbol);
}

abstract class TurnBasedGame {
  void play();                       // template method
  protected abstract void setupBoard();
}

class GameController {
  void startGame();
  MoveResult makeMove(String playerId, int row, int col);
}

class WinningStrategy {
public:
  virtual bool checkWinner(const Board& board, const Move& lastMove) = 0;
};

class MoveStrategy {
public:
  virtual Move decideMove(const Board& board, Symbol symbol) = 0;
};

class TurnBasedGame {
public:
  void play();                       // template method
protected:
  virtual void setupBoard() = 0;
};

class GameController {
public:
  void startGame();
  MoveResult makeMove(const std::string& playerId, int row, int col);
};

class WinningStrategy {
  checkWinner(board, lastMove) { throw new Error('not implemented'); }
}

class MoveStrategy {
  decideMove(board, symbol) { throw new Error('not implemented'); }
}

class TurnBasedGame {
  play() {}                       // template method
  setupBoard() { throw new Error('not implemented'); }
}

class GameController {
  startGame() {}
  makeMove(playerId, row, col) {}
}

interface WinningStrategy {
  checkWinner(board: Board, lastMove: Move): boolean;
}

interface MoveStrategy {
  decideMove(board: Board, symbol: Symbol): Move;
}

abstract class TurnBasedGame {
  play(): void {}                       // template method
  protected abstract setupBoard(): void;
}

class GameController {
  startGame(): void {}
  makeMove(playerId: string, row: number, col: number): MoveResult {}
}

Ownership/validation notes: Board.isValidMove() checks bounds and occupancy before placeMark() ever mutates state; WinningStrategy.checkWinner() is only ever invoked against the cell that was just played, not the whole board, keeping each check O(K) instead of rescanning everything.

Q. Pseudocode — Critical Logic

LineScanWinningStrategy.checkWinner(board, lastMove):
  symbol = board.get(lastMove.row, lastMove.col)
  for each direction in [horizontal, vertical, diagonal, anti-diagonal]:
    count = 1
    count += countMatching(board, lastMove, direction, symbol)
    count += countMatching(board, lastMove, oppositeOf(direction), symbol)
    if count >= K: return true
  return false

TurnBasedGame.play():
  setupBoard()
  while true:
    player = nextPlayer()
    move = player.getMove(board)
    if not board.isValidMove(move): continue   // human retries; AI never produces one
    board.placeMark(move, player.symbol)
    if winningStrategy.checkWinner(board, move): declareResult(WINNER, player); return
    if board.isFull(): declareResult(DRAW); return

boolean checkWinner(Board board, Move lastMove) {
  Symbol symbol = board.get(lastMove.getRow(), lastMove.getCol());
  for (Direction direction : new Direction[]{HORIZONTAL, VERTICAL, DIAGONAL, ANTI_DIAGONAL}) {
    int count = 1;
    count += countMatching(board, lastMove, direction, symbol);
    count += countMatching(board, lastMove, oppositeOf(direction), symbol);
    if (count >= K) return true;
  }
  return false;
}

void play() {
  setupBoard();
  while (true) {
    Player player = nextPlayer();
    Move move = player.getMove(board);
    if (!board.isValidMove(move)) continue;   // human retries; AI never produces one
    board.placeMark(move, player.getSymbol());
    if (winningStrategy.checkWinner(board, move)) { declareResult(Result.WINNER, player); return; }
    if (board.isFull()) { declareResult(Result.DRAW); return; }
  }
}

bool LineScanWinningStrategy::checkWinner(const Board& board, const Move& lastMove) {
  Symbol symbol = board.get(lastMove.row, lastMove.col);
  for (auto direction : {HORIZONTAL, VERTICAL, DIAGONAL, ANTI_DIAGONAL}) {
    int count = 1;
    count += countMatching(board, lastMove, direction, symbol);
    count += countMatching(board, lastMove, oppositeOf(direction), symbol);
    if (count >= K) return true;
  }
  return false;
}

void TurnBasedGame::play() {
  setupBoard();
  while (true) {
    auto player = nextPlayer();
    Move move = player->getMove(board);
    if (!board.isValidMove(move)) continue;   // human retries; AI never produces one
    board.placeMark(move, player->symbol);
    if (winningStrategy->checkWinner(board, move)) { declareResult(Result::WINNER, player); return; }
    if (board.isFull()) { declareResult(Result::DRAW); return; }
  }
}

checkWinner(board, lastMove) {
  const symbol = board.get(lastMove.row, lastMove.col);
  for (const direction of [HORIZONTAL, VERTICAL, DIAGONAL, ANTI_DIAGONAL]) {
    let count = 1;
    count += countMatching(board, lastMove, direction, symbol);
    count += countMatching(board, lastMove, oppositeOf(direction), symbol);
    if (count >= K) return true;
  }
  return false;
}

play() {
  this.setupBoard();
  while (true) {
    const player = this.nextPlayer();
    const move = player.getMove(this.board);
    if (!this.board.isValidMove(move)) continue;   // human retries; AI never produces one
    this.board.placeMark(move, player.symbol);
    if (this.winningStrategy.checkWinner(this.board, move)) { this.declareResult(Result.WINNER, player); return; }
    if (this.board.isFull()) { this.declareResult(Result.DRAW); return; }
  }
}

checkWinner(board: Board, lastMove: Move): boolean {
  const symbol = board.get(lastMove.row, lastMove.col);
  for (const direction of [HORIZONTAL, VERTICAL, DIAGONAL, ANTI_DIAGONAL]) {
    let count = 1;
    count += countMatching(board, lastMove, direction, symbol);
    count += countMatching(board, lastMove, oppositeOf(direction), symbol);
    if (count >= K) return true;
  }
  return false;
}

play(): void {
  this.setupBoard();
  while (true) {
    const player = this.nextPlayer();
    const move = player.getMove(this.board);
    if (!this.board.isValidMove(move)) continue;   // human retries; AI never produces one
    this.board.placeMark(move, player.symbol);
    if (this.winningStrategy.checkWinner(this.board, move)) { this.declareResult(Result.WINNER, player); return; }
    if (this.board.isFull()) { this.declareResult(Result.DRAW); return; }
  }
}

R. End-to-End Use Case

startGame() — 3×3 board, K=3, Player X (human), Player O (AI, RandomMoveStrategy)
  │
  ▼
makeMove(X, 0, 0) → valid → board updated → checkWinner (count=1) → no win → switch turn
  │
  ▼
AIPlayer.getMove() → RandomMoveStrategy picks (1,1) → board updated → checkWinner → no win
  │
  ▼
... turns continue until X completes a diagonal ...
  ▼
checkWinner(board, lastMove) scans diagonal through last move → count=3 → declareResult(WINNER, X)

S. Data Structures

Structure	Used For	Why	Alternative & Trade-off
2D array/grid of `Symbol`	Board storage	O(1) cell access by (row, col)	A sparse map works too but adds overhead with no benefit on a dense, small grid
Direction-vector scan around `lastMove`	Win-checking	Only checks the K-neighborhood of the just-played cell instead of rescanning the whole board every turn	Rescanning the entire board each move is simpler to write but wastefully re-derives information the previous checks already had

T. Complexity Analysis

Operation	Time	Space
`placeMark()` / `isValidMove()`	O(1)	O(1)
`checkWinner()` (incremental, around last move)	O(K) per direction, O(1) directions	O(1)
Random AI move	O(N²) worst case scanning for an empty cell	O(1)

U. Testing Strategy

Happy path: a completed row/column/diagonal of length K is detected as a win regardless of board size.
Edge cases: a full board with no K-in-a-row is a draw, not silently unresolved; an out-of-turn or occupied-cell move is rejected without mutating the board.
Generalization tests: the same WinningStrategy correctly handles a 5×5 board with K=4 without any code change — only the constructor parameter changes.
Polymorphism tests: swapping an AIPlayer's MoveStrategy at runtime changes its behavior without touching TurnBasedGame.

V. Interviewer Follow-Ups

Follow-Up	Testing	Design Change	Classes Changed	Pattern/Trade-off
"Generalize to any board size and win length."	Whether win-checking was ever hardcoded	None if `WinningStrategy` was already generic — just new constructor parameters	None (validates M)	The single most common follow-up for this exact problem
"Add a smarter AI."	Whether AI logic was isolated behind a Strategy	New `MinimaxMoveStrategy`	New class only	Validates the `MoveStrategy` boundary
"Now build Connect Four, reusing what you can."	Whether the game loop was genuinely reusable	New `ConnectFourGame extends TurnBasedGame` with a gravity-constrained `Board` variant	New subclass + board variant	Validates the Template Method boundary drawn in M — or reveals it was premature if a lot has to change anyway

W. Concurrency

This problem is turn-based and single-threaded by nature — only one player acts at a time, and there is no shared-resource race analogous to the ones in Parking Lot or Elevator. The one legitimate concern is a networked/remote human player submitting a move for a turn that is no longer theirs (a stale-turn check), which is a validation concern in TurnBasedGame.play(), not a locking concern.

X. Persistence

Not required for a live single-session game. If game history/replays are requested, each move is naturally an append-only log entry (player, cell, timestamp) — a simple repository behind the existing API, no change to Board or TurnBasedGame.

Y. Scaling Boundary

Layer	What Belongs Here
LLD	Board/win-check/player/game-loop class design and generalization
HLD	Matchmaking, real-time multiplayer sync across clients, leaderboards
Explicitly out of scope	Networked multiplayer infrastructure unless the round pivots there

Z. Failure Scenarios

A human player's move arrives out of turn (e.g. a delayed network message): rejected by the turn-order check in TurnBasedGame before it ever reaches Board.
An AI's MoveStrategy returns an already-occupied cell (a bug in that strategy): Board.isValidMove() still rejects it — validation is never skipped just because the mover is a computer.

AA. Common Bad Designs

8 hardcoded 3×3 win-line coordinate triples — the single most common shortcut for this problem, and the first thing a "generalize the board size" follow-up breaks.
One Player class with an isAI boolean and a branch in getMove() instead of real polymorphism.
Building a full TurnBasedGame Template Method hierarchy for a round that only ever asks for Tic-Tac-Toe — this problem is one of the few in this document where under-engineering is the safer default; add the abstraction only once a second game is actually requested (see O, M).

AB. Design Trade-Offs

Decision	Option A	Option B	Recommendation
Win-check scope	Full-board rescan every move	Incremental scan around only the last-played cell	Incremental — same correctness, strictly less work, and it's the natural implementation once you're scanning directions instead of enumerating lines
Template Method timing	Build `TurnBasedGame` upfront "in case" of future games	Build a plain loop now, extract the Template Method only when a second game is actually requested	Option B — see AA; this is a rare case in this document where premature abstraction is the more likely mistake, not premature concreteness

AC. Interviewer Evaluation

Strong signal: writing the win-check as a direction-scan from the start rather than enumerating lines; cleanly polymorphic Player subclasses; correctly judging not to build Template Method until a second game is actually on the table.

Red flag: hardcoded win-lines that silently break the moment board size is generalized; an isAI flag with branching logic; reflexively building a multi-game framework for a problem that only asked for Tic-Tac-Toe.

AD. Interview Simulation

Interviewer: Design Tic-Tac-Toe.

Candidate: A 3×3 grid, two players with distinct symbols, and a win-check. I'd write the win-check as a generic scan — for the cell just played, count consecutive matches in each of the four line directions — rather than listing the eight specific winning lines, since that generalizes for free.

Interviewer: Good. Now generalize it to any board size and any number-in-a-row to win.

Candidate: That's exactly why I avoided hardcoding the lines — the same scan works unchanged, I'd just parameterize K and the board dimension.

Interviewer: Add a computer player.

Candidate: I'd make Player an abstract type with HumanPlayer and AIPlayer subclasses rather than a flag, and give AIPlayer a swappable MoveStrategy so a smarter AI later is a new class, not a rewrite.

Interviewer: Would you build out a whole reusable game-engine framework here?

Candidate: Not unless a second game is actually requested — right now that would be speculative abstraction. I'd keep the loop simple and only extract a Template Method base class if Connect Four or something similar actually comes up.

AE. Online Solution Comparison

Source	Approach	Strength	Weakness	Worth Learning
GeeksforGeeks — Low-Level Design of Tic-Tac-Toe	Class-based design with separate Player and Board classes, functional/non-functional requirements laid out explicitly before the class diagram	Good requirements-first structure; clean SRP split between Board and game-flow control	Win-check in the public version is board-size-specific rather than presented as a generalized direction-scan	The requirements-first framing is worth adopting broadly, even outside this one problem
AlgoMaster.io — Design Tic-Tac-Toe	Object-oriented breakdown emphasizing Player abstraction and board state management as a stepping-stone LLD problem	Confirms Player-as-abstraction (not a boolean) as the expected shape	Public outline doesn't emphasize the generalized K-in-a-row scan as the central lesson	Validates the Player/Board split; this document's addition is treating win-check generality as the headline signal

AF. Interview Cheat Sheet

Problem	Tic-Tac-Toe / Board Game Engine
Difficulty	Beginner → Intermediate (Pattern Showcase)
Core requirements	N×N board, K-in-a-row win, human + AI players, draw detection
Key clarifications	Fixed 3×3 or generalized? Reusable engine for other games? AI sophistication? Player count?
Core entities	Board, Symbol, Player, HumanPlayer, AIPlayer, MoveStrategy, WinningStrategy, TurnBasedGame
Key relationships	Strategy for AI moves and win-checking; Template Method for the loop, only once a second game is real
Key patterns	Strategy (headline), Template Method (conditional, situational)
Most important decision	Generic direction-scan win-check, never hardcoded win-lines
Likely-changing behavior	Board size/win length, AI difficulty, game family
Concurrency concern	None beyond stale-turn validation for remote players
Top follow-ups	Generalize board/win-length, smarter AI, build a second game reusing the engine
Common mistakes	Hardcoded win-lines; isAI boolean instead of Player subclasses; premature Template Method framework for one game
What NOT to over-engineer	Don't build a multi-game engine or networked multiplayer unless actually asked

AG. Full Implementation

A complete, compilable reference implementation of every class in the diagram above (composition, inheritance, interface realization, and dependency-injected strategies all preserved per section I), with a runnable demo exercising the primary flow — in Java, C++, JavaScript, and TypeScript.

import java.util.*;

/**
 * Tic-Tac-Toe / Board Game Engine — full class-diagram implementation.
 *
 * TurnBasedGame is a Template Method: play() defines the fixed skeleton (setup -> loop
 * of get move / validate / place / check win-or-draw / switch turn) while setupBoard()
 * and the WinningStrategy are the pluggable hooks. WinningStrategy generically scans
 * K-in-a-row through the last move in every direction, so board size/win-length are
 * just parameters, never hardcoded coordinate lists.
 */
public class p12 {

    // ---------- Symbol (value) ----------
    static final class Symbol {
        final char value;
        Symbol(char value) { this.value = value; }
        @Override public String toString() { return String.valueOf(value); }
        @Override public boolean equals(Object o) { return o instanceof Symbol && ((Symbol) o).value == value; }
        @Override public int hashCode() { return value; }
    }

    // ---------- Move (value) ----------
    static final class Move {
        final int row, col;
        final Symbol symbol;
        Move(int row, int col, Symbol symbol) { this.row = row; this.col = col; this.symbol = symbol; }
    }

    enum MoveResultType { OK, INVALID, WIN, DRAW }
    static final class MoveResult {
        final MoveResultType type;
        final String message;
        MoveResult(MoveResultType type, String message) { this.type = type; this.message = message; }
    }

    // ---------- Board ----------
    /** Owns the grid and cell occupancy. Does NOT decide whether a placement wins. */
    static final class Board {
        final int size;
        private final Symbol[][] grid;

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

        boolean isValidMove(int row, int col) {
            return row >= 0 && row < size && col >= 0 && col < size && grid[row][col] == null;
        }

        void placeMark(int row, int col, Symbol symbol) {
            if (!isValidMove(row, col)) throw new IllegalArgumentException("Illegal move at " + row + "," + col);
            grid[row][col] = symbol;
        }

        Symbol get(int row, int col) {
            if (row < 0 || row >= size || col < 0 || col >= size) return null;
            return grid[row][col];
        }

        boolean isFull() {
            for (Symbol[] r : grid) for (Symbol s : r) if (s == null) return false;
            return true;
        }

        void print() {
            for (Symbol[] r : grid) {
                StringBuilder sb = new StringBuilder();
                for (Symbol s : r) sb.append(s == null ? '.' : s.value).append(' ');
                System.out.println(sb.toString().trim());
            }
        }
    }

    // ---------- WinningStrategy (interface, Strategy) ----------
    interface WinningStrategy {
        boolean checkWinner(Board board, Move lastMove);
    }

    /** Generic K-in-a-row check: scans every row/col/diagonal direction through the last move. */
    static final class LineScanWinningStrategy implements WinningStrategy {
        private final int k;
        LineScanWinningStrategy(int k) { this.k = k; }

        @Override
        public boolean checkWinner(Board board, Move lastMove) {
            Symbol symbol = board.get(lastMove.row, lastMove.col);
            if (symbol == null) return false;
            int[][] directions = { {0, 1}, {1, 0}, {1, 1}, {1, -1} }; // horizontal, vertical, diag, anti-diag
            for (int[] dir : directions) {
                int count = 1;
                count += countMatching(board, lastMove, dir[0], dir[1], symbol);
                count += countMatching(board, lastMove, -dir[0], -dir[1], symbol);
                if (count >= k) return true;
            }
            return false;
        }

        private int countMatching(Board board, Move move, int dRow, int dCol, Symbol symbol) {
            int count = 0;
            int r = move.row + dRow, c = move.col + dCol;
            while (symbol.equals(board.get(r, c))) {
                count++;
                r += dRow;
                c += dCol;
            }
            return count;
        }
    }

    // ---------- MoveStrategy (interface, Strategy) ----------
    interface MoveStrategy {
        Move decideMove(Board board, Symbol symbol);
    }

    /** Picks the first available empty cell -- trivially valid, deliberately simple default AI. */
    static final class FirstAvailableMoveStrategy implements MoveStrategy {
        @Override
        public Move decideMove(Board board, Symbol symbol) {
            for (int r = 0; r < board.size; r++) {
                for (int c = 0; c < board.size; c++) {
                    if (board.isValidMove(r, c)) return new Move(r, c, symbol);
                }
            }
            throw new IllegalStateException("No available moves");
        }
    }

    // ---------- Player (abstract) ----------
    /** Common identity for anything that produces a move. How the move is decided is delegated. */
    abstract static class Player {
        final String id;
        final Symbol symbol;
        Player(String id, Symbol symbol) { this.id = id; this.symbol = symbol; }
        abstract Move getMove(Board board);
    }

    /** Returns externally-supplied input as the move. */
    static final class HumanPlayer extends Player {
        private final Deque<int[]> pendingInputs = new ArrayDeque<>();

        HumanPlayer(String id, Symbol symbol) { super(id, symbol); }

        /** Feed the next external move (e.g. from UI/CLI input) before calling getMove(). */
        void supplyMove(int row, int col) { pendingInputs.addLast(new int[]{row, col}); }

        @Override
        Move getMove(Board board) {
            if (pendingInputs.isEmpty()) throw new IllegalStateException("No input supplied for human player " + id);
            int[] rc = pendingInputs.pollFirst();
            return new Move(rc[0], rc[1], symbol);
        }
    }

    /** Delegates move selection to a MoveStrategy -- the algorithm itself is not hardcoded here. */
    static final class AIPlayer extends Player {
        private final MoveStrategy moveStrategy;
        AIPlayer(String id, Symbol symbol, MoveStrategy moveStrategy) {
            super(id, symbol);
            this.moveStrategy = moveStrategy;
        }
        @Override
        Move getMove(Board board) { return moveStrategy.decideMove(board, symbol); }
    }

    // ---------- TurnBasedGame (abstract, Template Method) ----------
    abstract static class TurnBasedGame {
        Board board;
        final List<Player> players;
        final WinningStrategy winningStrategy;
        private int turnIndex = 0;
        private boolean finished = false;

        TurnBasedGame(List<Player> players, WinningStrategy winningStrategy) {
            this.players = players;
            this.winningStrategy = winningStrategy;
        }

        /** Hook: board dimensions/shape -- subclasses plug in their own structural piece. */
        protected abstract void setupBoard();

        protected abstract void declareResult(MoveResultType type, Player player);

        private Player nextPlayer() {
            Player p = players.get(turnIndex % players.size());
            turnIndex++;
            return p;
        }

        /** Template method: the fixed skeleton shared by any turn-based grid game. */
        MoveResult play() {
            setupBoard();
            while (!finished) {
                Player player = players.get(turnIndex % players.size());
                Move move = player.getMove(board);
                if (!board.isValidMove(move.row, move.col)) continue; // human retries; AI never produces one
                board.placeMark(move.row, move.col, player.symbol);
                nextPlayer();
                if (winningStrategy.checkWinner(board, move)) {
                    finished = true;
                    declareResult(MoveResultType.WIN, player);
                    return new MoveResult(MoveResultType.WIN, player.id + " wins");
                }
                if (board.isFull()) {
                    finished = true;
                    declareResult(MoveResultType.DRAW, null);
                    return new MoveResult(MoveResultType.DRAW, "draw");
                }
            }
            return new MoveResult(MoveResultType.OK, "game already finished");
        }

        boolean isFinished() { return finished; }
    }

    /** Concrete N x N, K-in-a-row game (default Tic-Tac-Toe: 3x3, 3-in-a-row). */
    static final class TicTacToeGame extends TurnBasedGame {
        private final int size;

        TicTacToeGame(int size, List<Player> players, WinningStrategy winningStrategy) {
            super(players, winningStrategy);
            this.size = size;
        }

        @Override
        protected void setupBoard() { this.board = new Board(size); }

        @Override
        protected void declareResult(MoveResultType type, Player player) {
            if (type == MoveResultType.WIN) System.out.println("Result: " + player.id + " (" + player.symbol + ") wins!");
            else System.out.println("Result: draw");
            board.print();
        }
    }

    // ---------- GameController (facade) ----------
    static final class GameController {
        private final TurnBasedGame game;
        GameController(TurnBasedGame game) { this.game = game; }

        MoveResult startGame() { return game.play(); }

        MoveResult makeMove(String playerId, int row, int col) {
            // For human players, external input is supplied before play()/loop consumes it.
            for (Player p : game.players) {
                if (p.id.equals(playerId) && p instanceof HumanPlayer) {
                    ((HumanPlayer) p).supplyMove(row, col);
                    return new MoveResult(MoveResultType.OK, "queued");
                }
            }
            return new MoveResult(MoveResultType.INVALID, "no such human player: " + playerId);
        }
    }

    // ---------- Demo ----------
    public static void main(String[] args) {
        Symbol X = new Symbol('X');
        Symbol O = new Symbol('O');

        HumanPlayer human = new HumanPlayer("P1", X);
        AIPlayer ai = new AIPlayer("P2", O, new FirstAvailableMoveStrategy());

        // Pre-supply a scripted sequence of human moves for this non-interactive demo.
        // Column 0 is targeted (rather than row 0) so it never collides with the AI's
        // deterministic "first empty cell" picks, which fill row 0 left-to-right first.
        human.supplyMove(0, 0);
        human.supplyMove(1, 0);
        human.supplyMove(2, 0); // completes left column -> human should win

        TicTacToeGame game = new TicTacToeGame(3, List.of(human, ai), new LineScanWinningStrategy(3));
        GameController controller = new GameController(game);

        MoveResult result = controller.startGame();
        System.out.println("Final: " + result.type + " -- " + result.message);
    }
}

// Tic-Tac-Toe / Board Game Engine -- full class-diagram implementation.
//
// TurnBasedGame is a Template Method: play() defines the fixed skeleton (setup -> loop
// of get move / validate / place / check win-or-draw / switch turn) while setupBoard()
// and the WinningStrategy are the pluggable hooks. WinningStrategy generically scans
// K-in-a-row through the last move in every direction, so board size/win-length are
// just parameters, never hardcoded coordinate lists.

#include <iostream>
#include <vector>
#include <string>
#include <memory>
#include <deque>
#include <stdexcept>

// ---------- Symbol (value) ----------
struct Symbol {
    char value;
    bool operator==(const Symbol& other) const { return value == other.value; }
};

// ---------- Move (value) ----------
struct Move {
    int row, col;
    Symbol symbol;
};

enum class MoveResultType { OK, INVALID, WIN, DRAW };
struct MoveResult { MoveResultType type; std::string message; };

// ---------- Board ----------
// Owns the grid and cell occupancy. Does NOT decide whether a placement wins.
class Board {
public:
    int size;
    explicit Board(int size_) : size(size_), grid_(size_, std::vector<bool>(size_, false)),
                                  symbols_(size_, std::vector<char>(size_, '\0')) {}

    bool isValidMove(int row, int col) const {
        return row >= 0 && row < size && col >= 0 && col < size && !grid_[row][col];
    }

    void placeMark(int row, int col, Symbol symbol) {
        if (!isValidMove(row, col)) throw std::invalid_argument("Illegal move");
        grid_[row][col] = true;
        symbols_[row][col] = symbol.value;
    }

    // Returns '\0' via hasSymbol=false when the cell is out of bounds or empty.
    bool get(int row, int col, Symbol& out) const {
        if (row < 0 || row >= size || col < 0 || col >= size || !grid_[row][col]) return false;
        out.value = symbols_[row][col];
        return true;
    }

    bool isFull() const {
        for (auto& r : grid_) for (bool occupied : r) if (!occupied) return false;
        return true;
    }

    void print() const {
        for (int r = 0; r < size; r++) {
            std::string line;
            for (int c = 0; c < size; c++) {
                line += grid_[r][c] ? symbols_[r][c] : '.';
                line += ' ';
            }
            std::cout << line << "\n";
        }
    }

private:
    std::vector<std::vector<bool>> grid_;
    std::vector<std::vector<char>> symbols_;
};

// ---------- WinningStrategy (interface, Strategy) ----------
struct WinningStrategy {
    virtual ~WinningStrategy() = default;
    virtual bool checkWinner(const Board& board, const Move& lastMove) = 0;
};

// Generic K-in-a-row check: scans every row/col/diagonal direction through the last move.
class LineScanWinningStrategy : public WinningStrategy {
public:
    explicit LineScanWinningStrategy(int k) : k_(k) {}

    bool checkWinner(const Board& board, const Move& lastMove) override {
        Symbol symbol;
        if (!board.get(lastMove.row, lastMove.col, symbol)) return false;
        static const int dirs[4][2] = { {0, 1}, {1, 0}, {1, 1}, {1, -1} };
        for (auto& d : dirs) {
            int count = 1;
            count += countMatching(board, lastMove, d[0], d[1], symbol);
            count += countMatching(board, lastMove, -d[0], -d[1], symbol);
            if (count >= k_) return true;
        }
        return false;
    }

private:
    int k_;

    int countMatching(const Board& board, const Move& move, int dRow, int dCol, const Symbol& symbol) const {
        int count = 0;
        int r = move.row + dRow, c = move.col + dCol;
        Symbol cell;
        while (board.get(r, c, cell) && cell == symbol) {
            count++;
            r += dRow;
            c += dCol;
        }
        return count;
    }
};

// ---------- MoveStrategy (interface, Strategy) ----------
struct MoveStrategy {
    virtual ~MoveStrategy() = default;
    virtual Move decideMove(const Board& board, Symbol symbol) = 0;
};

// Picks the first available empty cell -- trivially valid, deliberately simple default AI.
struct FirstAvailableMoveStrategy : MoveStrategy {
    Move decideMove(const Board& board, Symbol symbol) override {
        for (int r = 0; r < board.size; r++)
            for (int c = 0; c < board.size; c++)
                if (board.isValidMove(r, c)) return Move{r, c, symbol};
        throw std::runtime_error("No available moves");
    }
};

// ---------- Player (abstract) ----------
// Common identity for anything that produces a move. How the move is decided is delegated.
class Player {
public:
    std::string id;
    Symbol symbol;
    Player(std::string id_, Symbol symbol_) : id(std::move(id_)), symbol(symbol_) {}
    virtual ~Player() = default;
    virtual Move getMove(const Board& board) = 0;
};

// Returns externally-supplied input as the move.
class HumanPlayer : public Player {
public:
    HumanPlayer(std::string id_, Symbol symbol_) : Player(std::move(id_), symbol_) {}

    void supplyMove(int row, int col) { pendingInputs_.push_back({row, col}); }

    Move getMove(const Board&) override {
        if (pendingInputs_.empty()) throw std::runtime_error("No input supplied for human player " + id);
        auto rc = pendingInputs_.front();
        pendingInputs_.pop_front();
        return Move{rc.first, rc.second, symbol};
    }

private:
    std::deque<std::pair<int, int>> pendingInputs_;
};

// Delegates move selection to a MoveStrategy -- the algorithm itself is not hardcoded here.
class AIPlayer : public Player {
public:
    AIPlayer(std::string id_, Symbol symbol_, std::shared_ptr<MoveStrategy> strategy)
        : Player(std::move(id_), symbol_), moveStrategy_(std::move(strategy)) {}

    Move getMove(const Board& board) override { return moveStrategy_->decideMove(board, symbol); }

private:
    std::shared_ptr<MoveStrategy> moveStrategy_;
};

// ---------- TurnBasedGame (abstract, Template Method) ----------
class TurnBasedGame {
public:
    std::unique_ptr<Board> board;
    std::vector<std::shared_ptr<Player>> players;

    TurnBasedGame(std::vector<std::shared_ptr<Player>> players_, std::shared_ptr<WinningStrategy> winningStrategy)
        : players(std::move(players_)), winningStrategy_(std::move(winningStrategy)) {}
    virtual ~TurnBasedGame() = default;

    // Template method: the fixed skeleton shared by any turn-based grid game.
    MoveResult play() {
        setupBoard();
        while (!finished_) {
            auto player = players[turnIndex_ % players.size()];
            Move move = player->getMove(*board);
            if (!board->isValidMove(move.row, move.col)) continue; // human retries; AI never produces one
            board->placeMark(move.row, move.col, player->symbol);
            turnIndex_++;
            if (winningStrategy_->checkWinner(*board, move)) {
                finished_ = true;
                declareResult(MoveResultType::WIN, player);
                return MoveResult{MoveResultType::WIN, player->id + " wins"};
            }
            if (board->isFull()) {
                finished_ = true;
                declareResult(MoveResultType::DRAW, nullptr);
                return MoveResult{MoveResultType::DRAW, "draw"};
            }
        }
        return MoveResult{MoveResultType::OK, "game already finished"};
    }

protected:
    // Hook: board dimensions/shape -- subclasses plug in their own structural piece.
    virtual void setupBoard() = 0;
    virtual void declareResult(MoveResultType type, std::shared_ptr<Player> player) = 0;

private:
    std::shared_ptr<WinningStrategy> winningStrategy_;
    size_t turnIndex_ = 0;
    bool finished_ = false;
};

// Concrete N x N, K-in-a-row game (default Tic-Tac-Toe: 3x3, 3-in-a-row).
class TicTacToeGame : public TurnBasedGame {
public:
    TicTacToeGame(int size, std::vector<std::shared_ptr<Player>> players, std::shared_ptr<WinningStrategy> strategy)
        : TurnBasedGame(std::move(players), std::move(strategy)), size_(size) {}

protected:
    void setupBoard() override { board = std::make_unique<Board>(size_); }

    void declareResult(MoveResultType type, std::shared_ptr<Player> player) override {
        if (type == MoveResultType::WIN) std::cout << "Result: " << player->id << " (" << player->symbol.value << ") wins!\n";
        else std::cout << "Result: draw\n";
        board->print();
    }

private:
    int size_;
};

// ---------- GameController (facade) ----------
class GameController {
public:
    explicit GameController(std::shared_ptr<TurnBasedGame> game) : game_(std::move(game)) {}

    MoveResult startGame() { return game_->play(); }

    MoveResult makeMove(const std::string& playerId, int row, int col) {
        for (auto& p : game_->players) {
            if (p->id == playerId) {
                auto human = std::dynamic_pointer_cast<HumanPlayer>(p);
                if (human) {
                    human->supplyMove(row, col);
                    return MoveResult{MoveResultType::OK, "queued"};
                }
            }
        }
        return MoveResult{MoveResultType::INVALID, "no such human player: " + playerId};
    }

private:
    std::shared_ptr<TurnBasedGame> game_;
};

int main() {
    Symbol X{'X'};
    Symbol O{'O'};

    auto human = std::make_shared<HumanPlayer>("P1", X);
    auto ai = std::make_shared<AIPlayer>("P2", O, std::make_shared<FirstAvailableMoveStrategy>());

    // Pre-supply a scripted sequence of human moves for this non-interactive demo.
    // Column 0 is targeted (rather than row 0) so it never collides with the AI's
    // deterministic "first empty cell" picks, which fill row 0 left-to-right first.
    human->supplyMove(0, 0);
    human->supplyMove(1, 0);
    human->supplyMove(2, 0); // completes left column -> human should win

    auto game = std::make_shared<TicTacToeGame>(3, std::vector<std::shared_ptr<Player>>{human, ai},
                                                 std::make_shared<LineScanWinningStrategy>(3));
    GameController controller(game);

    MoveResult result = controller.startGame();
    std::cout << "Final: " << (result.type == MoveResultType::WIN ? "WIN" : "DRAW") << " -- " << result.message << "\n";

    return 0;
}

'use strict';
/**
 * Tic-Tac-Toe / Board Game Engine -- full class-diagram implementation.
 *
 * TurnBasedGame is a Template Method: play() defines the fixed skeleton (setup -> loop
 * of get move / validate / place / check win-or-draw / switch turn) while setupBoard()
 * and the WinningStrategy are the pluggable hooks. WinningStrategy generically scans
 * K-in-a-row through the last move in every direction, so board size/win-length are
 * just parameters, never hardcoded coordinate lists.
 */

// ---------- Board ----------
// Owns the grid and cell occupancy. Does NOT decide whether a placement wins.
class Board {
  constructor(size) {
    this.size = size;
    this.grid = Array.from({ length: size }, () => Array(size).fill(null));
  }

  isValidMove(row, col) {
    return row >= 0 && row < this.size && col >= 0 && col < this.size && this.grid[row][col] === null;
  }

  placeMark(row, col, symbol) {
    if (!this.isValidMove(row, col)) throw new Error(`Illegal move at ${row},${col}`);
    this.grid[row][col] = symbol;
  }

  get(row, col) {
    if (row < 0 || row >= this.size || col < 0 || col >= this.size) return null;
    return this.grid[row][col];
  }

  isFull() {
    return this.grid.every((r) => r.every((cell) => cell !== null));
  }

  print() {
    for (const row of this.grid) {
      console.log(row.map((c) => (c === null ? '.' : c)).join(' '));
    }
  }
}

// ---------- WinningStrategy (interface, Strategy) ----------
class WinningStrategy {
  checkWinner(_board, _lastMove) { throw new Error('not implemented'); }
}

// Generic K-in-a-row check: scans every row/col/diagonal direction through the last move.
class LineScanWinningStrategy extends WinningStrategy {
  constructor(k) { super(); this.k = k; }

  checkWinner(board, lastMove) {
    const symbol = board.get(lastMove.row, lastMove.col);
    if (symbol === null) return false;
    const directions = [[0, 1], [1, 0], [1, 1], [1, -1]]; // horizontal, vertical, diag, anti-diag
    for (const [dRow, dCol] of directions) {
      let count = 1;
      count += this._countMatching(board, lastMove, dRow, dCol, symbol);
      count += this._countMatching(board, lastMove, -dRow, -dCol, symbol);
      if (count >= this.k) return true;
    }
    return false;
  }

  _countMatching(board, move, dRow, dCol, symbol) {
    let count = 0;
    let r = move.row + dRow;
    let c = move.col + dCol;
    while (board.get(r, c) === symbol) {
      count++;
      r += dRow;
      c += dCol;
    }
    return count;
  }
}

// ---------- MoveStrategy (interface, Strategy) ----------
class MoveStrategy {
  decideMove(_board, _symbol) { throw new Error('not implemented'); }
}

// Picks the first available empty cell -- trivially valid, deliberately simple default AI.
class FirstAvailableMoveStrategy extends MoveStrategy {
  decideMove(board, symbol) {
    for (let r = 0; r < board.size; r++) {
      for (let c = 0; c < board.size; c++) {
        if (board.isValidMove(r, c)) return { row: r, col: c, symbol };
      }
    }
    throw new Error('No available moves');
  }
}

// ---------- Player (abstract) ----------
// Common identity for anything that produces a move. How the move is decided is delegated.
class Player {
  constructor(id, symbol) {
    if (new.target === Player) throw new Error('Player is abstract');
    this.id = id;
    this.symbol = symbol;
  }
  getMove(_board) { throw new Error('not implemented'); }
}

// Returns externally-supplied input as the move.
class HumanPlayer extends Player {
  constructor(id, symbol) {
    super(id, symbol);
    this._pendingInputs = [];
  }

  supplyMove(row, col) { this._pendingInputs.push([row, col]); }

  getMove(_board) {
    if (this._pendingInputs.length === 0) throw new Error(`No input supplied for human player ${this.id}`);
    const [row, col] = this._pendingInputs.shift();
    return { row, col, symbol: this.symbol };
  }
}

// Delegates move selection to a MoveStrategy -- the algorithm itself is not hardcoded here.
class AIPlayer extends Player {
  constructor(id, symbol, moveStrategy) {
    super(id, symbol);
    this.moveStrategy = moveStrategy;
  }
  getMove(board) { return this.moveStrategy.decideMove(board, this.symbol); }
}

// ---------- TurnBasedGame (abstract, Template Method) ----------
class TurnBasedGame {
  constructor(players, winningStrategy) {
    if (new.target === TurnBasedGame) throw new Error('TurnBasedGame is abstract');
    this.board = null;
    this.players = players;
    this.winningStrategy = winningStrategy;
    this._turnIndex = 0;
    this._finished = false;
  }

  // Hook: board dimensions/shape -- subclasses plug in their own structural piece.
  setupBoard() { throw new Error('not implemented'); }
  declareResult(_type, _player) { throw new Error('not implemented'); }

  // Template method: the fixed skeleton shared by any turn-based grid game.
  play() {
    this.setupBoard();
    while (!this._finished) {
      const player = this.players[this._turnIndex % this.players.length];
      const move = player.getMove(this.board);
      if (!this.board.isValidMove(move.row, move.col)) continue; // human retries; AI never produces one
      this.board.placeMark(move.row, move.col, player.symbol);
      this._turnIndex++;
      if (this.winningStrategy.checkWinner(this.board, move)) {
        this._finished = true;
        this.declareResult('WIN', player);
        return { type: 'WIN', message: `${player.id} wins` };
      }
      if (this.board.isFull()) {
        this._finished = true;
        this.declareResult('DRAW', null);
        return { type: 'DRAW', message: 'draw' };
      }
    }
    return { type: 'OK', message: 'game already finished' };
  }
}

// Concrete N x N, K-in-a-row game (default Tic-Tac-Toe: 3x3, 3-in-a-row).
class TicTacToeGame extends TurnBasedGame {
  constructor(size, players, winningStrategy) {
    super(players, winningStrategy);
    this.size = size;
  }

  setupBoard() { this.board = new Board(this.size); }

  declareResult(type, player) {
    if (type === 'WIN') console.log(`Result: ${player.id} (${player.symbol}) wins!`);
    else console.log('Result: draw');
    this.board.print();
  }
}

// ---------- GameController (facade) ----------
class GameController {
  constructor(game) { this.game = game; }

  startGame() { return this.game.play(); }

  makeMove(playerId, row, col) {
    for (const p of this.game.players) {
      if (p.id === playerId && p instanceof HumanPlayer) {
        p.supplyMove(row, col);
        return { type: 'OK', message: 'queued' };
      }
    }
    return { type: 'INVALID', message: `no such human player: ${playerId}` };
  }
}

// ---------- Demo ----------
function main() {
  const X = 'X';
  const O = 'O';

  const human = new HumanPlayer('P1', X);
  const ai = new AIPlayer('P2', O, new FirstAvailableMoveStrategy());

  // Pre-supply a scripted sequence of human moves for this non-interactive demo.
  // Column 0 is targeted (rather than row 0) so it never collides with the AI's
  // deterministic "first empty cell" picks, which fill row 0 left-to-right first.
  human.supplyMove(0, 0);
  human.supplyMove(1, 0);
  human.supplyMove(2, 0); // completes left column -> human should win

  const game = new TicTacToeGame(3, [human, ai], new LineScanWinningStrategy(3));
  const controller = new GameController(game);

  const result = controller.startGame();
  console.log(`Final: ${result.type} -- ${result.message}`);
}

if (require.main === module) {
  main();
}

module.exports = {
  Board, WinningStrategy, LineScanWinningStrategy, MoveStrategy, FirstAvailableMoveStrategy,
  Player, HumanPlayer, AIPlayer, TurnBasedGame, TicTacToeGame, GameController,
};

/**
 * Tic-Tac-Toe / Board Game Engine -- full class-diagram implementation.
 *
 * TurnBasedGame is a Template Method: play() defines the fixed skeleton (setup -> loop
 * of get move / validate / place / check win-or-draw / switch turn) while setupBoard()
 * and the WinningStrategy are the pluggable hooks. WinningStrategy generically scans
 * K-in-a-row through the last move in every direction, so board size/win-length are
 * just parameters, never hardcoded coordinate lists.
 */

type Symbol = string;

interface Move {
  row: number;
  col: number;
  symbol: Symbol;
}

type MoveResultType = 'OK' | 'INVALID' | 'WIN' | 'DRAW';
interface MoveResult {
  type: MoveResultType;
  message: string;
}

// ---------- Board ----------
// Owns the grid and cell occupancy. Does NOT decide whether a placement wins.
class Board {
  private grid: (Symbol | null)[][];

  constructor(readonly size: number) {
    this.grid = Array.from({ length: size }, () => Array<Symbol | null>(size).fill(null));
  }

  isValidMove(row: number, col: number): boolean {
    return row >= 0 && row < this.size && col >= 0 && col < this.size && this.grid[row][col] === null;
  }

  placeMark(row: number, col: number, symbol: Symbol): void {
    if (!this.isValidMove(row, col)) throw new Error(`Illegal move at ${row},${col}`);
    this.grid[row][col] = symbol;
  }

  get(row: number, col: number): Symbol | null {
    if (row < 0 || row >= this.size || col < 0 || col >= this.size) return null;
    return this.grid[row][col];
  }

  isFull(): boolean {
    return this.grid.every((r) => r.every((cell) => cell !== null));
  }

  print(): void {
    for (const row of this.grid) {
      console.log(row.map((c) => (c === null ? '.' : c)).join(' '));
    }
  }
}

// ---------- WinningStrategy (interface, Strategy) ----------
interface WinningStrategy {
  checkWinner(board: Board, lastMove: Move): boolean;
}

// Generic K-in-a-row check: scans every row/col/diagonal direction through the last move.
class LineScanWinningStrategy implements WinningStrategy {
  constructor(private readonly k: number) {}

  checkWinner(board: Board, lastMove: Move): boolean {
    const symbol = board.get(lastMove.row, lastMove.col);
    if (symbol === null) return false;
    const directions: [number, number][] = [[0, 1], [1, 0], [1, 1], [1, -1]]; // horizontal, vertical, diag, anti-diag
    for (const [dRow, dCol] of directions) {
      let count = 1;
      count += this.countMatching(board, lastMove, dRow, dCol, symbol);
      count += this.countMatching(board, lastMove, -dRow, -dCol, symbol);
      if (count >= this.k) return true;
    }
    return false;
  }

  private countMatching(board: Board, move: Move, dRow: number, dCol: number, symbol: Symbol): number {
    let count = 0;
    let r = move.row + dRow;
    let c = move.col + dCol;
    while (board.get(r, c) === symbol) {
      count++;
      r += dRow;
      c += dCol;
    }
    return count;
  }
}

// ---------- MoveStrategy (interface, Strategy) ----------
interface MoveStrategy {
  decideMove(board: Board, symbol: Symbol): Move;
}

// Picks the first available empty cell -- trivially valid, deliberately simple default AI.
class FirstAvailableMoveStrategy implements MoveStrategy {
  decideMove(board: Board, symbol: Symbol): Move {
    for (let r = 0; r < board.size; r++) {
      for (let c = 0; c < board.size; c++) {
        if (board.isValidMove(r, c)) return { row: r, col: c, symbol };
      }
    }
    throw new Error('No available moves');
  }
}

// ---------- Player (abstract) ----------
// Common identity for anything that produces a move. How the move is decided is delegated.
abstract class Player {
  constructor(readonly id: string, readonly symbol: Symbol) {}
  abstract getMove(board: Board): Move;
}

// Returns externally-supplied input as the move.
class HumanPlayer extends Player {
  private pendingInputs: [number, number][] = [];

  supplyMove(row: number, col: number): void {
    this.pendingInputs.push([row, col]);
  }

  getMove(_board: Board): Move {
    const next = this.pendingInputs.shift();
    if (!next) throw new Error(`No input supplied for human player ${this.id}`);
    const [row, col] = next;
    return { row, col, symbol: this.symbol };
  }
}

// Delegates move selection to a MoveStrategy -- the algorithm itself is not hardcoded here.
class AIPlayer extends Player {
  constructor(id: string, symbol: Symbol, private readonly moveStrategy: MoveStrategy) {
    super(id, symbol);
  }
  getMove(board: Board): Move { return this.moveStrategy.decideMove(board, this.symbol); }
}

// ---------- TurnBasedGame (abstract, Template Method) ----------
abstract class TurnBasedGame {
  board!: Board;
  private turnIndex = 0;
  private finished = false;

  constructor(readonly players: Player[], private readonly winningStrategy: WinningStrategy) {}

  /** Hook: board dimensions/shape -- subclasses plug in their own structural piece. */
  protected abstract setupBoard(): void;
  protected abstract declareResult(type: 'WIN' | 'DRAW', player: Player | null): void;

  /** Template method: the fixed skeleton shared by any turn-based grid game. */
  play(): MoveResult {
    this.setupBoard();
    while (!this.finished) {
      const player = this.players[this.turnIndex % this.players.length];
      const move = player.getMove(this.board);
      if (!this.board.isValidMove(move.row, move.col)) continue; // human retries; AI never produces one
      this.board.placeMark(move.row, move.col, player.symbol);
      this.turnIndex++;
      if (this.winningStrategy.checkWinner(this.board, move)) {
        this.finished = true;
        this.declareResult('WIN', player);
        return { type: 'WIN', message: `${player.id} wins` };
      }
      if (this.board.isFull()) {
        this.finished = true;
        this.declareResult('DRAW', null);
        return { type: 'DRAW', message: 'draw' };
      }
    }
    return { type: 'OK', message: 'game already finished' };
  }
}

// Concrete N x N, K-in-a-row game (default Tic-Tac-Toe: 3x3, 3-in-a-row).
class TicTacToeGame extends TurnBasedGame {
  constructor(private readonly size: number, players: Player[], winningStrategy: WinningStrategy) {
    super(players, winningStrategy);
  }

  protected setupBoard(): void { this.board = new Board(this.size); }

  protected declareResult(type: 'WIN' | 'DRAW', player: Player | null): void {
    if (type === 'WIN' && player) console.log(`Result: ${player.id} (${player.symbol}) wins!`);
    else console.log('Result: draw');
    this.board.print();
  }
}

// ---------- GameController (facade) ----------
class GameController {
  constructor(private readonly game: TurnBasedGame) {}

  startGame(): MoveResult { return this.game.play(); }

  makeMove(playerId: string, row: number, col: number): MoveResult {
    for (const p of this.game.players) {
      if (p.id === playerId && p instanceof HumanPlayer) {
        p.supplyMove(row, col);
        return { type: 'OK', message: 'queued' };
      }
    }
    return { type: 'INVALID', message: `no such human player: ${playerId}` };
  }
}

// ---------- Demo ----------
function main(): void {
  const X: Symbol = 'X';
  const O: Symbol = 'O';

  const human = new HumanPlayer('P1', X);
  const ai = new AIPlayer('P2', O, new FirstAvailableMoveStrategy());

  // Pre-supply a scripted sequence of human moves for this non-interactive demo.
  // Column 0 is targeted (rather than row 0) so it never collides with the AI's
  // deterministic "first empty cell" picks, which fill row 0 left-to-right first.
  human.supplyMove(0, 0);
  human.supplyMove(1, 0);
  human.supplyMove(2, 0); // completes left column -> human should win

  const game = new TicTacToeGame(3, [human, ai], new LineScanWinningStrategy(3));
  const controller = new GameController(game);

  const result = controller.startGame();
  console.log(`Final: ${result.type} -- ${result.message}`);
}

if (require.main === module) {
  main();
}

export {
  Board, WinningStrategy, LineScanWinningStrategy, MoveStrategy, FirstAvailableMoveStrategy,
  Player, HumanPlayer, AIPlayer, TurnBasedGame, TicTacToeGame, GameController,
};

← 11. Elevator System 13. Chess Game →