Chess

Design a two-player chess game: a board, pieces that move by their own rules, turn order, check detection and a validator that refuses illegal moves. The interview asks how you model pieces and how you test a move without breaking the board.

Design a chess game for two players. The board is 8 by 8. Each kind of piece moves by its own rule, and the players take turns. Refuse a move that is not allowed, including one that leaves your own king attacked. Tell the caller when a move gives check. Say which rules of chess you leave out.

Questions to ask first

• Which rules are in scope? Assume the moves of all six piece types, captures, turns, and check. Castling, en passant and pawn promotion are out for now. Say so, and show where each would be added.
• Do we detect checkmate and stalemate? Assume not in the first version. A move reports check, and the players decide when the game is over. Mate detection is a follow-up.
• Who plays? Assume two people who call `move(from, to)` in turn. There is no screen and no computer opponent.
• How are squares named? Assume the usual names, a1 to h8, where a1 is White's left corner. Text such as "e2" is turned into a Square at the edge of the design.
• What does the caller learn from a refused move? Assume a reason: no piece there, not your turn, the piece cannot move like that, or the move leaves your king attacked. A refused move changes nothing.
• Do we need undo, a move list or a clock? Assume none now. Undo is a likely follow-up, so keep each move as an object.

Requirements

• Set up the standard starting position with White to move.
• Move a piece from one square to another, and let the turn pass to the other colour only when the move is accepted.
• Give every piece type its own movement rule: pawns, knights, bishops, rooks, queens and kings, including captures and blocking.
• Refuse a move that leaves the mover's own king attacked, including a move by a pinned piece and a king stepping onto an attacked square.
• Report check after a move that attacks the opponent's king.
• Return a clear reason for every refused move, and leave the board and the turn unchanged.

Out of scope

• Castling, en passant and pawn promotion (the extensions show how they fit).
• Checkmate, stalemate, draws and resignation.
• A screen, move notation and a computer opponent.
• Clocks and saving games.

Entities

• Game: the turn, the history of moves; move(from, to)
• Board: an 8 by 8 grid of pieces; at(square), set(square, piece), isAttackedBy(color, square)
• Square: a file and a rank, a small immutable record
• Piece: a colour, a type and a MoveRule
• PieceType: PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING; Color: WHITE, BLACK
• MoveRule: attacks(board, piece, from, to) and canMove(...), one rule for each way of moving
• SlidingRule, StepRule, PawnRule: the three rules that cover all six piece types
• Move: a move as an object that can apply itself and take itself back
• MoveValidator: validate(board, turn, from, to) and isInCheck(board, color)

Classes in the model design

• Game (class)
• Board (class)
• Square (class)
• Color (enum)
• PieceType (enum)
• Piece (class)
• MoveRule (interface)
• SlidingRule (class)
• StepRule (class)
• PawnRule (class)
• Move (class)
• MoveValidator (class)

The main use case, step by step

1. The caller sends `move("e2", "e4")`. The facade turns the text into two `Square` objects and calls `game.move(from, to)`. A square that does not exist is refused here.
2. `Game` asks `MoveValidator.validate(board, turn, from, to)`. The validator looks up the piece on the from square. No piece means NO_PIECE. A piece of the other colour means NOT_YOUR_TURN.
3. The validator then asks the piece's rule: `piece.rule().canMove(board, piece, from, to)`. A `PawnRule` accepts one square forward onto an empty square, or two squares from the start rank when both squares are empty. A rule that says no gives ILLEGAL_MOVE.
4. The shape is fine, but the move must not expose the mover's own king. The validator builds a `Move`, applies it to the board, asks `isInCheck(board, turn)`, and then reverts the move. If the king is attacked, the answer is KING_IN_CHECK.
5. `isInCheck` finds the king with `board.kingOf(color)` and asks `board.isAttackedBy(opponent, kingSquare)`. That method asks every enemy piece's rule whether it attacks the king's square. A pawn attacks diagonally even though it moves straight, which is why a rule has both `attacks` and `canMove`.
6. On success `Game` applies the move, pushes it on the history, passes the turn, and asks `isInCheck` for the other colour. The result tells the caller what was captured and whether the new side to move is in check.

Patterns used

• Strategy (movement rules): MoveRule with SlidingRule, StepRule and PawnRule. Each Piece holds one rule.. Pieces differ only in how they move. Putting that in a rule object lets a rook, a bishop and a queen share one sliding rule, and lets each rule be tested alone on a small board.
• Command (the move): Move knows how to apply itself to a board and how to revert itself.. The validator tries a move and takes it back with the same two methods. Undo, redo and a move list then cost almost nothing, and special moves such as castling become new kinds of Move.
• Composition over inheritance: Piece has a MoveRule and a Color. There is no WhitePawn and no Queen subclass.. Colour and movement are separate things that vary on their own. Inheritance would force one class for every colour and type pair, or copy the rook and bishop code into the queen.

Key code

The rule interface and the two shared rules

public interface MoveRule {
    /** True if a piece of this kind on 'from' attacks 'to': the shape fits and nothing is in the way. */
    boolean attacks(Board board, Piece piece, Square from, Square to);

    /** True if the piece may move there, ignoring check. The target must not hold the piece's own colour. */
    default boolean canMove(Board board, Piece piece, Square from, Square to) {
        Piece target = board.at(to);
        return attacks(board, piece, from, to) && (target == null || target.color() != piece.color());
    }
}

/** Rook, bishop and queen: slide along the given directions until something blocks. */
public final class SlidingRule implements MoveRule {
    static final int[][] STRAIGHT = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static final int[][] DIAGONAL = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    private final int[][] directions;

    public SlidingRule(int[][] directions) { this.directions = directions; }

    @Override
    public boolean attacks(Board board, Piece piece, Square from, Square to) {
        for (int[] d : directions) {
            int f = from.file() + d[0], r = from.rank() + d[1];
            while (Square.inBounds(f, r)) {
                if (f == to.file() && r == to.rank()) return true;
                if (board.at(new Square(f, r)) != null) break;      // a piece blocks the rest of the line
                f += d[0];
                r += d[1];
            }
        }
        return false;
    }
}

/** King and knight: fixed jumps. Nothing can block them. */
public final class StepRule implements MoveRule {
    private final int[][] steps;
    public StepRule(int[][] steps) { this.steps = steps; }

    @Override
    public boolean attacks(Board board, Piece piece, Square from, Square to) {
        for (int[] s : steps) if (from.file() + s[0] == to.file() && from.rank() + s[1] == to.rank()) return true;
        return false;
    }
}

The pawn rule, and how a piece gets its rule

/** The pawn is the odd one: it moves straight, but attacks and captures diagonally. */
public final class PawnRule implements MoveRule {
    @Override
    public boolean attacks(Board board, Piece piece, Square from, Square to) {
        return to.rank() == from.rank() + piece.color().forward() && Math.abs(to.file() - from.file()) == 1;
    }

    @Override
    public boolean canMove(Board board, Piece piece, Square from, Square to) {
        int forward = piece.color().forward();
        Piece target = board.at(to);
        if (to.file() == from.file()) {
            if (target != null) return false;                         // straight moves never capture
            if (to.rank() == from.rank() + forward) return true;
            int startRank = piece.color() == Color.WHITE ? 1 : 6;
            return from.rank() == startRank && to.rank() == from.rank() + 2 * forward
                && board.at(new Square(from.file(), from.rank() + forward)) == null;   // both squares empty
        }
        return attacks(board, piece, from, to) && target != null && target.color() != piece.color();
    }
}

// inside Piece
private static final int[][] KNIGHT_JUMPS = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
private static final int[][] ALL_DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

public static Piece of(Color color, PieceType type) {
    MoveRule rule = switch (type) {
        case PAWN -> new PawnRule();
        case KNIGHT -> new StepRule(KNIGHT_JUMPS);
        case BISHOP -> new SlidingRule(SlidingRule.DIAGONAL);
        case ROOK -> new SlidingRule(SlidingRule.STRAIGHT);
        case QUEEN -> new SlidingRule(ALL_DIRECTIONS);
        case KING -> new StepRule(ALL_DIRECTIONS);
    };
    return new Piece(color, type, rule);
}

Move as a command, the validator and Game.move

public final class Move {
    private final Square from, to;
    private final Piece piece, captured;

    public Move(Board board, Square from, Square to) {
        this.from = from;
        this.to = to;
        this.piece = board.at(from);
        this.captured = board.at(to);                 // remembered, so revert can put it back
    }

    public void apply(Board board) { board.set(from, null); board.set(to, piece); }
    public void revert(Board board) { board.set(to, captured); board.set(from, piece); }
    public Piece captured() { return captured; }
}

public final class MoveValidator {
    public MoveStatus validate(Board board, Color turn, Square from, Square to) {
        Piece piece = board.at(from);
        if (piece == null) return MoveStatus.NO_PIECE;
        if (piece.color() != turn) return MoveStatus.NOT_YOUR_TURN;
        if (!piece.rule().canMove(board, piece, from, to)) return MoveStatus.ILLEGAL_MOVE;
        Move trial = new Move(board, from, to);
        trial.apply(board);                           // try it, look at the king, take it back
        boolean exposed = isInCheck(board, turn);
        trial.revert(board);
        return exposed ? MoveStatus.KING_IN_CHECK : MoveStatus.OK;
    }

    public boolean isInCheck(Board board, Color color) {
        return board.isAttackedBy(color.opposite(), board.kingOf(color));
    }
}

// inside Game
public MoveResult move(Square from, Square to) {
    MoveStatus status = validator.validate(board, turn, from, to);
    if (status != MoveStatus.OK) return new MoveResult(status, null, false);
    Move move = new Move(board, from, to);
    move.apply(board);
    history.push(move);
    turn = turn.opposite();
    return new MoveResult(MoveStatus.OK, move.captured(), validator.isInCheck(board, turn));
}

Deep dives

Pieces: inheritance or composition?

Weak: One Piece class with a type field and a switch inside canMove. All six rules live in one method. A change to the knight can break the rook, and the method grows with every rule you add.

Good: An abstract Piece with Pawn, Knight, Bishop, Rook, Queen and King subclasses, each overriding canMove. It matches how people think about chess, and it is what most interviewers expect. A cost appears at once: a queen moves like a rook and a bishop together, so you either copy their code or make the queen call both. Colour needs a field, never WhitePawn and BlackPawn classes.

Great: Ask what actually differs between pieces. Here it is only how they move: they carry no extra data. So the movement becomes an object, a MoveRule, and Piece holds a colour, a type and a rule. Rook, bishop and queen share SlidingRule with different directions. Knight and king share StepRule with different jumps. Only the pawn needs its own PawnRule. A new piece in a chess variant is a new combination of rules and not a new class tree.

Trade-off: The subclass tree is easy to read for six pieces, and gives a natural home to data that belongs to one piece, such as whether a pawn has moved. Composition removes duplication and lets you test a rule alone. Pick one, and say why: strong answers name the queen problem and the colour problem.

Check, pins and the validator

Weak: Write the shape check for each piece, then a separate scan for check that repeats the movement logic for the king's attackers. Pawns go wrong, because a pawn attacks diagonally but moves straight. Pins are forgotten: a bishop pinned to its king is allowed to move.

Good: Use one idea for all of it: after the move, the mover's own king must not be attacked. The validator makes the move, asks whether the king's square is attacked by any enemy piece, and takes the move back. Moving a pinned piece, ignoring a check, and a king stepping onto an attacked square are all caught by the same test.

Great: Give each rule an attacks method next to canMove, so that attack detection and move checking share the same code. The pawn is the one rule that differs. Make the trial move a Move command with apply and revert, so the board is restored exactly. Test the design with a count of all legal move sequences from the start position. The reference solution gives 20, 400, 8,902 and 197,281 moves for depths 1 to 4, which are the known values. A wrong pin or check rule changes those numbers.

Trade-off: The trial move scans up to 16 enemy pieces for every candidate, which is fast enough for a game between two people. Engines keep attack maps that update on each move, which is faster and much more code. Checkmate follows from the same test: in check, and no piece has a move that passes it.

Undo: Command or Memento

Weak: Keep a single copy of the previous position. One undo works and a second does not. Or copy the entire board by hand in every method that changes it, so each new rule must remember to do so.

Good: Memento. Before every move, save a snapshot of the whole position: the grid and whose turn it is. Undo restores the last snapshot. It is simple and always right, even for rules that change many things. It costs a copy of 64 squares for each move.

Great: Command. Each Move knows how to apply and revert itself, and remembers the piece it captured. Game keeps a stack of moves, and undo pops one, reverts it and gives the turn back. The validator already uses the same two methods for its trial move, so undo adds no new logic. A redo stack and a move list come from the same objects. Special moves such as castling are moves that revert two pieces, or a move that restores a promoted pawn.

Trade-off: Snapshots need no thought about what changed, and they are the safe choice when a move changes hidden state. Commands are smaller and give you the list of moves for free, but each special move must write its own revert correctly. Choose the command when moves are already objects, and say how you would test revert.

Now add one more feature

• Now add pawn promotion. When a pawn reaches the last rank, the player chooses a piece. Add a `PromotionMove` command whose `apply` puts the new piece on the board, and whose `revert` puts the pawn back. `PawnRule` is unchanged. `Game` asks for the choice only when the move is a promotion.
• Now add castling and en passant. Both are special moves, each its own `Move` subclass. Castling moves two pieces. It needs to know that the king and the rook have not moved, which `Piece` can hold as a flag or the history can answer. It also needs the squares between to be safe, which `board.isAttackedBy` already tells you. En passant needs the previous move from the history.
• Now detect checkmate and stalemate. Add `hasLegalMove(color)` to the validator: try every piece and every target square through `validate`. No legal move and in check is checkmate. No legal move and not in check is stalemate. Report the game status after each move.
• Now add undo and redo. `Game` pops a `Move` from the history, calls `revert`, gives the turn back and pushes the move on a redo stack. A new move clears the redo stack. The validator and the rules do not change.

What each level is expected to show

SDE-1: Clear classes for Board, Piece, Square and Game, a movement rule for each piece type with blocking handled for sliding pieces, turn order, and a refusal with a reason for every bad move. Can explain how check is found.

SDE-2: All of SDE-1, plus a rule object that shares code between pieces, and check found by asking every enemy piece whether it attacks the king. A trial move that is taken back handles pins and self-check, and a Move object makes undo easy. States which rules are left out and where each would be added.

Common mistakes

• Creating WhitePawn and BlackPawn, or one class for each colour and type, when colour is only a field.
• Treating a pawn's forward move as an attack on the king, or forgetting that a pawn attacks diagonal squares even when they are empty.
• Checking only whether the king is in check before the move, so a pinned piece can move away or a king can step into an attack.
• Letting a bishop, rook or queen jump over a piece, or capture a piece of its own colour.
• Passing the turn on a refused move, or leaving a half-made move on the board after a refusal.
• Putting all the rules inside Board, so the board class knows every piece and becomes the place where every change lands.
• Using strings such as "e2" through the whole design instead of a Square type, so parsing mistakes appear everywhere.
• Never saying which rules are left out. Interviewers expect castling, en passant and promotion to be named and placed.

Lessons behind this answer

• Inheritance, composition and polymorphism
• Strategy
• Command
• Single responsibility, open/closed, Liskov
• Interface segregation and dependency inversion
• Chess: pieces, turns, check and a trial move
• Memento