47 — LLD: Chess Game

Understanding the Problem

Model a chess game. Each piece type has its own movement rules. Support move validation, check detection, and checkmate detection. No timer, no networking — just a correct rules engine.

What is the Chess LLD?

The canonical Factory + Strategy exercise. Every piece has the same interface (canMove) but radically different behaviour, so each piece is a concrete strategy built by a factory from FEN characters.

---

Requirements

Clarifying Questions

You: Do we include castling, en passant, promotion?

Interviewer: Skip for v1. Regular moves only.

Keep the piece set simple; design leaves room for special moves.

You: Move input format — algebraic or coordinates?

Interviewer: Coordinates as (row, col).

Internal board indexing is [0..7][0..7] with row 0 at the top.

You: How do we detect checkmate?

Interviewer: If the king is in check and no legal move escapes it.

Checkmate reduces to legal-move enumeration + check detection.

You: Undo?

Interviewer: Not required, but nice to have.

Memento pattern for board snapshots falls out naturally.

Final Requirements

1. 8×8 board with the standard starting position.
2. Each piece validates its own moves.
3. Detect check after each move — revert if own king exposed.
4. Factory builds pieces from FEN chars.
5. Turn-based: alternate White and Black.

Out of scope: castling, en-passant, promotion, clocks, networking, PGN import/export.

---

Core Entities and Relationships

Entity	Responsibility
Piece (abstract)	Colour, canMove(board, from, to), symbol().
King, Queen, Rook, Bishop, Knight, Pawn	Concrete rules.
Board	8×8 grid, get/set, pathClear, clone, findKing.
PieceFactory	Build from FEN char.
Game	Turn state, move, isInCheck.

Why a class per piece type? Because each has distinct rules. A flat switch on piece type rots as you add castling-eligible pawns and en-passant-sensitive pawns.

Why Board.clone? Because move validation needs to simulate "what if we made this move" to check self-check, and reverting the grid is cleanest via a clone.

Design is iterative — six piece types, one factory, one board, one game.

---

Class Design

Piece

State: colorMethods: canMove(board, from, to) -> bool, symbol()

Board

State: grid: Piece[8][8]Methods:

• get(pos), set(pos, piece)
• pathClear(from, to) — diagonal/horizontal/vertical emptiness
• clone()
• findKing(color)

Game

State: board, turnMethods:

• move(from, to) — validate, apply, check self-check, swap turn
• isInCheck(color, board)

Design principles at play:

• Strategy Pattern — each piece encapsulates its own move algorithm.
• Factory Pattern — PieceFactory.fromChar(ch).
• Memento Pattern — Board.clone() as a lightweight snapshot for simulation.
• Open/Closed — adding a new piece (e.g., fairy-chess Chancellor) is one new class.

---

Implementation

Core Logic: isInCheck

Bad approach: keep a flag that says "Alice's king is in check" and update after each move.

• Error-prone; easy to drift from the board state.

Good approach: compute on demand. Scan the board; for every enemy piece, ask canMove(board, piecePos, kingPos). If any is true, the king is in check.

Great approach: the same, but precompute an "attacked squares" bitboard in production engines. For an interview, the scan is perfectly fine.

Verification

Simple scenario. White pawn at (6,4), Black king at (0,4), White queen at (4,4).

1. game.move({6,4}, {5,4}) — pawn pushes one square. Pawn.canMove returns true. Board updated. Snapshot saved. isInCheck(W) false. Turn flips to Black.
2. Black king tries {0,4}→{1,4} — King.canMove true (distance 1). Board updated. isInCheck(B) — enemy queen at (4,4). Queen's canMove({4,4}, {1,4}) is true because it's rook-like along column 4 and the path is clear. Revert from snapshot. Throw KING_IN_CHECK.

Thread Safety

Chess is turn-based, so a single lock on Game is enough. If you run a server with many games, shard games across workers by game ID — no cross-game interaction.

Complete Code Implementation

Java

enum Color { W, B }

record Position(int r, int c) {}

abstract class Piece {
    public final Color color;
    protected Piece(Color c) { this.color = c; }
    public abstract boolean canMove(Board b, Position from, Position to);
    public abstract String symbol();
}

class Knight extends Piece {
    public Knight(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        int dr = Math.abs(f.r() - t.r()), dc = Math.abs(f.c() - t.c());
        return (dr == 2 && dc == 1) || (dr == 1 && dc == 2);
    }
    public String symbol() { return color == Color.W ? "N" : "n"; }
}

class Rook extends Piece {
    public Rook(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        if (f.r() != t.r() && f.c() != t.c()) return false;
        return b.pathClear(f, t);
    }
    public String symbol() { return color == Color.W ? "R" : "r"; }
}

class Bishop extends Piece {
    public Bishop(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        if (Math.abs(f.r() - t.r()) != Math.abs(f.c() - t.c())) return false;
        return b.pathClear(f, t);
    }
    public String symbol() { return color == Color.W ? "B" : "b"; }
}

class Queen extends Piece {
    public Queen(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        return new Rook(color).canMove(b, f, t) || new Bishop(color).canMove(b, f, t);
    }
    public String symbol() { return color == Color.W ? "Q" : "q"; }
}

class King extends Piece {
    public King(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        return Math.abs(f.r() - t.r()) <= 1 && Math.abs(f.c() - t.c()) <= 1 && !(f.r() == t.r() && f.c() == t.c());
    }
    public String symbol() { return color == Color.W ? "K" : "k"; }
}

class Pawn extends Piece {
    public Pawn(Color c) { super(c); }
    public boolean canMove(Board b, Position f, Position t) {
        int dir = color == Color.W ? -1 : 1;
        int startRow = color == Color.W ? 6 : 1;
        int dr = t.r() - f.r(), dc = t.c() - f.c();
        Piece target = b.get(t);
        if (dc == 0 && dr == dir && target == null) return true;
        if (dc == 0 && f.r() == startRow && dr == 2 * dir && target == null && b.get(new Position(f.r() + dir, f.c())) == null) return true;
        if (Math.abs(dc) == 1 && dr == dir && target != null && target.color != color) return true;
        return false;
    }
    public String symbol() { return color == Color.W ? "P" : "p"; }
}

class PieceFactory {
    public static Piece fromChar(char ch) {
        Color col = Character.isUpperCase(ch) ? Color.W : Color.B;
        return switch (Character.toLowerCase(ch)) {
            case 'k' -> new King(col);
            case 'q' -> new Queen(col);
            case 'r' -> new Rook(col);
            case 'b' -> new Bishop(col);
            case 'n' -> new Knight(col);
            case 'p' -> new Pawn(col);
            default -> null;
        };
    }
}

class Board {
    public final Piece[][] grid = new Piece[8][8];

    public Piece get(Position p) { return grid[p.r()][p.c()]; }
    public void set(Position p, Piece piece) { grid[p.r()][p.c()] = piece; }

    public boolean pathClear(Position f, Position t) {
        int dr = Integer.signum(t.r() - f.r()), dc = Integer.signum(t.c() - f.c());
        int r = f.r() + dr, c = f.c() + dc;
        while (r != t.r() || c != t.c()) {
            if (grid[r][c] != null) return false;
            r += dr; c += dc;
        }
        return true;
    }

    public Board clone() {
        Board b = new Board();
        for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) b.grid[r][c] = grid[r][c];
        return b;
    }

    public Position findKing(Color color) {
        for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) {
            Piece p = grid[r][c];
            if (p instanceof King && p.color == color) return new Position(r, c);
        }
        throw new IllegalStateException("no king");
    }
}

class Game {
    public Color turn = Color.W;
    public Board board;
    private final Object lock = new Object();

    public Game(Board b) { this.board = b; }

    public boolean isInCheck(Color color, Board board) {
        Position king = board.findKing(color);
        for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) {
            Piece p = board.grid[r][c];
            if (p != null && p.color != color && p.canMove(board, new Position(r, c), king)) return true;
        }
        return false;
    }

    public void move(Position from, Position to) {
        synchronized (lock) {
            Piece piece = board.get(from);
            if (piece == null || piece.color != turn) throw new IllegalStateException("INVALID_TURN");
            Piece target = board.get(to);
            if (target != null && target.color == piece.color) throw new IllegalStateException("OWN_PIECE");
            if (!piece.canMove(board, from, to)) throw new IllegalStateException("ILLEGAL_MOVE");

            Board snapshot = board.clone();
            board.set(to, piece); board.set(from, null);
            if (isInCheck(turn, board)) {
                board = snapshot;
                throw new IllegalStateException("KING_IN_CHECK");
            }
            turn = turn == Color.W ? Color.B : Color.W;
        }
    }
}

C++

#include <cmath>
#include <memory>
#include <mutex>
#include <stdexcept>

enum class Color { W, B };
struct Position { int r, c; };

class Board;
struct Piece {
    Color color;
    explicit Piece(Color c) : color(c) {}
    virtual ~Piece() = default;
    virtual bool canMove(Board& b, Position from, Position to) = 0;
    virtual char symbol() const = 0;
};

class Board {
public:
    std::shared_ptr<Piece> grid[8][8] = {};
    std::shared_ptr<Piece> get(Position p) { return grid[p.r][p.c]; }
    void set(Position p, std::shared_ptr<Piece> piece) { grid[p.r][p.c] = piece; }

    bool pathClear(Position f, Position t) {
        int dr = (t.r > f.r) - (t.r < f.r), dc = (t.c > f.c) - (t.c < f.c);
        int r = f.r + dr, c = f.c + dc;
        while (r != t.r || c != t.c) {
            if (grid[r][c]) return false;
            r += dr; c += dc;
        }
        return true;
    }
    Board clone() { Board b; for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) b.grid[r][c] = grid[r][c]; return b; }
    Position findKing(Color color);
};

struct Knight : Piece {
    using Piece::Piece;
    bool canMove(Board&, Position f, Position t) override {
        int dr = std::abs(f.r - t.r), dc = std::abs(f.c - t.c);
        return (dr == 2 && dc == 1) || (dr == 1 && dc == 2);
    }
    char symbol() const override { return color == Color::W ? 'N' : 'n'; }
};
struct Rook : Piece {
    using Piece::Piece;
    bool canMove(Board& b, Position f, Position t) override {
        if (f.r != t.r && f.c != t.c) return false;
        return b.pathClear(f, t);
    }
    char symbol() const override { return color == Color::W ? 'R' : 'r'; }
};
struct Bishop : Piece {
    using Piece::Piece;
    bool canMove(Board& b, Position f, Position t) override {
        if (std::abs(f.r - t.r) != std::abs(f.c - t.c)) return false;
        return b.pathClear(f, t);
    }
    char symbol() const override { return color == Color::W ? 'B' : 'b'; }
};
struct Queen : Piece {
    using Piece::Piece;
    bool canMove(Board& b, Position f, Position t) override {
        Rook r(color); Bishop bi(color);
        return r.canMove(b, f, t) || bi.canMove(b, f, t);
    }
    char symbol() const override { return color == Color::W ? 'Q' : 'q'; }
};
struct King : Piece {
    using Piece::Piece;
    bool canMove(Board&, Position f, Position t) override {
        return std::abs(f.r - t.r) <= 1 && std::abs(f.c - t.c) <= 1 && !(f.r == t.r && f.c == t.c);
    }
    char symbol() const override { return color == Color::W ? 'K' : 'k'; }
};
struct Pawn : Piece {
    using Piece::Piece;
    bool canMove(Board& b, Position f, Position t) override {
        int dir = color == Color::W ? -1 : 1;
        int startRow = color == Color::W ? 6 : 1;
        int dr = t.r - f.r, dc = t.c - f.c;
        auto target = b.get(t);
        if (dc == 0 && dr == dir && !target) return true;
        if (dc == 0 && f.r == startRow && dr == 2 * dir && !target && !b.get({f.r + dir, f.c})) return true;
        if (std::abs(dc) == 1 && dr == dir && target && target->color != color) return true;
        return false;
    }
    char symbol() const override { return color == Color::W ? 'P' : 'p'; }
};

Position Board::findKing(Color color) {
    for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) {
        auto p = grid[r][c];
        if (p && dynamic_cast<King*>(p.get()) && p->color == color) return {r, c};
    }
    throw std::runtime_error("no king");
}

class Game {
public:
    Board board;
    Color turn = Color::W;
    std::mutex mu;

    explicit Game(Board b) : board(std::move(b)) {}

    bool isInCheck(Color color, Board& bb) {
        Position king = bb.findKing(color);
        for (int r = 0; r < 8; r++) for (int c = 0; c < 8; c++) {
            auto p = bb.grid[r][c];
            if (p && p->color != color && p->canMove(bb, {r, c}, king)) return true;
        }
        return false;
    }

    void move(Position from, Position to) {
        std::lock_guard<std::mutex> g(mu);
        auto piece = board.get(from);
        if (!piece || piece->color != turn) throw std::runtime_error("INVALID_TURN");
        auto target = board.get(to);
        if (target && target->color == piece->color) throw std::runtime_error("OWN_PIECE");
        if (!piece->canMove(board, from, to)) throw std::runtime_error("ILLEGAL_MOVE");

        Board snapshot = board.clone();
        board.set(to, piece); board.set(from, nullptr);
        if (isInCheck(turn, board)) { board = std::move(snapshot); throw std::runtime_error("KING_IN_CHECK"); }
        turn = turn == Color::W ? Color::B : Color::W;
    }
};

TypeScript

type Color = "W" | "B";
type Position = { r: number; c: number };

abstract class Piece {
  constructor(public color: Color) {}
  abstract canMove(board: Board, from: Position, to: Position): boolean;
  abstract symbol(): string;
}

class Knight extends Piece {
  canMove(_b: Board, from: Position, to: Position): boolean {
    const dr = Math.abs(from.r - to.r), dc = Math.abs(from.c - to.c);
    return (dr === 2 && dc === 1) || (dr === 1 && dc === 2);
  }
  symbol() { return this.color === "W" ? "N" : "n"; }
}

class Rook extends Piece {
  canMove(b: Board, from: Position, to: Position): boolean {
    if (from.r !== to.r && from.c !== to.c) return false;
    return b.pathClear(from, to);
  }
  symbol() { return this.color === "W" ? "R" : "r"; }
}

class Bishop extends Piece {
  canMove(b: Board, from: Position, to: Position): boolean {
    if (Math.abs(from.r - to.r) !== Math.abs(from.c - to.c)) return false;
    return b.pathClear(from, to);
  }
  symbol() { return this.color === "W" ? "B" : "b"; }
}

class Queen extends Piece {
  canMove(b: Board, from: Position, to: Position): boolean {
    const rook = new Rook(this.color);
    const bishop = new Bishop(this.color);
    return rook.canMove(b, from, to) || bishop.canMove(b, from, to);
  }
  symbol() { return this.color === "W" ? "Q" : "q"; }
}

class King extends Piece {
  canMove(_b: Board, from: Position, to: Position): boolean {
    return Math.abs(from.r - to.r) <= 1 && Math.abs(from.c - to.c) <= 1 && !(from.r === to.r && from.c === to.c);
  }
  symbol() { return this.color === "W" ? "K" : "k"; }
}

class Pawn extends Piece {
  canMove(b: Board, from: Position, to: Position): boolean {
    const dir = this.color === "W" ? -1 : 1;
    const startRow = this.color === "W" ? 6 : 1;
    const dr = to.r - from.r, dc = to.c - from.c;
    const target = b.get(to);
    if (dc === 0 && dr === dir && !target) return true;
    if (dc === 0 && from.r === startRow && dr === 2 * dir && !target && !b.get({ r: from.r + dir, c: from.c })) return true;
    if (Math.abs(dc) === 1 && dr === dir && target && target.color !== this.color) return true;
    return false;
  }
  symbol() { return this.color === "W" ? "P" : "p"; }
}

class PieceFactory {
  static fromChar(ch: string): Piece | null {
    const color: Color = ch === ch.toUpperCase() ? "W" : "B";
    switch (ch.toLowerCase()) {
      case "k": return new King(color);
      case "q": return new Queen(color);
      case "r": return new Rook(color);
      case "b": return new Bishop(color);
      case "n": return new Knight(color);
      case "p": return new Pawn(color);
      default: return null;
    }
  }
}

class Board {
  private grid: (Piece | null)[][] = Array.from({ length: 8 }, () => Array(8).fill(null));
  get(p: Position) { return this.grid[p.r][p.c]; }
  set(p: Position, piece: Piece | null) { this.grid[p.r][p.c] = piece; }
  pathClear(from: Position, to: Position): boolean {
    const dr = Math.sign(to.r - from.r), dc = Math.sign(to.c - from.c);
    let r = from.r + dr, c = from.c + dc;
    while (r !== to.r || c !== to.c) {
      if (this.grid[r][c]) return false;
      r += dr; c += dc;
    }
    return true;
  }
  clone(): Board {
    const b = new Board();
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) b.grid[r][c] = this.grid[r][c];
    return b;
  }
  findKing(color: Color): Position {
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {
      const p = this.grid[r][c];
      if (p instanceof King && p.color === color) return { r, c };
    }
    throw new Error("no king");
  }
}

class Game {
  turn: Color = "W";
  constructor(public board: Board) {}

  isInCheck(color: Color, board: Board = this.board): boolean {
    const king = board.findKing(color);
    for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {
      const p = board.get({ r, c });
      if (p && p.color !== color && p.canMove(board, { r, c }, king)) return true;
    }
    return false;
  }

  move(from: Position, to: Position): void {
    const piece = this.board.get(from);
    if (!piece || piece.color !== this.turn) throw new Error("INVALID_TURN");
    const target = this.board.get(to);
    if (target && target.color === piece.color) throw new Error("OWN_PIECE");
    if (!piece.canMove(this.board, from, to)) throw new Error("ILLEGAL_MOVE");

    const snapshot = this.board.clone();
    this.board.set(to, piece); this.board.set(from, null);
    if (this.isInCheck(this.turn)) {
      this.board = snapshot;
      throw new Error("KING_IN_CHECK");
    }
    this.turn = this.turn === "W" ? "B" : "W";
  }
}

---

Extensibility

1. "Castling, en-passant, promotion"

Add special-move handlers to King and Pawn. King.canCastle(board, side) reads a hasMoved flag. Pawn.canEnPassant(lastMove) reads the move history. Promotion is a post-move hook that swaps the pawn for a new piece type via the factory.

2. "AI opponent"

Plug in a MoveChooser strategy. The engine enumerates legal moves (for each of its pieces, for each target square, simulate and discard if self-check). The strategy picks one. Minimax or MCTS implementations drop in behind the same interface.

3. "Replay / PGN export"

Keep a moves: Move[] list on Game. Serialise in algebraic notation for export, or replay by re-applying in order onto a fresh board.

---

What is Expected at Each Level

Level	Expectations
Mid	Piece movement, no check detection.
Senior / SMTS	Full check detection via clone + simulate, Factory from FEN, clean inheritance hierarchy.
Staff	Performance of legal-move generation, move encoding, integration with a protocol like UCI, move history / PGN.