Problem 5: Design a Chess Game

The setup

"Design a chess game. Two players, standard 8×8 board, six piece types, all standard movement rules including castling and en passant. Validate moves, detect check and checkmate, handle game state."

This problem tests polymorphism (each piece has different movement rules), game state management, and rule encapsulation. Strong candidates can identify the natural class hierarchy and avoid the trap of a god-class Board that knows all the rules.

Clarifying questions

Core entities

The Piece hierarchy

Each piece type knows its own movement rules. The Board doesn't need a giant switch statement on piece type. This is polymorphism doing the work.

abstract class Piece {
  Color color;
  
  // Returns true if this move is legal for this piece type
  // (ignoring whether it puts own king in check — that's the Game's job)
  abstract boolean canMove(Board board, Cell from, Cell to);
  
  // For pieces that affect game state beyond simple movement (e.g., king for castling)
  // Override if needed
  void onMoveComplete(Board board, Cell from, Cell to) {}
}

class Pawn extends Piece {
  boolean hasMoved = false;
  
  public boolean canMove(Board board, Cell from, Cell to) {
    int direction = (color == WHITE) ? 1 : -1;
    int rowDiff = to.row - from.row;
    int colDiff = Math.abs(to.col - from.col);
    
    // Forward move
    if (colDiff == 0 && rowDiff == direction && board.isEmpty(to)) {
      return true;
    }
    // First move can be 2 squares
    if (colDiff == 0 && rowDiff == 2 * direction && !hasMoved 
        && board.isEmpty(to) && board.isEmpty(from.shift(0, direction))) {
      return true;
    }
    // Diagonal capture
    if (colDiff == 1 && rowDiff == direction 
        && !board.isEmpty(to) && board.getPiece(to).color != color) {
      return true;
    }
    // En passant (special — see notes)
    if (canEnPassant(board, from, to)) return true;
    
    return false;
  }
  
  public void onMoveComplete(Board board, Cell from, Cell to) {
    hasMoved = true;
    // Promotion check
    int promotionRow = (color == WHITE) ? 7 : 0;
    if (to.row == promotionRow) {
      board.replacePiece(to, new Queen(color));  // default to Queen
    }
  }
}

class Rook extends Piece {
  boolean hasMoved = false;
  
  public boolean canMove(Board board, Cell from, Cell to) {
    // Must move in straight line
    if (from.row != to.row && from.col != to.col) return false;
    // Must not jump over pieces
    if (!board.isPathClear(from, to)) return false;
    // Destination must be empty or enemy
    if (!board.isEmpty(to) && board.getPiece(to).color == color) return false;
    return true;
  }
}

class Knight extends Piece {
  public boolean canMove(Board board, Cell from, Cell to) {
    int rowDiff = Math.abs(to.row - from.row);
    int colDiff = Math.abs(to.col - from.col);
    if (!((rowDiff == 2 && colDiff == 1) || (rowDiff == 1 && colDiff == 2))) return false;
    if (!board.isEmpty(to) && board.getPiece(to).color == color) return false;
    return true;
  }
}

class Bishop extends Piece {
  public boolean canMove(Board board, Cell from, Cell to) {
    int rowDiff = Math.abs(to.row - from.row);
    int colDiff = Math.abs(to.col - from.col);
    if (rowDiff != colDiff) return false;  // not diagonal
    if (!board.isPathClear(from, to)) return false;
    if (!board.isEmpty(to) && board.getPiece(to).color == color) return false;
    return true;
  }
}

class Queen extends Piece {
  public boolean canMove(Board board, Cell from, Cell to) {
    // Queen moves like rook OR bishop
    Rook tempRook = new Rook(color);
    Bishop tempBishop = new Bishop(color);
    return tempRook.canMove(board, from, to) || tempBishop.canMove(board, from, to);
  }
}

class King extends Piece {
  boolean hasMoved = false;
  
  public boolean canMove(Board board, Cell from, Cell to) {
    int rowDiff = Math.abs(to.row - from.row);
    int colDiff = Math.abs(to.col - from.col);
    if (rowDiff > 1 || colDiff > 1) {
      // Could be castling
      if (rowDiff == 0 && colDiff == 2) return canCastle(board, from, to);
      return false;
    }
    if (!board.isEmpty(to) && board.getPiece(to).color == color) return false;
    return true;
  }
}

The pattern: each piece is responsible for knowing its own movement. The Board provides utilities (isEmpty, isPathClear, getPiece). The Game orchestrates.

The Game class — orchestration and rule enforcement

class Game {
  private final Board board;
  private final Player white;
  private final Player black;
  private Player currentTurn;
  private GameStatus status;  // ACTIVE, CHECKMATE_WHITE_WINS, etc.
  private List moveHistory;
  
  public MoveResult makeMove(Player player, Cell from, Cell to) {
    if (player != currentTurn) {
      return MoveResult.failed("Not your turn");
    }
    Piece piece = board.getPiece(from);
    if (piece == null || piece.color != player.color) {
      return MoveResult.failed("No piece of yours at " + from);
    }
    
    // Piece-specific movement check
    if (!piece.canMove(board, from, to)) {
      return MoveResult.failed("Invalid move for " + piece.getClass().getSimpleName());
    }
    
    // Simulate the move; check if own king would be in check (illegal)
    Board hypothetical = board.cloneWithMove(from, to);
    if (isInCheck(hypothetical, player.color)) {
      return MoveResult.failed("Move would leave your king in check");
    }
    
    // Apply move
    Move move = board.executeMove(from, to);
    piece.onMoveComplete(board, from, to);
    moveHistory.add(move);
    
    // Check end-game conditions
    Color opponent = (player.color == WHITE) ? BLACK : WHITE;
    if (isCheckmate(board, opponent)) {
      status = (player.color == WHITE) ? CHECKMATE_WHITE_WINS : CHECKMATE_BLACK_WINS;
    } else if (isStalemate(board, opponent)) {
      status = STALEMATE;
    }
    
    // Switch turn
    currentTurn = (currentTurn == white) ? black : white;
    return MoveResult.success(move);
  }
  
  private boolean isInCheck(Board board, Color color) {
    Cell kingCell = board.findKing(color);
    Color opponent = (color == WHITE) ? BLACK : WHITE;
    // Check if any opponent piece can capture king
    for (Cell c : board.cellsWithPieces(opponent)) {
      Piece p = board.getPiece(c);
      if (p.canMove(board, c, kingCell)) return true;
    }
    return false;
  }
  
  private boolean isCheckmate(Board board, Color color) {
    if (!isInCheck(board, color)) return false;
    // Check if any move can get out of check
    for (Cell from : board.cellsWithPieces(color)) {
      Piece p = board.getPiece(from);
      for (Cell to : board.allCells()) {
        if (p.canMove(board, from, to)) {
          Board hypothetical = board.cloneWithMove(from, to);
          if (!isInCheck(hypothetical, color)) return false;  // escape exists
        }
      }
    }
    return true;
  }
}

Cross-examination round 1: check/checkmate separation

Cross-examination round 2: special moves

Takeaway

Chess is the canonical use of polymorphism for behavioural variation. Each piece type has different movement rules — same interface (canMove), different implementations. The naive design has one giant isValidMove(piece, from, to) method with a 6-way switch. The OO design distributes the knowledge to the pieces. Adding a new piece type (variant chess: like a Cannon from Chinese chess) becomes a new class, not a modification to existing code.

The deeper lesson: let behavior live where the data lives. The Pawn class knows about pawns; the Rook class knows about rooks. The Game class doesn't need to be omniscient — it orchestrates by asking each piece what it can do.