Getting Ready: Chess Game

Chess is the oldest and most famous strategy game in the world — over 600 million people play it regularly, and platforms like Chess.com and Lichess serve billions of games per year. But from a software engineering perspective, what makes a chess game one of the best LLD problems isn't the game's popularity — it's the sheer density of object-oriented design challenges packed into a single domain.

Consider what a chess engine must model:

• Six distinct piece types — each with completely different movement rules. A Knight jumps in an L-shape and can leap over pieces. A Bishop slides diagonally across any number of squares. A Pawn moves forward but captures diagonally, can advance two squares on its first move, and transforms into any other piece upon reaching the far rank. This is not a problem where a single move() method works — it's a problem that demands polymorphism.

• Complex legality rules — a move is not legal just because the piece can physically reach the target square. It is only legal if it does not leave the moving player's own King in check. This means every candidate move must be simulated and the resulting board position must be evaluated for check before the move can be accepted.

• Special composite rules — castling involves moving TWO pieces (King and Rook) in a single turn, but only if neither has ever moved, no pieces stand between them, and the King does not pass through or land on an attacked square. En passant allows a Pawn to capture an adjacent Pawn that just moved two squares — but only on the immediately next turn. These rules test whether a design can gracefully accommodate exceptions without degenerating into spaghetti conditionals.

• Game state detection — the system must detect check, checkmate, and stalemate. Checkmate means the King is in check and no legal move can escape it. Stalemate means the King is NOT in check but no legal move exists. The difference between these two conditions determines whether someone wins or the game is a draw — getting it wrong is a critical bug.

This problem appears in LLD interviews at companies like Google, Amazon, Microsoft, and Meta because it simultaneously tests inheritance hierarchies, polymorphism, turn-based game loops, and algorithmic thinking — all in one cohesive system.

Over the next 9 tutorials, you'll design and implement a complete two-player Chess Game:

• Design a class hierarchy rooted in polymorphism — model six piece types (King, Queen, Rook, Bishop, Knight, Pawn) as subclasses of an abstract Piece, each overriding a getValidMoves() method that encodes its unique movement rules (Fundamentals S3: Inheritance)
• Create two UML class diagrams — one for the Piece hierarchy (showing inheritance and polymorphism), one for the Board and Game infrastructure (showing composition and associations)
• Build a UML sequence diagram — trace the complete flow of making a move: input parsing → validation → execution → check detection → turn switch
• Implement the board and all six pieces in Python and Java — complete, runnable code with type hints and access modifiers
• Implement the game loop and rule engine — turn management, move validation that prevents self-check, and game-ending condition detection
• Build the check, checkmate, and stalemate algorithm — a dedicated tutorial walking through the detection logic step-by-step with traced examples
• Apply three design patterns — Strategy (piece movement), Command (move history and undo), and see how they combine to create a clean, extensible architecture
• Handle special chess rules — castling (kingside and queenside), en passant, pawn promotion, and the fifty-move draw rule

Before starting this problem, make sure you're comfortable with:

• Inheritance and Polymorphism — the entire Piece hierarchy depends on abstract methods overridden in subclasses. If you're unsure how a Piece reference can call getValidMoves() and get behavior specific to a Knight or Bishop, review Fundamentals S3
• Abstract Classes vs Interfaces — we use an abstract Piece class (not an interface) because pieces share state (color, position). Understand when to choose one over the other (Fundamentals S4)
• Composition and Association — the Board composes Cells, and a Cell associates with a Piece. A Game composes a Board and associates with Players. These relationship types have different lifecycle semantics (Fundamentals S4)
• UML Class Diagrams — reading inheritance triangles, composition diamonds, and multiplicity labels (Fundamentals S5)
• UML Sequence Diagrams — lifelines, synchronous messages, alt fragments for conditional logic (Fundamentals S5)
• SOLID Principles — especially Open/Closed: adding a new piece type (e.g., a custom fairy chess piece) should not require modifying the Board or Game classes (Fundamentals S6)
• Strategy Pattern — each piece type has a different movement algorithm. This is Strategy applied through inheritance polymorphism (Fundamentals S12)
• Command Pattern — we track moves as objects so we can implement undo. Each Move encapsulates what changed and how to reverse it (Fundamentals S12)

If you've completed the easy and medium problems, you have all the building blocks. This problem pushes you to handle a deeper class hierarchy (6 concrete subclasses) and multi-step validation logic (move legality depends on the board state AFTER the move).

We will design:

• The complete domain model — Piece hierarchy, Board, Cell, Player, Game, Move, and GameStatus
• Movement rules for all six piece types — including sliding pieces (Queen, Rook, Bishop), jumping pieces (Knight), and the complex Pawn (forward, capture, double-advance, en passant, promotion)
• Castling — both kingside and queenside with all prerequisite checks
• Check detection — determining if a king is under attack
• Checkmate and stalemate detection — the difference is whether the king is in check
• Move validation — a move is legal only if it doesn't leave the player's own king in check
• Move history — tracked as Command objects for undo capability
• Turn management — alternating between White and Black

We will NOT design:

• Network multiplayer — no sockets, no client-server architecture. We design a local two-player game
• AI or move search — no minimax, no alpha-beta pruning, no evaluation functions. Stockfish has 350,000+ lines of code for this; it's a separate domain entirely
• Timers and clocks — chess clocks (blitz, rapid, classical) are a UI/infrastructure concern, not core domain modeling
• Database persistence — no saving games to disk, no replays from stored data
• GUI rendering — no graphical board display. Our interface is the domain model itself

Difficulty: Hard — This problem has 12-15 classes, a 6-subclass inheritance hierarchy, two class diagrams (split because one diagram would be too dense), special-rule handling, and an algorithm tutorial for check/checkmate/stalemate. It's one of the most OOP-intensive problems in the course.

How it differs from Tic Tac Toe (DP2): Tic Tac Toe has one piece type (X/O), trivial placement rules, and a 3×3 board. Chess has six piece types with unique movement, a complex legality layer (self-check prevention), special composite rules (castling, en passant), and game-termination detection that requires exhaustive search of all legal moves. Where Tic Tac Toe tests basic game loop design, Chess tests deep polymorphism and algorithmic validation.

Interview time allocation: In a 45-minute LLD interview, spend 5 minutes on requirements, 15 minutes on the Piece hierarchy and Board class diagram, 10 minutes on move validation and the make-a-move sequence, 10 minutes on check/checkmate logic, and 5 minutes on patterns and extensions.