13. Chess Game Intermediate → Advanced

Jump to section:

A. Realistic Interview Prompt

"Design a two-player chess game. Support standard piece movement, detecting check and checkmate, and undoing a move. You do not need a graphical interface."

B. Difficulty

Intermediate → Advanced. Per-piece movement rules are mechanical; the real difficulty is check/checkmate detection (which requires simulating a move before committing to it) and building undo cleanly without an ad hoc "remember the last few fields I changed" hack.

C. What This Problem Tests

Judgment on inheritance vs. Strategy for piece movement — and recognizing that plain polymorphism is the correct simple answer here, not an under-engineered one
Modeling a move as a first-class Command object, enabling undo/redo and move-history without special-casing
Check detection as "is the king's square attacked by any opposing piece," reusing each piece's own move-generation logic rather than writing a separate parallel algorithm
Recognizing which real chess rules (castling, en passant, promotion) are meaningful scope-boundary discussions rather than something to silently skip or silently over-build

D. Requirements

Functional

Standard 8×8 board, standard piece set and starting position for two players (White, Black)
Enforce each piece type's legal movement, including captures
Detect check, checkmate, and stalemate
Reject any move that would leave the moving player's own king in check
Support undo of the most recent move

Non-Functional

Adding a new piece-movement rule (a variant game) must not require changes to the turn/check-detection engine
Undo must restore all incidental state a move may have changed (captured piece, castling rights), not just the piece's square

E. Clarifying Questions

#	Question	Why It Matters	Design Decision Affected
1	Are special moves (castling, en passant, pawn promotion) in scope?	Each adds meaningful state and edge-case handling well beyond basic movement	Scope of `Move`'s special-move flags (see F, V)
2	Is this local two-player, or does it need to support two remote players over a network?	Determines whether server-authoritative move validation is in scope	Scope of W
3	Is a full undo/redo history required, or just single-move undo?	Affects whether moves are stored as a stack or a full navigable list	Data structure in S
4	Do we need move legality only, or also position evaluation (for an AI opponent)?	An AI opponent is an entirely separate, much larger scope (search + evaluation)	Explicitly excluded by assumption (see F)

F. Assumptions

Confirmed: standard 8×8 board, standard pieces, check/checkmate/stalemate detection, single-move undo.
Assumption: castling, en passant, and promotion are in scope but flagged explicitly as the highest-complexity part of the design (see V) rather than silently simplified away.
Assumption: no AI opponent — an engine that evaluates positions (minimax, alpha-beta, neural evaluation) is an entirely different, much larger problem than legality-checking, and is named but out of scope unless the interviewer pivots there.
Assumption: local two-player by default; network play, if raised, adds a server-authoritative validation boundary but doesn't change the core piece/board/move model.

G. Actors

Actor	Responsibility
Player	Submits moves for their color on their turn
ChessGame (facade)	Validates, applies, and records moves; detects check/checkmate

H. Core Domain Entities

Class	Responsibility	Key Attributes	Key Methods	Does NOT Handle
`Piece` (abstract)	Identity + its own movement rule	color, position	`getValidMoves(board)`	Whether a move leaves its own king in check — that's the Game's job, one level up
`Pawn`, `Rook`, `Knight`, `Bishop`, `Queen`, `King`	Concrete movement rules	—	`getValidMoves(board)`	—
`Board`	8×8 grid of pieces, occupancy queries	grid	`getPieceAt()`, `isSquareAttacked(square, byColor)`	Move legality by chess rules — only raw occupancy/attack facts
`Move` (Command)	One executed move, reversible	from, to, movedPiece, capturedPiece, specialFlag	`execute(board)`, `undo(board)`	Deciding whether the move was legal in the first place
`MoveHistory`	Stack of executed `Move` commands	—	`push()`, `popAndUndo()`	—
`ChessGame` (facade)	Turn order, move validation, check/checkmate detection	board, currentTurn, history	`makeMove()`, `undo()`, `isInCheck(color)`, `isCheckmate(color)`	Piece-level movement math

I. Class Relationships

Why plain polymorphism, not Strategy, for piece movement (a deliberate rejection): Strategy exists to let the same object swap algorithms independently of its identity. A Rook's movement rule is not independent of being a Rook — a piece's type and its movement rule are the same fact, and always change together (a Rook never needs to "become" bishop-movement without becoming a Bishop). Plain subclassing (Piece → Rook/Bishop/…) is the honest, simpler answer, and reaching for Strategy here would be pattern-matching for its own sake rather than solving a real independent-variation problem — the same kind of judgment call as Splitwise's Payment-as-sibling-not-subclass, just landing on the opposite pattern.
Command (headline) for moves: a Move knows how to execute() and undo() itself, including restoring a captured piece and any castling-rights side effects. This is what makes undo a one-line pop-and-undo off a MoveHistory stack instead of manually diffing board state.
Check detection reuses getValidMoves(), it doesn't duplicate it: "is my king in check" is exactly "does any opposing piece's valid-move set include my king's square" — Board.isSquareAttacked() is built directly on the same per-piece movement logic already written for regular moves, not a second parallel implementation.
Why Command over Memento for undo: a full-board Memento snapshot per move is simpler to reason about (no risk of forgetting an incidental field) but far more memory per move; a Command that stores only the delta (moved piece, captured piece, one flag) is the more space-efficient standard choice for a game with potentially hundreds of moves in a history — see AB for the explicit trade-off.

J. Class Diagram

View Mermaid source

classDiagram
  class Piece {
    <<abstract>>
    color
    position
    +getValidMoves(board)
  }
  Piece <|-- Pawn
  Piece <|-- Rook
  Piece <|-- Knight
  Piece <|-- Bishop
  Piece <|-- Queen
  Piece <|-- King
  class Board {
    grid
    +getPieceAt()
    +isSquareAttacked()
  }
  class Move {
    from
    to
    movedPiece
    capturedPiece
    +execute(board)
    +undo(board)
  }
  class MoveHistory {
    +push()
    +popAndUndo()
  }
  class ChessGame {
    board
    currentTurn
    +makeMove()
    +undo()
    +isInCheck()
    +isCheckmate()
  }
  Board --> "*" Piece
  ChessGame --> Board
  ChessGame --> MoveHistory
  ChessGame --> Move : creates

K. Responsibility Mapping

Class	Responsibility	Does NOT Handle
Piece subclasses	Own movement-generation rule	Whether the resulting position leaves the mover's king in check
Board	Occupancy and attack queries	Chess-rule legality itself
Move	Executing and reversing one specific move, including side effects	Deciding legality upfront
ChessGame	Turn order, legality gate (including self-check rejection), checkmate detection	Piece-level movement math, raw board storage

L. SOLID Analysis

Principle	How It's Applied	Naive Violation
SRP	Each piece subclass owns only its own movement rule; `ChessGame` owns turn/check orchestration; `Move` owns execute/undo	One `Piece` class with a `type` enum and a giant switch inside `getValidMoves()`
OCP	A chess variant with a new piece is a new `Piece` subclass, zero changes to `ChessGame`	Adding a new piece type means editing a central switch statement everywhere piece behavior is referenced
LSP	Every `Piece` subclass honestly returns only its own legal geometric moves; `ChessGame` layers the check-rejection filter identically on top of any piece type	A `King` subclass secretly also implementing "am I in check" logic that other pieces don't have, breaking substitutability in `getValidMoves()` callers
ISP	`Piece` stays a small interface (position, color, movement); undo/history concerns live entirely in `Move`/`MoveHistory`, not forced onto `Piece`	Forcing every `Piece` to implement its own `undo()` instead of centralizing that in `Move`
DIP	`ChessGame` depends on the abstract `Piece.getValidMoves()`, never on a concrete piece type	`ChessGame.isInCheck()` doing `instanceof Rook`/`instanceof Bishop` checks inline instead of delegating uniformly

M. Design Patterns

Pattern	Problem It Solves	Where It Appears	When NOT to Use
Command	Moves need to be executed, undone, and recorded uniformly	`Move`, `MoveHistory`	Skip only if undo/history is explicitly out of scope
Template Method (optional)	Every piece's move-generation shares a "generate candidates, filter off-board, filter same-color-occupied" skeleton	Optional shared base logic in `Piece` with a `generateCandidates()` hook	Skip if each piece's geometry is different enough that a shared skeleton adds more ceremony than it saves

Explicitly avoided: Strategy for piece movement — see I for why plain polymorphism is the correct, deliberate choice, not a missed opportunity.

N. What Is Likely to Change?

Behavior	Current Design	Anticipated Change	Protecting Abstraction
Special moves	Basic movement only	Castling, en passant, promotion	`Move`'s optional `specialFlag` and side-effect fields, without changing the base execute/undo contract
Network play	Local, trusted calls to `makeMove()`	Two remote clients submitting moves	`ChessGame` becomes the single server-authoritative validator; no change to `Piece`/`Board`
Opponent type	Two human players	An AI opponent	A new evaluation/search layer consuming `getValidMoves()` as its move generator — entirely additive

O. Design Evolution

V1: board + pieces with basic movement, no check detection, no undo.
V2: add isSquareAttacked() and self-check rejection once "you can't move into check" becomes a real requirement.
V3: extract Move as a Command once undo is requested, replacing any ad hoc "remember what I changed" approach.
V4: add checkmate/stalemate detection (no legal move exists that escapes check) once the game needs to actually end.
V5: add castling/en passant/promotion as explicit special-move handling once requested — flagged as the highest-complexity increment, not a drop-in.

What stays stable: Piece.getValidMoves()'s signature and ChessGame.makeMove()'s public contract. Special moves and network play both layer on without touching the base movement model.

P. API / Interface Design

abstract class Piece {
  Color color; Position position;
  abstract List<Position> getValidMoves(Board board);
}

class Move {
  void execute(Board board);
  void undo(Board board);
}

class ChessGame {
  MoveResult makeMove(Position from, Position to);
  void undo();
  boolean isInCheck(Color color);
  boolean isCheckmate(Color color);
}

abstract class Piece {
  Color color; Position position;
  abstract List<Position> getValidMoves(Board board);
}

class Move {
  void execute(Board board);
  void undo(Board board);
}

class ChessGame {
  MoveResult makeMove(Position from, Position to);
  void undo();
  boolean isInCheck(Color color);
  boolean isCheckmate(Color color);
}

class Piece {
public:
  Color color; Position position;
  virtual std::vector<Position> getValidMoves(const Board& board) = 0;
};

class Move {
public:
  void execute(Board& board);
  void undo(Board& board);
};

class ChessGame {
public:
  MoveResult makeMove(Position from, Position to);
  void undo();
  bool isInCheck(Color color);
  bool isCheckmate(Color color);
};

class Piece {
  constructor(color, position) {
    this.color = color;
    this.position = position;
  }
  getValidMoves(board) { throw new Error('not implemented'); }
}

class Move {
  execute(board) {}
  undo(board) {}
}

class ChessGame {
  makeMove(from, to) {}
  undo() {}
  isInCheck(color) {}
  isCheckmate(color) {}
}

abstract class Piece {
  color: Color;
  position: Position;
  abstract getValidMoves(board: Board): Position[];
}

class Move {
  execute(board: Board): void {}
  undo(board: Board): void {}
}

class ChessGame {
  makeMove(from: Position, to: Position): MoveResult {}
  undo(): void {}
  isInCheck(color: Color): boolean {}
  isCheckmate(color: Color): boolean {}
}

Ownership/validation notes: makeMove() first asks the piece at from for its candidate moves, confirms to is among them, then simulates the move on the board, checks isInCheck(movingColor) against the simulated result, and only commits (pushes to MoveHistory) if the simulated position is legal — otherwise it reverts the simulation and rejects the move.

Q. Pseudocode — Critical Logic

ChessGame.makeMove(from, to):
  piece = board.getPieceAt(from)
  if piece == null or piece.color != currentTurn: reject
  if to not in piece.getValidMoves(board): reject

  move = new Move(from, to, piece, board.getPieceAt(to))
  move.execute(board)                      // simulate
  if isInCheck(currentTurn):
    move.undo(board)                       // illegal — leaves own king in check
    reject
  history.push(move)                        // commit
  currentTurn = opponent(currentTurn)
  if isCheckmate(currentTurn): declareWinner(piece.color)

Board.isSquareAttacked(square, byColor):
  for each piece on board where piece.color == byColor:
    if square in piece.getValidMoves(board): return true
  return false

MoveResult makeMove(Position from, Position to) {
  Piece piece = board.getPieceAt(from);
  if (piece == null || piece.getColor() != currentTurn) return MoveResult.REJECT;
  if (!piece.getValidMoves(board).contains(to)) return MoveResult.REJECT;

  Move move = new Move(from, to, piece, board.getPieceAt(to));
  move.execute(board);                      // simulate
  if (isInCheck(currentTurn)) {
    move.undo(board);                       // illegal — leaves own king in check
    return MoveResult.REJECT;
  }
  history.push(move);                        // commit
  currentTurn = opponent(currentTurn);
  if (isCheckmate(currentTurn)) declareWinner(piece.getColor());
  return MoveResult.OK;
}

boolean isSquareAttacked(Position square, Color byColor) {
  for (Piece piece : board.getPieces()) {
    if (piece.getColor() == byColor && piece.getValidMoves(board).contains(square)) return true;
  }
  return false;
}

MoveResult ChessGame::makeMove(Position from, Position to) {
  auto piece = board.getPieceAt(from);
  if (piece == nullptr || piece->color != currentTurn) return MoveResult::REJECT;
  auto validMoves = piece->getValidMoves(board);
  if (std::find(validMoves.begin(), validMoves.end(), to) == validMoves.end()) return MoveResult::REJECT;

  Move move(from, to, piece, board.getPieceAt(to));
  move.execute(board);                      // simulate
  if (isInCheck(currentTurn)) {
    move.undo(board);                       // illegal — leaves own king in check
    return MoveResult::REJECT;
  }
  history.push(move);                        // commit
  currentTurn = opponent(currentTurn);
  if (isCheckmate(currentTurn)) declareWinner(piece->color);
  return MoveResult::OK;
}

bool Board::isSquareAttacked(Position square, Color byColor) {
  for (auto& piece : pieces) {
    if (piece->color != byColor) continue;
    auto moves = piece->getValidMoves(*this);
    if (std::find(moves.begin(), moves.end(), square) != moves.end()) return true;
  }
  return false;
}

makeMove(from, to) {
  const piece = this.board.getPieceAt(from);
  if (piece === null || piece.color !== this.currentTurn) return MoveResult.REJECT;
  if (!piece.getValidMoves(this.board).includes(to)) return MoveResult.REJECT;

  const move = new Move(from, to, piece, this.board.getPieceAt(to));
  move.execute(this.board);                      // simulate
  if (this.isInCheck(this.currentTurn)) {
    move.undo(this.board);                       // illegal — leaves own king in check
    return MoveResult.REJECT;
  }
  this.history.push(move);                        // commit
  this.currentTurn = opponent(this.currentTurn);
  if (this.isCheckmate(this.currentTurn)) this.declareWinner(piece.color);
  return MoveResult.OK;
}

isSquareAttacked(square, byColor) {
  for (const piece of this.board.getPieces()) {
    if (piece.color === byColor && piece.getValidMoves(this.board).includes(square)) return true;
  }
  return false;
}

makeMove(from: Position, to: Position): MoveResult {
  const piece = this.board.getPieceAt(from);
  if (piece === null || piece.color !== this.currentTurn) return MoveResult.REJECT;
  if (!piece.getValidMoves(this.board).includes(to)) return MoveResult.REJECT;

  const move = new Move(from, to, piece, this.board.getPieceAt(to));
  move.execute(this.board);                      // simulate
  if (this.isInCheck(this.currentTurn)) {
    move.undo(this.board);                       // illegal — leaves own king in check
    return MoveResult.REJECT;
  }
  this.history.push(move);                        // commit
  this.currentTurn = opponent(this.currentTurn);
  if (this.isCheckmate(this.currentTurn)) this.declareWinner(piece.color);
  return MoveResult.OK;
}

isSquareAttacked(square: Position, byColor: Color): boolean {
  for (const piece of this.board.getPieces()) {
    if (piece.color === byColor && piece.getValidMoves(this.board).includes(square)) return true;
  }
  return false;
}

R. End-to-End Use Case

makeMove(e2, e4)  — White pawn
  │  e4 in Pawn.getValidMoves(board)? yes → simulate → isInCheck(WHITE)? no → commit
  ▼
makeMove(e7, e5)  — Black pawn (symmetric)
  ▼
... play continues ...
  ▼
makeMove(d8, h4)  — Black queen delivers check
  │  after commit: isInCheck(WHITE) == true
  ▼
White's next makeMove() candidates are filtered: any move that doesn't resolve
the check is rejected the same way as any other self-check-inducing move
  ▼
If no legal move exists for WHITE while in check → isCheckmate(WHITE) == true → game ends

S. Data Structures

Structure	Used For	Why	Alternative & Trade-off
8×8 array of `Piece` references	Board storage	O(1) position lookup, matches the physical board directly	A bitboard (64-bit integer per piece type) is the real high-performance chess-engine representation, but is overkill complexity for an LLD interview unless explicitly asked for engine-level performance
Stack of `Move` (Command) objects	Undo history	O(1) push and pop-and-undo of the most recent move	Full board-snapshot-per-move (Memento) trades higher memory for simpler reasoning — see AB

T. Complexity Analysis

Operation	Time	Space
`getValidMoves()` per piece	O(1) to O(8) depending on piece type (sliding pieces scan up to board length)	O(1)
`isInCheck()` / `isSquareAttacked()`	O(pieces) × O(moves per piece) ≈ O(32 × 8) worst case	O(1)
`isCheckmate()`	O(pieces × moves per piece) to enumerate all candidate escapes, each simulated	O(1) per simulation

U. Testing Strategy

Happy path: each piece type's movement matches its rule exactly, including capture-vs-block distinctions (a pawn captures diagonally but moves straight).
Edge cases: a move that would leave the mover's own king in check is rejected even though the piece's raw geometry allows it; checkmate is detected only when truly no legal escape exists (not merely "the king is attacked").
Undo correctness: undoing a capturing move restores the captured piece to its original square and color, not just the mover's position.
Special-move tests (if in scope): castling is rejected if the king has previously moved, if the rook has previously moved, or if any square in the king's path is attacked.

V. Interviewer Follow-Ups

Follow-Up	Testing	Design Change	Classes Changed	Pattern/Trade-off
"Add castling, en passant, and pawn promotion."	Recognizing this as the single highest-complexity increment in the whole problem	`Move` gains special-move flags and side-effect state (rook position for castling, en passant target square); `King`/`Rook` track "has moved"	Move, King, Rook, ChessGame	A strong candidate names the complexity explicitly rather than hand-waving it (echoes File System's symlink follow-up)
"Support two players over a network."	Server-authoritative validation reasoning	`ChessGame` becomes the single source of truth a server runs; clients submit intents, not state	ChessGame (deployment context), no core-model change	Validates the Piece/Board separation from network concerns
"Add an AI opponent."	LLD/HLD (and LLD/AI) boundary awareness	N/A at this layer — candidate should name minimax/alpha-beta position evaluation as a separate, much larger scope	N/A	Recognizing the boundary is the actual signal

W. Concurrency

A single game is inherently turn-based and single-writer — only one move is ever being validated/applied at a time, so there is no shared-resource race analogous to Parking Lot's or Elevator's. The one real concern, and only if network play is in scope, is server-side move authority: the server (running the same ChessGame) must be the sole place a move is validated and committed, rejecting a client's move if it doesn't match the server's current turn/board state — a staleness check, not a lock.

X. Persistence

Move history doubles naturally as a persistence log — replaying the MoveHistory stack from the initial position reconstructs the full game, which is exactly how real chess notation (PGN) works. Persisting a game is therefore "serialize the move list," not "serialize the board," which is both more compact and naturally resumable.

Y. Scaling Boundary

Layer	What Belongs Here
LLD	Piece movement, board, move Command/undo, check/checkmate detection
HLD	Matchmaking, ranking/rating systems, spectator broadcast at scale
Separate large domain	AI opponent (search + evaluation) — related to, but distinct from, this LLD problem

Z. Failure Scenarios

A client submits a move for a turn that already passed (stale network message): rejected by the turn-order check before any board simulation happens.
Undo requested with no moves in history: a no-op rejection, not an exception from popping an empty stack.
A simulated move is found illegal (leaves own king in check): the simulation is fully reverted via the same Move.undo() path used for ordinary undo — there is exactly one reversal code path, not a separate "rollback a rejected move" special case.

AA. Common Bad Designs

One Piece class with a type enum and a switch statement inside getValidMoves() instead of real subclasses — the most common naive shape for this problem.
Checking for check with a separate, hand-rolled attack algorithm instead of reusing getValidMoves() — duplicated logic that inevitably drifts out of sync with actual piece movement rules.
Undo implemented as "remember the last few (from, to) squares" without capturing the captured piece or castling-rights side effects — passes simple tests, corrupts the board on any capture-undo.
Applying Strategy to piece movement "for consistency" with other problems in this document — see I; the pattern must fit the actual variation, not be applied reflexively for stylistic consistency.

AB. Design Trade-Offs

Decision	Option A	Option B	Recommendation
Undo mechanism	Command (store move delta + reverse operation)	Memento (store a full board snapshot per move)	Command for memory efficiency over a long game; Memento only if the incidental-state bookkeeping for reversal (castling rights, en passant target) becomes error-prone enough that simplicity outweighs the memory cost
Board representation	2D array of piece references	Bitboards (one 64-bit integer per piece type)	Array for an LLD interview — clear and directly maps to the problem; bitboards are a real chess-engine performance technique, not an LLD-interview expectation unless explicitly asked

AC. Interviewer Evaluation

Strong signal: explicitly explaining why piece movement is plain polymorphism and not Strategy; reusing getValidMoves() for check detection instead of writing a second algorithm; simulate-then-validate-then-commit as the shape of makeMove(); naming castling/en passant/promotion as a real complexity jump rather than glossing over them.

Red flag: a type-enum-and-switch Piece class; a separate hand-rolled check-detection algorithm; undo that only restores the moved piece's position; reflexively reaching for Strategy on piece movement without justification.

AD. Interview Simulation

Interviewer: Design a chess game.

Candidate: Each piece type has its own movement rule, so I'd make Piece abstract with a concrete subclass per type — Rook, Bishop, and so on — each implementing its own getValidMoves(). I'd deliberately avoid Strategy here since a piece's type and its movement rule are the same fact and always change together.

Interviewer: How do you detect check?

Candidate: "In check" just means the king's square is attacked — I'd reuse the exact same getValidMoves() every piece already implements: scan the opponent's pieces, and if any of their valid moves include my king's square, I'm in check. No separate algorithm.

Interviewer: How would you support undo?

Candidate: Model each move as a Command with execute() and undo(), storing the captured piece and any side effects, and push it onto a history stack. Undo is just pop-and-undo — and I actually reuse that same reversal path when a simulated move turns out to leave my own king in check.

Interviewer: What about castling and en passant?

Candidate: I'd flag those explicitly as the highest-complexity part of the design — castling needs "has this king or rook ever moved" tracking plus an attacked-square check along the king's path, and en passant needs one extra piece of transient state for the target square. I wouldn't want to quietly simplify those away without naming the cost.

AE. Online Solution Comparison

Source	Approach	Strength	Weakness	Worth Learning
AlgoMaster.io — Design Chess Game	Piece class hierarchy with per-piece movement, a Board class, and a Game orchestrator, presented as a stepping-stone LLD problem	Confirms the Piece-subclass (not Strategy) shape as the expected answer	Public outline does not deeply emphasize reusing movement logic for check detection, or the Command-based undo trade-off	Validates the core class shape; this document's contribution is the explicit Strategy-rejection reasoning and the Command/Memento trade-off
GeeksforGeeks — Design a Chess Game	Class-diagram-first approach covering Board, Piece hierarchy, and Player, with movement validation per piece	Clear separation of Board from Piece responsibilities	Less emphasis on check/checkmate as a reused attack-query rather than a bespoke algorithm	Useful as a structural cross-check for the Board/Piece boundary

AF. Interview Cheat Sheet

Problem	Chess Game
Difficulty	Intermediate → Advanced
Core requirements	Standard movement, check/checkmate/stalemate detection, undo
Key clarifications	Special moves in scope? Local or networked? Undo/redo depth? AI opponent needed?
Core entities	Piece (+ 6 subclasses), Board, Move, MoveHistory, ChessGame
Key relationships	Plain polymorphism for movement (Strategy deliberately rejected); Command for moves; check reuses move-generation
Key patterns	Command (headline), optional Template Method for shared move-generation steps
Most important decision	Simulate → validate (no self-check) → commit, as one atomic sequence per move
Likely-changing behavior	Special moves, network play, AI opponent
Concurrency concern	Server-authoritative move validation for networked play; otherwise single-writer by nature
Top follow-ups	Castling/en passant/promotion, networked play, AI opponent (LLD/AI boundary)
Common mistakes	Type-enum-and-switch Piece class; duplicated check-detection algorithm; incomplete undo; reflexive Strategy on piece movement
What NOT to over-engineer	Don't build bitboards or an AI evaluation engine unless explicitly 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.

// Chess Game - full LLD implementation (single-file demo).
// No "Concurrency" badge -> single-threaded, no locks needed.
//
// Design notes:
// - Piece uses plain subclassing (not Strategy): a piece's type and its movement rule
//   are the same fact and always change together, so Piece -> Rook/Bishop/... is the
//   honest simpler answer.
// - Move is a Command: it knows how to execute()/undo() itself (including restoring a
//   captured piece), so ChessGame.undo() is a one-line pop-and-undo off MoveHistory.
// - Board.isSquareAttacked() reuses each piece's own getValidMoves() rather than a
//   second parallel "attack" implementation - check detection is exactly "does any
//   opposing piece's move-set include this square".
import java.util.*;

public class p13 {

    enum Color { WHITE, BLACK }

    enum MoveResult { OK, CHECK, CHECKMATE, STALEMATE, REJECTED_ILLEGAL, REJECTED_SELF_CHECK }

    // ---------- Position ----------
    static final class Position {
        final int row, col;
        Position(int row, int col) { this.row = row; this.col = col; }
        boolean inBounds() { return row >= 0 && row < 8 && col >= 0 && col < 8; }
        @Override public boolean equals(Object o) {
            if (!(o instanceof Position)) return false;
            Position p = (Position) o;
            return p.row == row && p.col == col;
        }
        @Override public int hashCode() { return row * 8 + col; }
        @Override public String toString() { return "" + (char) ('a' + col) + (8 - row); }
    }

    // ---------- Piece hierarchy ----------
    static abstract class Piece {
        Color color;
        Position position;
        Piece(Color color, Position position) { this.color = color; this.position = position; }

        // Pseudo-legal moves: respects board occupancy/own-piece blocking, but does NOT
        // check whether the move leaves the mover's own king in check - that is
        // ChessGame's job, one level up.
        abstract List<Position> getValidMoves(Board board);
        abstract char symbol();

        // Shared helper: walk a direction until off-board, own piece, or a capture.
        void slide(Board board, List<Position> out, int dr, int dc) {
            int r = position.row + dr, c = position.col + dc;
            while (true) {
                Position p = new Position(r, c);
                if (!p.inBounds()) break;
                Piece occupant = board.getPieceAt(p);
                if (occupant == null) { out.add(p); }
                else { if (occupant.color != color) out.add(p); break; }
                r += dr; c += dc;
            }
        }
    }

    static class Rook extends Piece {
        Rook(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) slide(board, moves, d[0], d[1]);
            return moves;
        }
        char symbol() { return color == Color.WHITE ? 'R' : 'r'; }
    }

    static class Bishop extends Piece {
        Bishop(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            for (int[] d : new int[][]{{1,1},{1,-1},{-1,1},{-1,-1}}) slide(board, moves, d[0], d[1]);
            return moves;
        }
        char symbol() { return color == Color.WHITE ? 'B' : 'b'; }
    }

    static class Queen extends Piece {
        Queen(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}})
                slide(board, moves, d[0], d[1]);
            return moves;
        }
        char symbol() { return color == Color.WHITE ? 'Q' : 'q'; }
    }

    static class Knight extends Piece {
        Knight(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            int[][] deltas = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
            for (int[] d : deltas) {
                Position p = new Position(position.row + d[0], position.col + d[1]);
                if (!p.inBounds()) continue;
                Piece occ = board.getPieceAt(p);
                if (occ == null || occ.color != color) moves.add(p);
            }
            return moves;
        }
        char symbol() { return color == Color.WHITE ? 'N' : 'n'; }
    }

    static class King extends Piece {
        King(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    Position p = new Position(position.row + dr, position.col + dc);
                    if (!p.inBounds()) continue;
                    Piece occ = board.getPieceAt(p);
                    if (occ == null || occ.color != color) moves.add(p);
                }
            }
            return moves; // castling intentionally omitted - out of scope for this exercise
        }
        char symbol() { return color == Color.WHITE ? 'K' : 'k'; }
    }

    static class Pawn extends Piece {
        Pawn(Color c, Position p) { super(c, p); }
        List<Position> getValidMoves(Board board) {
            List<Position> moves = new ArrayList<>();
            int dir = color == Color.WHITE ? -1 : 1;
            int startRow = color == Color.WHITE ? 6 : 1;

            Position oneStep = new Position(position.row + dir, position.col);
            if (oneStep.inBounds() && board.getPieceAt(oneStep) == null) {
                moves.add(oneStep);
                Position twoStep = new Position(position.row + 2 * dir, position.col);
                if (position.row == startRow && board.getPieceAt(twoStep) == null) moves.add(twoStep);
            }
            for (int dc : new int[]{-1, 1}) {
                Position diag = new Position(position.row + dir, position.col + dc);
                if (!diag.inBounds()) continue;
                Piece occ = board.getPieceAt(diag);
                if (occ != null && occ.color != color) moves.add(diag); // capture only diagonally
            }
            return moves; // en passant / promotion intentionally omitted
        }
        char symbol() { return color == Color.WHITE ? 'P' : 'p'; }
    }

    // ---------- Board ----------
    static class Board {
        private final Piece[][] grid = new Piece[8][8];

        Piece getPieceAt(Position p) { return p.inBounds() ? grid[p.row][p.col] : null; }

        void setPieceAt(Position p, Piece piece) {
            grid[p.row][p.col] = piece;
            if (piece != null) piece.position = p;
        }

        List<Piece> getAllPieces(Color color) {
            List<Piece> pieces = new ArrayList<>();
            for (Piece[] row : grid) for (Piece p : row) if (p != null && p.color == color) pieces.add(p);
            return pieces;
        }

        // Reuses each piece's own getValidMoves() - the same movement logic already
        // written for regular moves, not a second parallel "attack" implementation.
        boolean isSquareAttacked(Position square, Color byColor) {
            for (Piece piece : getAllPieces(byColor)) {
                if (piece.getValidMoves(this).contains(square)) return true;
            }
            return false;
        }

        void setupStandardPosition() {
            Color[] rows = {Color.BLACK, Color.WHITE};
            int[] backRanks = {0, 7};
            int[] pawnRanks = {1, 6};
            for (int i = 0; i < 2; i++) {
                Color color = rows[i];
                int back = backRanks[i];
                setPieceAt(new Position(back, 0), new Rook(color, null));
                setPieceAt(new Position(back, 1), new Knight(color, null));
                setPieceAt(new Position(back, 2), new Bishop(color, null));
                setPieceAt(new Position(back, 3), new Queen(color, null));
                setPieceAt(new Position(back, 4), new King(color, null));
                setPieceAt(new Position(back, 5), new Bishop(color, null));
                setPieceAt(new Position(back, 6), new Knight(color, null));
                setPieceAt(new Position(back, 7), new Rook(color, null));
                for (int c = 0; c < 8; c++) setPieceAt(new Position(pawnRanks[i], c), new Pawn(color, null));
            }
        }

        void print() {
            for (int r = 0; r < 8; r++) {
                StringBuilder sb = new StringBuilder();
                for (int c = 0; c < 8; c++) {
                    Piece p = grid[r][c];
                    sb.append(p == null ? '.' : p.symbol()).append(' ');
                }
                System.out.println(sb);
            }
        }
    }

    // ---------- Move (Command) ----------
    static class Move {
        final Position from, to;
        final Piece movedPiece;
        final Piece capturedPiece;
        String specialFlag = "NONE"; // extension point for castling/promotion, unused here

        Move(Position from, Position to, Piece movedPiece, Piece capturedPiece) {
            this.from = from; this.to = to; this.movedPiece = movedPiece; this.capturedPiece = capturedPiece;
        }

        void execute(Board board) {
            board.setPieceAt(to, movedPiece);
            board.setPieceAt(from, null);
        }

        // Restores both the moved piece's square AND the captured piece - this is what
        // makes undo a single call instead of manually diffing board state.
        void undo(Board board) {
            board.setPieceAt(from, movedPiece);
            board.setPieceAt(to, capturedPiece);
        }
    }

    // ---------- MoveHistory ----------
    static class MoveHistory {
        private final Deque<Move> stack = new ArrayDeque<>();
        void push(Move move) { stack.push(move); }
        Move popAndUndo(Board board) {
            if (stack.isEmpty()) return null;
            Move move = stack.pop();
            move.undo(board);
            return move;
        }
        boolean isEmpty() { return stack.isEmpty(); }
    }

    // ---------- ChessGame (facade) ----------
    static class ChessGame {
        final Board board = new Board();
        Color currentTurn = Color.WHITE;
        final MoveHistory history = new MoveHistory();

        ChessGame() { board.setupStandardPosition(); }

        Color opponent(Color c) { return c == Color.WHITE ? Color.BLACK : Color.WHITE; }

        Position findKing(Color color) {
            for (Piece p : board.getAllPieces(color)) if (p instanceof King) return p.position;
            throw new IllegalStateException("King missing for " + color);
        }

        boolean isInCheck(Color color) {
            return board.isSquareAttacked(findKing(color), opponent(color));
        }

        // Checkmate iff in check AND no legal move (for any of this color's pieces)
        // escapes check when simulated.
        boolean isCheckmate(Color color) {
            if (!isInCheck(color)) return false;
            return !hasAnyLegalMove(color);
        }

        boolean isStalemate(Color color) {
            return !isInCheck(color) && !hasAnyLegalMove(color);
        }

        private boolean hasAnyLegalMove(Color color) {
            for (Piece piece : new ArrayList<>(board.getAllPieces(color))) {
                for (Position dest : piece.getValidMoves(board)) {
                    Move trial = new Move(piece.position, dest, piece, board.getPieceAt(dest));
                    trial.execute(board);
                    boolean stillInCheck = isInCheck(color);
                    trial.undo(board);
                    if (!stillInCheck) return true;
                }
            }
            return false;
        }

        MoveResult makeMove(Position from, Position to) {
            Piece piece = board.getPieceAt(from);
            if (piece == null || piece.color != currentTurn) return MoveResult.REJECTED_ILLEGAL;
            if (!piece.getValidMoves(board).contains(to)) return MoveResult.REJECTED_ILLEGAL;

            Move move = new Move(from, to, piece, board.getPieceAt(to));
            move.execute(board); // simulate first
            if (isInCheck(currentTurn)) {
                move.undo(board); // illegal - leaves own king in check
                return MoveResult.REJECTED_SELF_CHECK;
            }
            history.push(move); // commit
            currentTurn = opponent(currentTurn);

            if (isCheckmate(currentTurn)) return MoveResult.CHECKMATE;
            if (isStalemate(currentTurn)) return MoveResult.STALEMATE;
            if (isInCheck(currentTurn)) return MoveResult.CHECK;
            return MoveResult.OK;
        }

        void undo() {
            if (history.isEmpty()) return;
            history.popAndUndo(board);
            currentTurn = opponent(currentTurn);
        }
    }

    // ---------- Demo ----------
    public static void main(String[] args) {
        ChessGame game = new ChessGame();
        game.board.print();

        // 1. e2-e4 (White pawn double step)
        System.out.println(game.makeMove(new Position(6, 4), new Position(4, 4)));
        // 2. e7-e5 (Black pawn double step)
        System.out.println(game.makeMove(new Position(1, 4), new Position(3, 4)));
        // 3. Queen out for White: d1-h5
        System.out.println(game.makeMove(new Position(7, 3), new Position(3, 7)));
        // Illegal: it's Black's turn now, but this tries to move a White pawn
        System.out.println(game.makeMove(new Position(6, 0), new Position(5, 0)));

        System.out.println("Is white in check? " + game.isInCheck(Color.WHITE));
        game.undo(); // undo the queen move
        game.board.print();
    }
}

// Chess Game - full LLD implementation (single-file demo).
// No "Concurrency" badge -> single-threaded, no mutexes needed.
//
// Design notes:
// - Piece uses plain subclassing (not Strategy): a piece's type and its movement rule
//   are the same fact and always change together, so Piece -> Rook/Bishop/... is the
//   honest simpler answer.
// - Move is a Command: it knows how to execute()/undo() itself (including restoring a
//   captured piece), so ChessGame::undo() is a one-line pop-and-undo off MoveHistory.
// - Board::isSquareAttacked() reuses each piece's own getValidMoves() rather than a
//   second parallel "attack" implementation.
#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <stdexcept>

using namespace std;

enum class Color { WHITE, BLACK };
enum class MoveResult { OK, CHECK, CHECKMATE, STALEMATE, REJECTED_ILLEGAL, REJECTED_SELF_CHECK };

// ---------- Position ----------
struct Position {
    int row, col;
    Position(int r = -1, int c = -1) : row(r), col(c) {}
    bool inBounds() const { return row >= 0 && row < 8 && col >= 0 && col < 8; }
    bool operator==(const Position& o) const { return row == o.row && col == o.col; }
};

static string toString(MoveResult r) {
    switch (r) {
        case MoveResult::OK: return "OK";
        case MoveResult::CHECK: return "CHECK";
        case MoveResult::CHECKMATE: return "CHECKMATE";
        case MoveResult::STALEMATE: return "STALEMATE";
        case MoveResult::REJECTED_ILLEGAL: return "REJECTED_ILLEGAL";
        case MoveResult::REJECTED_SELF_CHECK: return "REJECTED_SELF_CHECK";
    }
    return "?";
}

class Board;

// ---------- Piece hierarchy ----------
class Piece {
public:
    Color color;
    Position position;
    Piece(Color c, Position p) : color(c), position(p) {}
    virtual ~Piece() = default;
    // Pseudo-legal moves only; self-check filtering is ChessGame's job.
    virtual vector<Position> getValidMoves(Board& board) = 0;
    virtual char symbol() const = 0;

protected:
    void slide(Board& board, vector<Position>& out, int dr, int dc);
};

class Board {
    Piece* grid[8][8];
public:
    Board() { for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) grid[r][c] = nullptr; }

    Piece* getPieceAt(const Position& p) const { return p.inBounds() ? grid[p.row][p.col] : nullptr; }

    void setPieceAt(const Position& p, Piece* piece) {
        grid[p.row][p.col] = piece;
        if (piece) piece->position = p;
    }

    vector<Piece*> getAllPieces(Color color) const {
        vector<Piece*> pieces;
        for (int r = 0; r < 8; r++)
            for (int c = 0; c < 8; c++)
                if (grid[r][c] != nullptr && grid[r][c]->color == color) pieces.push_back(grid[r][c]);
        return pieces;
    }

    // Reuses each piece's own movement logic - same code path as regular moves.
    bool isSquareAttacked(const Position& square, Color byColor) {
        for (Piece* piece : getAllPieces(byColor)) {
            auto moves = piece->getValidMoves(*this);
            if (find(moves.begin(), moves.end(), square) != moves.end()) return true;
        }
        return false;
    }

    void print() const {
        for (int r = 0; r < 8; r++) {
            for (int c = 0; c < 8; c++) cout << (grid[r][c] ? grid[r][c]->symbol() : '.') << ' ';
            cout << "\n";
        }
    }
};

void Piece::slide(Board& board, vector<Position>& out, int dr, int dc) {
    int r = position.row + dr, c = position.col + dc;
    while (true) {
        Position p(r, c);
        if (!p.inBounds()) break;
        Piece* occupant = board.getPieceAt(p);
        if (occupant == nullptr) { out.push_back(p); }
        else { if (occupant->color != color) out.push_back(p); break; }
        r += dr; c += dc;
    }
}

class Rook : public Piece {
public:
    Rook(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : dirs) slide(board, moves, d[0], d[1]);
        return moves;
    }
    char symbol() const override { return color == Color::WHITE ? 'R' : 'r'; }
};

class Bishop : public Piece {
public:
    Bishop(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        int dirs[4][2] = {{1,1},{1,-1},{-1,1},{-1,-1}};
        for (auto& d : dirs) slide(board, moves, d[0], d[1]);
        return moves;
    }
    char symbol() const override { return color == Color::WHITE ? 'B' : 'b'; }
};

class Queen : public Piece {
public:
    Queen(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        int dirs[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        for (auto& d : dirs) slide(board, moves, d[0], d[1]);
        return moves;
    }
    char symbol() const override { return color == Color::WHITE ? 'Q' : 'q'; }
};

class Knight : public Piece {
public:
    Knight(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        int deltas[8][2] = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
        for (auto& d : deltas) {
            Position p(position.row + d[0], position.col + d[1]);
            if (!p.inBounds()) continue;
            Piece* occ = board.getPieceAt(p);
            if (occ == nullptr || occ->color != color) moves.push_back(p);
        }
        return moves;
    }
    char symbol() const override { return color == Color::WHITE ? 'N' : 'n'; }
};

class King : public Piece {
public:
    King(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        for (int dr = -1; dr <= 1; dr++)
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                Position p(position.row + dr, position.col + dc);
                if (!p.inBounds()) continue;
                Piece* occ = board.getPieceAt(p);
                if (occ == nullptr || occ->color != color) moves.push_back(p);
            }
        return moves; // castling intentionally omitted
    }
    char symbol() const override { return color == Color::WHITE ? 'K' : 'k'; }
};

class Pawn : public Piece {
public:
    Pawn(Color c, Position p) : Piece(c, p) {}
    vector<Position> getValidMoves(Board& board) override {
        vector<Position> moves;
        int dir = color == Color::WHITE ? -1 : 1;
        int startRow = color == Color::WHITE ? 6 : 1;

        Position oneStep(position.row + dir, position.col);
        if (oneStep.inBounds() && board.getPieceAt(oneStep) == nullptr) {
            moves.push_back(oneStep);
            Position twoStep(position.row + 2 * dir, position.col);
            if (position.row == startRow && board.getPieceAt(twoStep) == nullptr) moves.push_back(twoStep);
        }
        for (int dc : {-1, 1}) {
            Position diag(position.row + dir, position.col + dc);
            if (!diag.inBounds()) continue;
            Piece* occ = board.getPieceAt(diag);
            if (occ != nullptr && occ->color != color) moves.push_back(diag);
        }
        return moves; // en passant / promotion intentionally omitted
    }
    char symbol() const override { return color == Color::WHITE ? 'P' : 'p'; }
};

// ---------- Move (Command) ----------
class Move {
public:
    Position from, to;
    Piece* movedPiece;
    Piece* capturedPiece;
    string specialFlag = "NONE"; // extension point for castling/promotion, unused here

    Move(Position f, Position t, Piece* mp, Piece* cp) : from(f), to(t), movedPiece(mp), capturedPiece(cp) {}

    void execute(Board& board) {
        board.setPieceAt(to, movedPiece);
        board.setPieceAt(from, nullptr);
    }

    // Restores both the moved piece's square AND the captured piece.
    void undo(Board& board) {
        board.setPieceAt(from, movedPiece);
        board.setPieceAt(to, capturedPiece);
    }
};

// ---------- MoveHistory ----------
class MoveHistory {
    vector<Move> stack;
public:
    void push(const Move& move) { stack.push_back(move); }
    bool isEmpty() const { return stack.empty(); }
    void popAndUndo(Board& board) {
        if (stack.empty()) return;
        Move move = stack.back();
        stack.pop_back();
        move.undo(board);
    }
};

// ---------- ChessGame (facade) ----------
class ChessGame {
public:
    Board board;
    Color currentTurn = Color::WHITE;
    MoveHistory history;
    vector<unique_ptr<Piece>> pieces; // owns all piece lifetimes

    ChessGame() { setupStandardPosition(); }

    static Color opponent(Color c) { return c == Color::WHITE ? Color::BLACK : Color::WHITE; }

    Position findKing(Color color) {
        for (Piece* p : board.getAllPieces(color))
            if (dynamic_cast<King*>(p) != nullptr) return p->position;
        throw runtime_error("King missing");
    }

    bool isInCheck(Color color) { return board.isSquareAttacked(findKing(color), opponent(color)); }

    bool isCheckmate(Color color) {
        if (!isInCheck(color)) return false;
        return !hasAnyLegalMove(color);
    }

    bool isStalemate(Color color) { return !isInCheck(color) && !hasAnyLegalMove(color); }

    MoveResult makeMove(Position from, Position to) {
        Piece* piece = board.getPieceAt(from);
        if (piece == nullptr || piece->color != currentTurn) return MoveResult::REJECTED_ILLEGAL;
        auto validMoves = piece->getValidMoves(board);
        if (find(validMoves.begin(), validMoves.end(), to) == validMoves.end()) return MoveResult::REJECTED_ILLEGAL;

        Move move(from, to, piece, board.getPieceAt(to));
        move.execute(board); // simulate first
        if (isInCheck(currentTurn)) {
            move.undo(board); // illegal - leaves own king in check
            return MoveResult::REJECTED_SELF_CHECK;
        }
        history.push(move); // commit
        currentTurn = opponent(currentTurn);

        if (isCheckmate(currentTurn)) return MoveResult::CHECKMATE;
        if (isStalemate(currentTurn)) return MoveResult::STALEMATE;
        if (isInCheck(currentTurn)) return MoveResult::CHECK;
        return MoveResult::OK;
    }

    void undo() {
        if (history.isEmpty()) return;
        history.popAndUndo(board);
        currentTurn = opponent(currentTurn);
    }

private:
    bool hasAnyLegalMove(Color color) {
        for (Piece* piece : board.getAllPieces(color)) {
            for (Position dest : piece->getValidMoves(board)) {
                Move trial(piece->position, dest, piece, board.getPieceAt(dest));
                trial.execute(board);
                bool stillInCheck = isInCheck(color);
                trial.undo(board);
                if (!stillInCheck) return true;
            }
        }
        return false;
    }

    template <typename T>
    Piece* make(Color c, Position p) {
        pieces.push_back(make_unique<T>(c, p));
        return pieces.back().get();
    }

    void setupStandardPosition() {
        Color rows[2] = {Color::BLACK, Color::WHITE};
        int backRanks[2] = {0, 7};
        int pawnRanks[2] = {1, 6};
        for (int i = 0; i < 2; i++) {
            Color color = rows[i];
            int back = backRanks[i];
            board.setPieceAt(Position(back, 0), make<Rook>(color, Position(back, 0)));
            board.setPieceAt(Position(back, 1), make<Knight>(color, Position(back, 1)));
            board.setPieceAt(Position(back, 2), make<Bishop>(color, Position(back, 2)));
            board.setPieceAt(Position(back, 3), make<Queen>(color, Position(back, 3)));
            board.setPieceAt(Position(back, 4), make<King>(color, Position(back, 4)));
            board.setPieceAt(Position(back, 5), make<Bishop>(color, Position(back, 5)));
            board.setPieceAt(Position(back, 6), make<Knight>(color, Position(back, 6)));
            board.setPieceAt(Position(back, 7), make<Rook>(color, Position(back, 7)));
            for (int c = 0; c < 8; c++)
                board.setPieceAt(Position(pawnRanks[i], c), make<Pawn>(color, Position(pawnRanks[i], c)));
        }
    }
};

// ---------- Demo ----------
int main() {
    ChessGame game;
    game.board.print();

    cout << toString(game.makeMove(Position(6, 4), Position(4, 4))) << "\n"; // e2-e4
    cout << toString(game.makeMove(Position(1, 4), Position(3, 4))) << "\n"; // e7-e5
    cout << toString(game.makeMove(Position(7, 3), Position(3, 7))) << "\n"; // Qd1-h5
    // Illegal: it's Black's turn now, but this tries to move a White pawn
    cout << toString(game.makeMove(Position(6, 0), Position(5, 0))) << "\n";

    cout << "Is white in check? " << (game.isInCheck(Color::WHITE) ? "true" : "false") << "\n";
    game.undo(); // undo the queen move
    game.board.print();
    return 0;
}

// Chess Game - full LLD implementation (single-file demo, Node/CommonJS).
// No "Concurrency" badge -> single-threaded, no locking primitives needed.
//
// Design notes:
// - Piece uses plain subclassing (not Strategy): a piece's type and its movement rule
//   are the same fact and always change together, so Piece -> Rook/Bishop/... is the
//   honest simpler answer.
// - Move is a Command: it knows how to execute()/undo() itself (including restoring a
//   captured piece), so ChessGame.undo() is a one-line pop-and-undo off MoveHistory.
// - Board.isSquareAttacked() reuses each piece's own getValidMoves() rather than a
//   second parallel "attack" implementation.

const Color = Object.freeze({ WHITE: 'WHITE', BLACK: 'BLACK' });
const MoveResult = Object.freeze({
  OK: 'OK', CHECK: 'CHECK', CHECKMATE: 'CHECKMATE', STALEMATE: 'STALEMATE',
  REJECTED_ILLEGAL: 'REJECTED_ILLEGAL', REJECTED_SELF_CHECK: 'REJECTED_SELF_CHECK',
});

class Position {
  constructor(row, col) { this.row = row; this.col = col; }
  inBounds() { return this.row >= 0 && this.row < 8 && this.col >= 0 && this.col < 8; }
  equals(other) { return other != null && this.row === other.row && this.col === other.col; }
}

function containsPosition(list, pos) { return list.some((p) => p.equals(pos)); }

// ---------- Piece hierarchy ----------
class Piece {
  constructor(color, position) {
    if (new.target === Piece) throw new Error('Piece is abstract');
    this.color = color;
    this.position = position;
  }
  // Pseudo-legal moves only; self-check filtering happens one level up, in ChessGame.
  getValidMoves(_board) { throw new Error('not implemented'); }
  symbol() { throw new Error('not implemented'); }

  slide(board, out, dr, dc) {
    let r = this.position.row + dr;
    let c = this.position.col + dc;
    while (true) {
      const p = new Position(r, c);
      if (!p.inBounds()) break;
      const occupant = board.getPieceAt(p);
      if (occupant === null) { out.push(p); }
      else { if (occupant.color !== this.color) out.push(p); break; }
      r += dr; c += dc;
    }
  }
}

class Rook extends Piece {
  getValidMoves(board) {
    const moves = [];
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) this.slide(board, moves, dr, dc);
    return moves;
  }
  symbol() { return this.color === Color.WHITE ? 'R' : 'r'; }
}

class Bishop extends Piece {
  getValidMoves(board) {
    const moves = [];
    for (const [dr, dc] of [[1, 1], [1, -1], [-1, 1], [-1, -1]]) this.slide(board, moves, dr, dc);
    return moves;
  }
  symbol() { return this.color === Color.WHITE ? 'B' : 'b'; }
}

class Queen extends Piece {
  getValidMoves(board) {
    const moves = [];
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]) {
      this.slide(board, moves, dr, dc);
    }
    return moves;
  }
  symbol() { return this.color === Color.WHITE ? 'Q' : 'q'; }
}

class Knight extends Piece {
  getValidMoves(board) {
    const moves = [];
    const deltas = [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]];
    for (const [dr, dc] of deltas) {
      const p = new Position(this.position.row + dr, this.position.col + dc);
      if (!p.inBounds()) continue;
      const occ = board.getPieceAt(p);
      if (occ === null || occ.color !== this.color) moves.push(p);
    }
    return moves;
  }
  symbol() { return this.color === Color.WHITE ? 'N' : 'n'; }
}

class King extends Piece {
  getValidMoves(board) {
    const moves = [];
    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        if (dr === 0 && dc === 0) continue;
        const p = new Position(this.position.row + dr, this.position.col + dc);
        if (!p.inBounds()) continue;
        const occ = board.getPieceAt(p);
        if (occ === null || occ.color !== this.color) moves.push(p);
      }
    }
    return moves; // castling intentionally omitted
  }
  symbol() { return this.color === Color.WHITE ? 'K' : 'k'; }
}

class Pawn extends Piece {
  getValidMoves(board) {
    const moves = [];
    const dir = this.color === Color.WHITE ? -1 : 1;
    const startRow = this.color === Color.WHITE ? 6 : 1;

    const oneStep = new Position(this.position.row + dir, this.position.col);
    if (oneStep.inBounds() && board.getPieceAt(oneStep) === null) {
      moves.push(oneStep);
      const twoStep = new Position(this.position.row + 2 * dir, this.position.col);
      if (this.position.row === startRow && board.getPieceAt(twoStep) === null) moves.push(twoStep);
    }
    for (const dc of [-1, 1]) {
      const diag = new Position(this.position.row + dir, this.position.col + dc);
      if (!diag.inBounds()) continue;
      const occ = board.getPieceAt(diag);
      if (occ !== null && occ.color !== this.color) moves.push(diag); // capture only diagonally
    }
    return moves; // en passant / promotion intentionally omitted
  }
  symbol() { return this.color === Color.WHITE ? 'P' : 'p'; }
}

// ---------- Board ----------
class Board {
  constructor() {
    this.grid = Array.from({ length: 8 }, () => Array(8).fill(null));
  }

  getPieceAt(p) { return p.inBounds() ? this.grid[p.row][p.col] : null; }

  setPieceAt(p, piece) {
    this.grid[p.row][p.col] = piece;
    if (piece) piece.position = p;
  }

  getAllPieces(color) {
    const pieces = [];
    for (const row of this.grid) for (const p of row) if (p !== null && p.color === color) pieces.push(p);
    return pieces;
  }

  // Reuses each piece's own movement logic - the same code path as regular moves.
  isSquareAttacked(square, byColor) {
    for (const piece of this.getAllPieces(byColor)) {
      if (containsPosition(piece.getValidMoves(this), square)) return true;
    }
    return false;
  }

  setupStandardPosition() {
    const rows = [Color.BLACK, Color.WHITE];
    const backRanks = [0, 7];
    const pawnRanks = [1, 6];
    for (let i = 0; i < 2; i++) {
      const color = rows[i];
      const back = backRanks[i];
      const order = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook];
      order.forEach((Ctor, col) => this.setPieceAt(new Position(back, col), new Ctor(color, new Position(back, col))));
      for (let c = 0; c < 8; c++) {
        this.setPieceAt(new Position(pawnRanks[i], c), new Pawn(color, new Position(pawnRanks[i], c)));
      }
    }
  }

  print() {
    for (let r = 0; r < 8; r++) {
      console.log(this.grid[r].map((p) => (p ? p.symbol() : '.')).join(' '));
    }
  }
}

// ---------- Move (Command) ----------
class Move {
  constructor(from, to, movedPiece, capturedPiece) {
    this.from = from;
    this.to = to;
    this.movedPiece = movedPiece;
    this.capturedPiece = capturedPiece;
    this.specialFlag = 'NONE'; // extension point for castling/promotion, unused here
  }

  execute(board) {
    board.setPieceAt(this.to, this.movedPiece);
    board.setPieceAt(this.from, null);
  }

  // Restores both the moved piece's square AND the captured piece.
  undo(board) {
    board.setPieceAt(this.from, this.movedPiece);
    board.setPieceAt(this.to, this.capturedPiece);
  }
}

// ---------- MoveHistory ----------
class MoveHistory {
  constructor() { this.stack = []; }
  push(move) { this.stack.push(move); }
  isEmpty() { return this.stack.length === 0; }
  popAndUndo(board) {
    if (this.stack.length === 0) return null;
    const move = this.stack.pop();
    move.undo(board);
    return move;
  }
}

// ---------- ChessGame (facade) ----------
class ChessGame {
  constructor() {
    this.board = new Board();
    this.currentTurn = Color.WHITE;
    this.history = new MoveHistory();
    this.board.setupStandardPosition();
  }

  static opponent(c) { return c === Color.WHITE ? Color.BLACK : Color.WHITE; }

  findKing(color) {
    const king = this.board.getAllPieces(color).find((p) => p instanceof King);
    if (!king) throw new Error(`King missing for ${color}`);
    return king.position;
  }

  isInCheck(color) {
    return this.board.isSquareAttacked(this.findKing(color), ChessGame.opponent(color));
  }

  isCheckmate(color) {
    if (!this.isInCheck(color)) return false;
    return !this.hasAnyLegalMove(color);
  }

  isStalemate(color) {
    return !this.isInCheck(color) && !this.hasAnyLegalMove(color);
  }

  hasAnyLegalMove(color) {
    for (const piece of [...this.board.getAllPieces(color)]) {
      for (const dest of piece.getValidMoves(this.board)) {
        const trial = new Move(piece.position, dest, piece, this.board.getPieceAt(dest));
        trial.execute(this.board);
        const stillInCheck = this.isInCheck(color);
        trial.undo(this.board);
        if (!stillInCheck) return true;
      }
    }
    return false;
  }

  makeMove(from, to) {
    const piece = this.board.getPieceAt(from);
    if (piece === null || piece.color !== this.currentTurn) return MoveResult.REJECTED_ILLEGAL;
    if (!containsPosition(piece.getValidMoves(this.board), to)) return MoveResult.REJECTED_ILLEGAL;

    const move = new Move(from, to, piece, this.board.getPieceAt(to));
    move.execute(this.board); // simulate first
    if (this.isInCheck(this.currentTurn)) {
      move.undo(this.board); // illegal - leaves own king in check
      return MoveResult.REJECTED_SELF_CHECK;
    }
    this.history.push(move); // commit
    this.currentTurn = ChessGame.opponent(this.currentTurn);

    if (this.isCheckmate(this.currentTurn)) return MoveResult.CHECKMATE;
    if (this.isStalemate(this.currentTurn)) return MoveResult.STALEMATE;
    if (this.isInCheck(this.currentTurn)) return MoveResult.CHECK;
    return MoveResult.OK;
  }

  undo() {
    if (this.history.isEmpty()) return;
    this.history.popAndUndo(this.board);
    this.currentTurn = ChessGame.opponent(this.currentTurn);
  }
}

// ---------- Demo ----------
function main() {
  const game = new ChessGame();
  game.board.print();

  console.log(game.makeMove(new Position(6, 4), new Position(4, 4))); // e2-e4
  console.log(game.makeMove(new Position(1, 4), new Position(3, 4))); // e7-e5
  console.log(game.makeMove(new Position(7, 3), new Position(3, 7))); // Qd1-h5
  // Illegal: it's Black's turn now, but this tries to move a White pawn
  console.log(game.makeMove(new Position(6, 0), new Position(5, 0)));

  console.log('Is white in check?', game.isInCheck(Color.WHITE));
  game.undo(); // undo the queen move
  game.board.print();
}

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

module.exports = {
  Color, MoveResult, Position, Piece, Rook, Bishop, Queen, Knight, King, Pawn, Board, Move, MoveHistory, ChessGame,
};

// Chess Game - full LLD implementation (single-file demo).
// No "Concurrency" badge -> single-threaded, no locking primitives needed.
//
// Design notes:
// - Piece uses plain subclassing (not Strategy): a piece's type and its movement rule
//   are the same fact and always change together, so Piece -> Rook/Bishop/... is the
//   honest simpler answer.
// - Move is a Command: it knows how to execute()/undo() itself (including restoring a
//   captured piece), so ChessGame.undo() is a one-line pop-and-undo off MoveHistory.
// - Board.isSquareAttacked() reuses each piece's own getValidMoves() rather than a
//   second parallel "attack" implementation.

enum Color { WHITE = 'WHITE', BLACK = 'BLACK' }

enum MoveResult {
  OK = 'OK', CHECK = 'CHECK', CHECKMATE = 'CHECKMATE', STALEMATE = 'STALEMATE',
  REJECTED_ILLEGAL = 'REJECTED_ILLEGAL', REJECTED_SELF_CHECK = 'REJECTED_SELF_CHECK',
}

class Position {
  constructor(public row: number, public col: number) {}
  inBounds(): boolean { return this.row >= 0 && this.row < 8 && this.col >= 0 && this.col < 8; }
  equals(other: Position | null): boolean { return other != null && this.row === other.row && this.col === other.col; }
}

function containsPosition(list: Position[], pos: Position): boolean {
  return list.some((p) => p.equals(pos));
}

// ---------- Piece hierarchy ----------
abstract class Piece {
  color: Color;
  position: Position;
  constructor(color: Color, position: Position) { this.color = color; this.position = position; }

  // Pseudo-legal moves only; self-check filtering happens one level up, in ChessGame.
  abstract getValidMoves(board: Board): Position[];
  abstract symbol(): string;

  protected slide(board: Board, out: Position[], dr: number, dc: number): void {
    let r = this.position.row + dr;
    let c = this.position.col + dc;
    while (true) {
      const p = new Position(r, c);
      if (!p.inBounds()) break;
      const occupant = board.getPieceAt(p);
      if (occupant === null) { out.push(p); }
      else { if (occupant.color !== this.color) out.push(p); break; }
      r += dr; c += dc;
    }
  }
}

class Rook extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) this.slide(board, moves, dr, dc);
    return moves;
  }
  symbol(): string { return this.color === Color.WHITE ? 'R' : 'r'; }
}

class Bishop extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    for (const [dr, dc] of [[1, 1], [1, -1], [-1, 1], [-1, -1]]) this.slide(board, moves, dr, dc);
    return moves;
  }
  symbol(): string { return this.color === Color.WHITE ? 'B' : 'b'; }
}

class Queen extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]) {
      this.slide(board, moves, dr, dc);
    }
    return moves;
  }
  symbol(): string { return this.color === Color.WHITE ? 'Q' : 'q'; }
}

class Knight extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    const deltas = [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]];
    for (const [dr, dc] of deltas) {
      const p = new Position(this.position.row + dr, this.position.col + dc);
      if (!p.inBounds()) continue;
      const occ = board.getPieceAt(p);
      if (occ === null || occ.color !== this.color) moves.push(p);
    }
    return moves;
  }
  symbol(): string { return this.color === Color.WHITE ? 'N' : 'n'; }
}

class King extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        if (dr === 0 && dc === 0) continue;
        const p = new Position(this.position.row + dr, this.position.col + dc);
        if (!p.inBounds()) continue;
        const occ = board.getPieceAt(p);
        if (occ === null || occ.color !== this.color) moves.push(p);
      }
    }
    return moves; // castling intentionally omitted
  }
  symbol(): string { return this.color === Color.WHITE ? 'K' : 'k'; }
}

class Pawn extends Piece {
  getValidMoves(board: Board): Position[] {
    const moves: Position[] = [];
    const dir = this.color === Color.WHITE ? -1 : 1;
    const startRow = this.color === Color.WHITE ? 6 : 1;

    const oneStep = new Position(this.position.row + dir, this.position.col);
    if (oneStep.inBounds() && board.getPieceAt(oneStep) === null) {
      moves.push(oneStep);
      const twoStep = new Position(this.position.row + 2 * dir, this.position.col);
      if (this.position.row === startRow && board.getPieceAt(twoStep) === null) moves.push(twoStep);
    }
    for (const dc of [-1, 1]) {
      const diag = new Position(this.position.row + dir, this.position.col + dc);
      if (!diag.inBounds()) continue;
      const occ = board.getPieceAt(diag);
      if (occ !== null && occ.color !== this.color) moves.push(diag); // capture only diagonally
    }
    return moves; // en passant / promotion intentionally omitted
  }
  symbol(): string { return this.color === Color.WHITE ? 'P' : 'p'; }
}

// ---------- Board ----------
class Board {
  private grid: (Piece | null)[][] = Array.from({ length: 8 }, () => Array(8).fill(null));

  getPieceAt(p: Position): Piece | null { return p.inBounds() ? this.grid[p.row][p.col] : null; }

  setPieceAt(p: Position, piece: Piece | null): void {
    this.grid[p.row][p.col] = piece;
    if (piece) piece.position = p;
  }

  getAllPieces(color: Color): Piece[] {
    const pieces: Piece[] = [];
    for (const row of this.grid) for (const p of row) if (p !== null && p.color === color) pieces.push(p);
    return pieces;
  }

  // Reuses each piece's own movement logic - the same code path as regular moves.
  isSquareAttacked(square: Position, byColor: Color): boolean {
    for (const piece of this.getAllPieces(byColor)) {
      if (containsPosition(piece.getValidMoves(this), square)) return true;
    }
    return false;
  }

  setupStandardPosition(): void {
    const rows = [Color.BLACK, Color.WHITE];
    const backRanks = [0, 7];
    const pawnRanks = [1, 6];
    for (let i = 0; i < 2; i++) {
      const color = rows[i];
      const back = backRanks[i];
      const order: Array<new (c: Color, p: Position) => Piece> = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook];
      order.forEach((Ctor, col) => this.setPieceAt(new Position(back, col), new Ctor(color, new Position(back, col))));
      for (let c = 0; c < 8; c++) {
        this.setPieceAt(new Position(pawnRanks[i], c), new Pawn(color, new Position(pawnRanks[i], c)));
      }
    }
  }

  print(): void {
    for (let r = 0; r < 8; r++) {
      console.log(this.grid[r].map((p) => (p ? p.symbol() : '.')).join(' '));
    }
  }
}

// ---------- Move (Command) ----------
class Move {
  specialFlag = 'NONE'; // extension point for castling/promotion, unused here
  constructor(
    public from: Position,
    public to: Position,
    public movedPiece: Piece,
    public capturedPiece: Piece | null,
  ) {}

  execute(board: Board): void {
    board.setPieceAt(this.to, this.movedPiece);
    board.setPieceAt(this.from, null);
  }

  // Restores both the moved piece's square AND the captured piece.
  undo(board: Board): void {
    board.setPieceAt(this.from, this.movedPiece);
    board.setPieceAt(this.to, this.capturedPiece);
  }
}

// ---------- MoveHistory ----------
class MoveHistory {
  private stack: Move[] = [];
  push(move: Move): void { this.stack.push(move); }
  isEmpty(): boolean { return this.stack.length === 0; }
  popAndUndo(board: Board): Move | null {
    const move = this.stack.pop();
    if (!move) return null;
    move.undo(board);
    return move;
  }
}

// ---------- ChessGame (facade) ----------
class ChessGame {
  board = new Board();
  currentTurn: Color = Color.WHITE;
  history = new MoveHistory();

  constructor() { this.board.setupStandardPosition(); }

  static opponent(c: Color): Color { return c === Color.WHITE ? Color.BLACK : Color.WHITE; }

  findKing(color: Color): Position {
    const king = this.board.getAllPieces(color).find((p) => p instanceof King);
    if (!king) throw new Error(`King missing for ${color}`);
    return king.position;
  }

  isInCheck(color: Color): boolean {
    return this.board.isSquareAttacked(this.findKing(color), ChessGame.opponent(color));
  }

  isCheckmate(color: Color): boolean {
    if (!this.isInCheck(color)) return false;
    return !this.hasAnyLegalMove(color);
  }

  isStalemate(color: Color): boolean {
    return !this.isInCheck(color) && !this.hasAnyLegalMove(color);
  }

  private hasAnyLegalMove(color: Color): boolean {
    for (const piece of [...this.board.getAllPieces(color)]) {
      for (const dest of piece.getValidMoves(this.board)) {
        const trial = new Move(piece.position, dest, piece, this.board.getPieceAt(dest));
        trial.execute(this.board);
        const stillInCheck = this.isInCheck(color);
        trial.undo(this.board);
        if (!stillInCheck) return true;
      }
    }
    return false;
  }

  makeMove(from: Position, to: Position): MoveResult {
    const piece = this.board.getPieceAt(from);
    if (piece === null || piece.color !== this.currentTurn) return MoveResult.REJECTED_ILLEGAL;
    if (!containsPosition(piece.getValidMoves(this.board), to)) return MoveResult.REJECTED_ILLEGAL;

    const move = new Move(from, to, piece, this.board.getPieceAt(to));
    move.execute(this.board); // simulate first
    if (this.isInCheck(this.currentTurn)) {
      move.undo(this.board); // illegal - leaves own king in check
      return MoveResult.REJECTED_SELF_CHECK;
    }
    this.history.push(move); // commit
    this.currentTurn = ChessGame.opponent(this.currentTurn);

    if (this.isCheckmate(this.currentTurn)) return MoveResult.CHECKMATE;
    if (this.isStalemate(this.currentTurn)) return MoveResult.STALEMATE;
    if (this.isInCheck(this.currentTurn)) return MoveResult.CHECK;
    return MoveResult.OK;
  }

  undo(): void {
    if (this.history.isEmpty()) return;
    this.history.popAndUndo(this.board);
    this.currentTurn = ChessGame.opponent(this.currentTurn);
  }
}

// ---------- Demo ----------
function main(): void {
  const game = new ChessGame();
  game.board.print();

  console.log(game.makeMove(new Position(6, 4), new Position(4, 4))); // e2-e4
  console.log(game.makeMove(new Position(1, 4), new Position(3, 4))); // e7-e5
  console.log(game.makeMove(new Position(7, 3), new Position(3, 7))); // Qd1-h5
  // Illegal: it's Black's turn now, but this tries to move a White pawn
  console.log(game.makeMove(new Position(6, 0), new Position(5, 0)));

  console.log('Is white in check?', game.isInCheck(Color.WHITE));
  game.undo(); // undo the queen move
  game.board.print();
}

main();

export {
  Color, MoveResult, Position, Piece, Rook, Bishop, Queen, Knight, King, Pawn, Board, Move, MoveHistory, ChessGame,
};

← 12. Tic-Tac-Toe / Board Game Engine 14. ATM Machine →