Cruxly

Cruxly › Low-level design › LLD Exercises

Chess / Game Board

per-piece rules without an inheritance explosion

Open the interactive lesson

Prompt: design a chess game. Model the board, pieces, moves and turns; validate whether a move is legal; detect check and checkmate.

45 minutes. The interesting part is where the rules live.

Applying the five moves: nouns are Board, Piece, Move, Player — and the temptation to add a subclass per piece type is exactly what move 2 ("kill most of them") should catch, since a piece's identity (what it is) and its movement rule (how it moves) are different concerns that don't need to live in the same class hierarchy. The invariant is "a move is legal only if it doesn't leave the mover's own king in check" — this single sentence is why castling, en passant, and pins can't be per-piece overrides, because legality depends on the whole board's state, not one piece in isolation. The interface seam is the movement rule itself (a MoveRule per piece type, held as data on the piece rather than expressed via inheritance), because the prompt's mention of check/checkmate is the signal that rules need to be evaluated against global state, not just local piece geometry. Concurrency: a single game between two players making alternating moves has no real concurrency story — say that plainly rather than inventing one, and name multi-game-server concurrency as a genuinely separate, unasked-for problem if it comes up.

Where the rules live — the whole exercise

Almost every candidate starts with:

abstract class Piece { abstract boolean isValidMove(from, to); } class Knight extends Piece { ... }

It is not wrong, and it handles six pieces cleanly. It breaks on the rules that are not about a single piece:

Knight.isValidMove cannot see any of that without being handed the whole game, at which point the encapsulation was a fiction.

The clean separation, and it is the answer to this problem:

That is: pseudo-legal moves from the piece, legal moves from the rules engine. This single distinction is what the exercise is testing, and naming those two terms is a strong signal.

The model

enum Colour { WHITE, BLACK } enum PieceType { KING, QUEEN, ROOK, BISHOP, KNIGHT, PAWN }

class Piece { PieceType type; Colour colour; boolean hasMoved; }

class Square { int rank, file; } // value type, immutable

class Board { Piece[8][8] grid; Square enPassantTarget; // null unless a pawn just double-stepped CastlingRights rights; }

class Move { Square from, to; PieceType promotion; } // value type

interface MoveGenerator { List<Square> pseudoLegal(Board b, Square from); } // one per PieceType — geometry only

class Rules { boolean isLegal(Board b, Move m, Colour turn); List<Move> legalMoves(Board b, Colour turn); boolean inCheck(Board b, Colour c); GameState state(Board b, Colour turn); // ONGOING, CHECKMATE, STALEMATE, DRAW }

Three decisions worth defending:

Piece is a small value object, not a class hierarchy. Composition over inheritance: type and colour are data, geometry is a lookup from type to a MoveGenerator. A subclass per piece buys nothing once the rules live outside, and it makes "what does a promoted pawn become" a mutation of identity rather than a field.

hasMoved lives on the piece because castling and the pawn double-step need it. It is the minimum state that makes those rules expressible.

enPassantTarget lives on the board, not the pawn, because it is a property of the position that expires after exactly one move. Putting it on the pawn means every pawn needs clearing every turn — a loop that is easy to forget and produces a bug that appears once in a hundred games.

Legality, check, and the one honest trick

isLegal(board, move, turn):

  1. move.from holds a piece of turn's colour
  2. move.to ∈ pseudoLegal(board, move.from)
  3. path is clear (except knight) and destination is empty or an enemy
  4. special cases: castling rights / en passant target / promotion required
  5. after applying the move, turn's king is not attacked ← the key step

Step 5 is where pins, discovered checks and "you may not move into check" all come from — as one rule, not three. Candidates who try to detect pins directly write a large amount of geometry and still miss discovered checks. Applying the move and asking "is my king attacked?" handles every case uniformly.

The trick: apply, test, undo. Do not deep-copy the board for every candidate move — that is allocation-heavy and slow when generating all legal moves. Mutate, evaluate, then reverse the mutation, storing what was captured so the undo is exact.

Be honest that this makes Board mutable and therefore not thread-safe, and that the undo must restore enPassantTarget and hasMoved as well as the squares. The undo restoring more than the grid is the bug everyone hits — a rook that castled and then had the move undone must have hasMoved restored, or castling rights are silently lost.

inCheck(board, colour): find that king, ask whether any enemy pseudo-legal move attacks the square. Naively O(pieces × moves), which for a 64-square board is trivially fast — say that explicitly so nobody thinks you missed it. The real optimisation (attack maps) belongs in an engine, not an interview.

Checkmate is not a separate algorithm: inCheck(c) && legalMoves(c).isEmpty(). Stalemate is !inCheck(c) && legalMoves(c).isEmpty(). Deriving both from one primitive rather than writing two detectors is the point.

What the follow-ups actually test

"Add a new piece with different movement." A new MoveGenerator implementation and an enum value. Nothing else changes — this is the payoff for putting geometry behind an interface, and it is why the piece-subclass design is worse even though it looks equivalent at first.

"Support undo of whole moves, not just internal testing." The internal undo is already there; expose it as a move stack. Each entry must capture: the move, the captured piece, the previous enPassantTarget, previous castling rights, and previous hasMoved flags. The completeness of that list is the answer — undo bugs are always a missing field, never a missing algorithm.

"Threefold repetition and the 50-move rule." Both need history, not position: a hash of each position seen (Zobrist hashing is the standard, worth naming) and a halfmove clock reset on pawn moves and captures. Notice that these are the first rules that cannot be answered from the current board alone — the model must grow from a position to a game. That observation is worth more than the implementation.

"Make it a chess engine." Out of scope, and say so rather than drifting into minimax with four minutes left. The model above is the right foundation for one (legalMoves is exactly what a search needs), which is the useful sentence.

How to say it in the interview

"The temptation is a subclass per piece with an overridden isValidMove. That works for the six basic pieces and then breaks on castling, en passant and pinned pieces — because those rules are not properties of a piece, they are properties of the game state."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons