The 100 problems, solved / Games / 065 · Design chess

Design chess

Pieces with polymorphic moves, check and checkmate, undo with Command.

Problem 065 of 100GamesL4-L52 Nov 2026
Concepts this design leans on

01The design, in the six-step framework

1. Requirements and use cases

Nobody finishes chess in an interview, so the skill is in scoping. Agree the core first: pieces, legal moves, check, and undo. Leave the rule edge cases named but unbuilt, and make sure the structure has a place for them.

  • Two players alternate moves on an 8×8 board.
  • A move is rejected if the piece cannot move that way, if the path is blocked, or if it leaves the mover's own king in check.
  • The game detects check, checkmate and stalemate after each move.
  • A player can undo the last move, and the history can be replayed.
  • A pawn reaching the last rank is promoted to a queen in this version.

Out of scope for this round: castling, en passant, draw by repetition, clocks and a chess engine. All are named so the interviewer knows they were considered. Constraints: adding a new piece type must not touch the game loop; undo must restore everything a move changed, including a captured piece; legal-move checking must not corrupt the real board when it tries a move.

2. Core entities and relationships

  • Colour: white or black.
  • Position: an immutable (row, col) value.
  • Piece: an abstract class with a colour and pseudo_moves(board, from); each subclass supplies its movement.
  • Board: the map from position to piece, with path queries and attack detection.
  • Move: a command object that knows how to apply and undo itself on a board.
  • Game: the turn, the move history and legality.
GameBoard and commandsPieceshistory0..32Gameboard: Boardturn: Colourhistory: list[Move]status: Statusmove(src, dst) -> Statusundo()legal_moves(colour)Boardsquares: dict[Position, Piece]at(pos)king_of(colour)is_attacked(pos, by)Movesrcdstpiececapturedpromoted_toapply(board)undo(board)Piececolour: Colourpseudo_moves(board, src)Sliderdirectionspseudo_moves(board, src)KnightPawnKing

The board aggregates pieces rather than composing them, because a captured piece leaves the board and lives on inside its Move so undo can put it back. The game composes its history, since a move means nothing outside its game.

3. Interfaces and key methods

from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum
from typing import Iterator, Optional

class Colour(Enum):
    WHITE = 1
    BLACK = -1
    def other(self) -> "Colour":
        return Colour.BLACK if self is Colour.WHITE else Colour.WHITE

class Status(Enum):
    ACTIVE = "active"
    CHECK = "check"
    CHECKMATE = "checkmate"
    STALEMATE = "stalemate"

@dataclass(frozen=True)
class Position:
    row: int
    col: int
    def on_board(self) -> bool:
        return 0 <= self.row < 8 and 0 <= self.col < 8

class IllegalMove(Exception):
    """The requested move breaks the rules."""

class Piece(ABC):
    def __init__(self, colour: Colour) -> None:
        self.colour = colour
    @abstractmethod
    def pseudo_moves(self, board: "Board", src: Position) -> Iterator[Position]:
        """Destinations by movement rules alone; own-king safety is checked by Game."""

Invariants: pseudo_moves never changes the board; every subclass honours that contract, so Game can treat all pieces alike; after any accepted move the mover's king is not attacked; Move.undo is the exact inverse of Move.apply.

4. Design patterns and the choices behind them

Polymorphic movement

The force: six piece types with different movement. A switch on piece type would sit in every place that asks about movement. Instead, each class answers pseudo_moves, so the game makes one call and polymorphism does the dispatch. Bishop, rook and queen differ only in their directions, so they share a Slider base. That is a case where inheritance fits: a queen really is a kind of piece, and the sliding walk is shared behaviour rather than a borrowed helper.

The Liskov substitution check is simple: any Piece can be asked for moves, none raises, none mutates the board. Note the deliberate split of responsibility. A piece knows how it moves; only the game knows the rule about exposing your own king, because that rule involves the whole board.

Moves as commands

The force: undo must restore the captured piece and reverse a promotion. Making a move an object with apply and undo is the command pattern, and the history list becomes undo, replay and move notation for free. The alternative, copying the whole board per move, is simpler but costs 64 entries per ply, and that cost is paid again for every candidate during checkmate detection.

Try, test, take back

Legality is decided by applying the command, asking whether the king is attacked, and undoing it. One mechanism covers pins, blocks and moving out of check, with no special rules. The board stays correct because undo is exact. This is the same object doing double duty, and it is the reason the command was worth having.

Shared piece objects and a status

Pieces hold only a colour, so one instance per (type, colour) could be shared across games, which is the flyweight idea. Promotion and capture still work, since position lives in the board. The game's Status is a small state value recomputed after each move, and the board is a sparse map from position to piece.

5. Core flow and code

  1. Game.move(src, dst) checks a piece of the right colour is on src and that dst is in its pseudo_moves.
  2. It builds a Move, calls apply, and asks Board.is_attacked about its own king; if attacked, it undoes and raises IllegalMove.
  3. The move joins the history and the turn passes.
  4. _status checks whether the opponent is in check and whether any legal reply exists: no reply means checkmate or stalemate.
class Slider(Piece):
    directions: tuple = ()
    def pseudo_moves(self, board: "Board", src: Position) -> Iterator[Position]:
        for dr, dc in self.directions:
            pos = Position(src.row + dr, src.col + dc)
            while pos.on_board():
                other = board.at(pos)
                if other is None:
                    yield pos
                else:
                    if other.colour is not self.colour:
                        yield pos
                    break
                pos = Position(pos.row + dr, pos.col + dc)

STRAIGHT = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIAGONAL = ((1, 1), (1, -1), (-1, 1), (-1, -1))

class Rook(Slider):
    directions = STRAIGHT
class Bishop(Slider):
    directions = DIAGONAL
class Queen(Slider):
    directions = STRAIGHT + DIAGONAL

class Stepper(Piece):
    steps: tuple = ()
    def pseudo_moves(self, board: "Board", src: Position) -> Iterator[Position]:
        for dr, dc in self.steps:
            pos = Position(src.row + dr, src.col + dc)
            if pos.on_board():
                other = board.at(pos)
                if other is None or other.colour is not self.colour:
                    yield pos

class Knight(Stepper):
    steps = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1))
class King(Stepper):
    steps = STRAIGHT + DIAGONAL

class Pawn(Piece):
    def pseudo_moves(self, board: "Board", src: Position) -> Iterator[Position]:
        step = self.colour.value
        one = Position(src.row + step, src.col)
        if one.on_board() and board.at(one) is None:
            yield one
            two = Position(src.row + 2 * step, src.col)
            home = 1 if self.colour is Colour.WHITE else 6
            if src.row == home and board.at(two) is None:
                yield two
        for dc in (-1, 1):
            diag = Position(src.row + step, src.col + dc)
            if diag.on_board():
                other = board.at(diag)
                if other is not None and other.colour is not self.colour:
                    yield diag

class Board:
    def __init__(self) -> None:
        self.squares: dict = {}
    def at(self, pos: Position) -> Optional[Piece]:
        return self.squares.get(pos)
    def pieces(self, colour: Colour) -> list:
        return [(p, pc) for p, pc in self.squares.items() if pc.colour is colour]
    def king_of(self, colour: Colour) -> Position:
        return next(p for p, pc in self.pieces(colour) if isinstance(pc, King))
    def is_attacked(self, pos: Position, by: Colour) -> bool:
        return any(pos in pc.pseudo_moves(self, p) for p, pc in self.pieces(by))

@dataclass
class Move:
    src: Position
    dst: Position
    piece: Piece
    captured: Optional[Piece] = None
    promoted_to: Optional[Piece] = None

    def apply(self, board: Board) -> None:
        self.captured = board.at(self.dst)
        del board.squares[self.src]
        last_rank = 7 if self.piece.colour is Colour.WHITE else 0
        if isinstance(self.piece, Pawn) and self.dst.row == last_rank:
            self.promoted_to = Queen(self.piece.colour)
        board.squares[self.dst] = self.promoted_to or self.piece

    def undo(self, board: Board) -> None:
        board.squares[self.src] = self.piece
        if self.captured is not None:
            board.squares[self.dst] = self.captured
        else:
            del board.squares[self.dst]

class Game:
    def __init__(self, board: Board, turn: Colour = Colour.WHITE) -> None:
        self.board, self.turn = board, turn
        self.history: list = []
        self.status = Status.ACTIVE

    def _safe(self, move: Move, colour: Colour) -> bool:
        move.apply(self.board)
        safe = not self.board.is_attacked(self.board.king_of(colour), colour.other())
        move.undo(self.board)
        return safe

    def legal_moves(self, colour: Colour) -> list:
        candidates = [Move(src, dst, pc) for src, pc in self.board.pieces(colour)
                      for dst in pc.pseudo_moves(self.board, src)]
        return [m for m in candidates if self._safe(m, colour)]

    def _status(self) -> Status:
        in_check = self.board.is_attacked(self.board.king_of(self.turn), self.turn.other())
        if self.legal_moves(self.turn):
            return Status.CHECK if in_check else Status.ACTIVE
        return Status.CHECKMATE if in_check else Status.STALEMATE

    def move(self, src: Position, dst: Position) -> Status:
        piece = self.board.at(src)
        if self.status in (Status.CHECKMATE, Status.STALEMATE):
            raise IllegalMove("the game is over")
        if piece is None or piece.colour is not self.turn:
            raise IllegalMove("no piece of yours on that square")
        if dst not in piece.pseudo_moves(self.board, src):
            raise IllegalMove("that piece cannot move there")
        move = Move(src, dst, piece)
        if not self._safe(move, self.turn):
            raise IllegalMove("that move leaves your king in check")
        move.apply(self.board)
        self.history.append(move)
        self.turn = self.turn.other()
        self.status = self._status()
        return self.status

    def undo(self) -> None:
        if not self.history:
            raise IllegalMove("nothing to undo")
        self.history.pop().undo(self.board)
        self.turn = self.turn.other()
        self.status = self._status()

6. Extensions, concurrency and what interviewers probe

  • "Add castling and en passant." Both are special moves touching two pieces or depending on the last move. Subclass Move so apply and undo handle both pieces; Game.history[-1] already answers "what moved last". Castling also asks whether empty squares are attacked, which is_attacked cannot answer as written: a pawn's pseudo_moves yields a forward step that is no attack and omits a diagonal with nothing on it, so it is reliable only for an occupied square such as the king's.
  • "How do you detect checkmate?" No legal reply while in check. Stalemate is no legal reply while not in check. It is the same loop, and it is slow only in the sense that it tries every move, which is fine at human speed.
  • "Add a new fairy piece." One subclass with its directions or steps; nothing else changes. That is the open-closed payoff.
  • "Add an engine." legal_moves plus apply and undo is exactly what minimax needs, without copying boards.
  • Concurrency: a game is one sequential stream of moves. _safe mutates the board temporarily, so one lock per game must also cover readers, or readers must wait for the move to finish.
  • Common mistake: putting the king-safety rule inside each piece, which duplicates it six times, and an undo that forgets the captured piece or the promotion.

02Where this question was reported