9.7.14 — The Board Game Family: Tic-Tac-Toe, Connect Four, Snake and Ladder

"Design tic-tac-toe." "Now make the board N×N and the win condition K in a row." "Design snake and ladder."

Tic-tac-toe is the most common warm-up question in the whole of low-level design, and it is a trap dressed as a gift. It is small enough that you can finish something in five minutes, so most candidates write one class holding a char[3][3], a checkWinner() full of hard-coded index triples, and a while loop that reads from the keyboard. It works. Then the interviewer says "make it 10×10 with 5 in a row" or "add a computer player" or "let me undo the last move", and the whole thing has to be rewritten, because every one of those three requests touches the same method.

This page builds the version that absorbs all three without a rewrite, and then shows what snake and ladder — a game with no decisions in it at all — teaches that tic-tac-toe cannot.

1. The three things that must not be one class

A board game is made of three separate concerns, and the single biggest grading difference in this problem is whether you keep them apart.

Concern	What it owns	What it must not know
Board	Where the pieces are	The rules
Rules	Legal moves, when the game ends	Whose turn it is
Game	Turn order, the move log, the outcome	How a win is detected

The board is storage. It answers "what is at row 4, column 2?" and "put this here". It has no opinion about whether the move was allowed.

The rules are a policy. Given a board and a proposed move, is the move legal? Given a board and the move that was just played, is the game over, and how? Nothing in here cares whether the player is a human or a program.

The game is the loop. Whose turn is it, what happened so far, and what is the result. It asks the rules whether a move is legal and asks the rules whether the game just ended, but it never inspects the board itself.

Once those three are separate, every follow-up the interviewer has lands in exactly one of them. A bigger board is the board. A different win condition is the rules. Undo is the game. That is the whole reason for the split, and it is worth saying out loud in the interview in exactly those terms, because it tells the interviewer you are not going to have to rewrite anything.

The god-class version, which is what most people write:

class TicTacToe {
  board: string[][] = [["","",""],["","",""],["","",""]];  // (1)
  play() {                                                  // (2)
    while (true) {
      const move = readFromKeyboard();                      // (3)
      this.board[move.row][move.col] = this.currentMark;
      if (this.checkWinner()) { console.log("winner"); return; }  // (4)
      this.swapMark();
    }
  }
}

(1) The size is baked into the field initialiser, so "make it 10×10" is an edit here.

(2) The loop, the input, the rules and the output are all inside one method, so every follow-up is an edit to the same twenty lines.

(3) Reading the keyboard from inside the game means a computer player has nowhere to live. It also means the game cannot be replayed, because the moves came from somewhere that no longer exists.

(4) checkWinner will contain the eight hard-coded winning lines, which is the piece that cannot survive a change of board size.

Everything below is the same game with those four lines pulled apart.

2. The board, and how to store it

type Mark = "X" | "O";                       // (1)
type Cell = Mark | null;                     // (2)

class Board {
  readonly rows: number;
  readonly cols: number;
  #cells: Cell[];                            // (3) flat, not nested

  constructor(rows: number, cols: number) {
    this.rows = rows;
    this.cols = cols;
    this.#cells = new Array(rows * cols).fill(null);
  }

  #index(r: number, c: number): number {     // (4)
    return r * this.cols + c;
  }

  at(r: number, c: number): Cell {
    return this.inside(r, c) ? this.#cells[this.#index(r, c)] : null;   // (5)
  }

  place(r: number, c: number, mark: Mark): void {
    this.#cells[this.#index(r, c)] = mark;
  }

  inside(r: number, c: number): boolean {
    return r >= 0 && r < this.rows && c >= 0 && c < this.cols;
  }
}

(1) A union of two string literals rather than a char. A wrong mark is now a compile error rather than a runtime surprise, and this is the cheapest correctness you will ever buy.

(2) null means empty. Using the empty string for empty is the common alternative and it is worse, because the empty string is a valid string and so nothing stops it flowing into a function expecting a mark.

(3) One flat array instead of an array of arrays. It is a single allocation instead of rows + 1, the memory is contiguous so scanning is faster, and there is no way to end up with a ragged board where one row is shorter than the others. The nested version is not wrong; the flat one has fewer ways to be wrong.

(4) The one place that knows the layout. If you later switch to a bitboard, this is the method that changes and nothing above it notices.

(5) at returns null for coordinates off the board instead of throwing. That single decision removes every boundary check from the win detector in section 3, which is where the boundary bugs would otherwise live.

Other representations, and when they earn their cost.

Representation	Good for	Cost
Flat array	Everything normal	None worth naming
Nested array	Reads naturally	Ragged rows possible
Bitboard	Chess, Connect Four engines	Hard to read
Sparse map	Huge or unbounded boards	Slower per cell

A bitboard stores the board as a set of bits inside one or two integers, one bit per square, so testing a whole winning line becomes a single bitwise AND. It is how serious game engines work and it is completely wrong for an interview answer, because it trades readability for a speed nobody asked for. Mention that it exists if the interviewer asks about a game engine playing millions of positions per second; do not write it.

A sparse map from coordinate to mark matters when the board is enormous or has no fixed edge — infinite Go-moku, or a game where the board grows as pieces are placed. If the interviewer says "the board has no fixed size", this is the answer.

3. Win detection: the part everybody gets wrong first

The naive win check scans the whole board after every move. For an N×N board with K in a row, that is roughly N² positions each looking in four directions, so about 4N²K work per move. For a 3×3 board nobody notices. For 15×15 with 5 in a row, it is the reason the interviewer asked.

The insight that fixes it: a win can only involve the square that was just played. No move can complete a line that does not pass through the square it just filled, because before that move the line had a hole in it. So you never scan the board — you scan the four lines through one point.

Figure 1 — A win passes through the square just played. Count outward in both directions along each of the four axes. The work is proportional to K, the length needed to win, not to the size of the board.

const DIRECTIONS = [
  [0, 1],   // (1) horizontal
  [1, 0],   //     vertical
  [1, 1],   //     diagonal down-right
  [1, -1],  //     diagonal down-left
] as const;

function isWinningMove(board: Board, r: number, c: number, k: number): boolean {
  const mark = board.at(r, c);
  if (mark === null) return false;                       // (2)

  for (const [dr, dc] of DIRECTIONS) {
    let run = 1;                                         // (3) the new mark itself
    run += countRun(board, r, c, dr, dc, mark);          // (4) forward
    run += countRun(board, r, c, -dr, -dc, mark);        // (5) backward
    if (run >= k) return true;                           // (6)
  }
  return false;
}

function countRun(board: Board, r: number, c: number,
                  dr: number, dc: number, mark: Mark): number {
  let n = 0;
  let rr = r + dr, cc = c + dc;
  while (board.at(rr, cc) === mark) {                    // (7)
    n++;
    rr += dr;
    cc += dc;
  }
  return n;
}

(1) Four directions, not eight. Left and right are the same axis, so you count both ways along four axes rather than treating eight directions as separate.

(2) A guard for being called on an empty square. It should not happen, and returning false is better than pretending.

(3) The run starts at one because the square just played is part of it.

(4) and (5) are the same helper called with the direction and its opposite. That symmetry is why the four-direction table works.

(6) k is a parameter, so this same function is tic-tac-toe (k = 3), Gomoku (k = 5) and Connect Four (k = 4). Nothing about the board size appears anywhere in it.

(7) This is where at returning null off the board pays for itself. Walking off the edge returns null, which is not equal to mark, so the loop stops. No boundary arithmetic, no separate edge case, no off-by-one.

What it costs. Each direction walks at most K−1 steps each way, so a move costs about 8K comparisons. For 5-in-a-row that is forty comparisons regardless of whether the board is 15×15 or 1000×1000. The naive scan on a 1000×1000 board is twenty million. That gap is the entire point of the question.

A draw is not "no winner". A draw is "no winner and no legal move remains". Track the number of filled squares in the game object and compare it with rows × cols; do not scan for an empty cell. In Connect Four, where pieces stack, the same counter works but the legal move test is different — see section 5.

4. The rules, as a thing you can swap

The win check above is already general, but the rules layer is where the whole variation of the family lives, so it deserves an interface even in a small answer.

interface GameRules {
  isLegal(board: Board, move: Move, player: Player): boolean;   // (1)
  resolve(board: Board, move: Move): Placement;                 // (2)
  outcomeAfter(board: Board, placed: Placement,
               filled: number): Outcome | null;                 // (3)
}

type Outcome = { kind: "win"; player: Player } | { kind: "draw" };

(1) Is this move allowed right now? For tic-tac-toe: the square is inside the board and empty. For Connect Four: the column is inside the board and not full.

(2) Where does the piece actually land? This is the method most people do not think to separate, and it is exactly what makes Connect Four different from tic-tac-toe. In tic-tac-toe you name a square and the piece goes there. In Connect Four you name a column and the piece falls to the lowest empty row in it. Same board, same win detection, different resolution.

(3) Did that placement end the game? It gets the filled count so it can report a draw without scanning.

Connect Four is now about ten lines, which is the payoff:

class ConnectFourRules implements GameRules {
  constructor(private k = 4) {}

  isLegal(board: Board, move: Move): boolean {
    return move.col >= 0 && move.col < board.cols
        && board.at(0, move.col) === null;             // (1) top row still open
  }

  resolve(board: Board, move: Move): Placement {
    for (let r = board.rows - 1; r >= 0; r--) {        // (2) from the bottom up
      if (board.at(r, move.col) === null) return { row: r, col: move.col };
    }
    throw new Error("column full");                    // (3)
  }

  outcomeAfter(board: Board, p: Placement, filled: number): Outcome | null {
    if (isWinningMove(board, p.row, p.col, this.k))
      return { kind: "win", player: board.at(p.row, p.col) as Player };
    if (filled === board.rows * board.cols) return { kind: "draw" };
    return null;
  }
}

(1) A column is playable exactly when its top cell is still empty, which is one read rather than a scan.

(2) Gravity, spelled out: scan upward from the bottom for the first empty row. On a seven-column board this is at most six steps.

(3) Unreachable if isLegal was checked first, and it should still be here. A rule that cannot be violated by the caller today can be violated by a caller written next year, and an exception is a much better outcome than a silent wrong placement.

Tic-tac-toe's rules are the same interface with a trivial resolve that returns the square the player named. Two games, one board, one win detector, one game loop.

5. Players, and why a bot is a drop-in

The god class read the keyboard. The moment you put a Player behind an interface, a computer opponent becomes a new class rather than a rewrite.

interface Player {
  readonly mark: Mark;
  chooseMove(board: Board, rules: GameRules): Promise<Move>;   // (1)
}

class RandomBot implements Player {                             // (2)
  constructor(readonly mark: Mark, private random: RandomSource) {}
  async chooseMove(board: Board, rules: GameRules): Promise<Move> {
    const legal = allLegalMoves(board, rules);
    return legal[this.random.nextInt(legal.length)];
  }
}

(1) It returns a promise because a human player is slow and a network player is slower. Making the interface asynchronous from the start costs nothing and means a remote opponent needs no change here. This is the same reasoning as putting hardware behind a port in 9.7.8: the thing that takes unpredictable time goes behind an interface, and the game does not care which kind it got.

(2) The bot takes its randomness as a constructor argument rather than calling a global random function. That one parameter is what makes a game reproducible — feed the same seed and the same sequence of moves comes back, so a player who reports "the bot did something absurd on move 14" can send you their seed and you can watch the identical game. A global Math.random() makes that impossible.

A stronger bot is another class, which is the point. Minimax with alpha-beta pruning for tic-tac-toe, a heuristic evaluation for Connect Four, a trained policy for anything bigger — each is a Player, and the game loop never learns that anything changed. This is 9.4.12 exactly: the varying decision is behind an interface, and the caller holds the interface.

6. The game: turns, the move log, and undo

class Game {
  #board: Board;
  #players: Player[];
  #turn = 0;
  #filled = 0;
  #log: Placement[] = [];                              // (1)
  #outcome: Outcome | null = null;

  async step(): Promise<Outcome | null> {
    if (this.#outcome) return this.#outcome;           // (2)
    const player = this.#players[this.#turn];
    const move = await player.chooseMove(this.#board, this.#rules);

    if (!this.#rules.isLegal(this.#board, move, player))
      throw new IllegalMove(move);                     // (3)

    const at = this.#rules.resolve(this.#board, move); // (4)
    this.#board.place(at.row, at.col, player.mark);
    this.#log.push(at);                                // (5)
    this.#filled++;

    this.#outcome = this.#rules.outcomeAfter(this.#board, at, this.#filled);
    this.#turn = (this.#turn + 1) % this.#players.length;   // (6)
    return this.#outcome;
  }

  undo(): void {
    const last = this.#log.pop();                      // (7)
    if (!last) return;
    this.#board.clear(last.row, last.col);
    this.#filled--;
    this.#turn = (this.#turn - 1 + this.#players.length) % this.#players.length;
    this.#outcome = null;                              // (8)
  }
}

(1) The log of placements, not of requested moves. Storing where the piece actually landed is what makes undo a one-liner in Connect Four, where the requested move was a column and the landing row was computed.

(2) A finished game refuses to continue. The outcome is stored rather than recomputed, so nothing can produce a different answer later.

(3) An illegal move throws rather than being silently ignored. A human interface should ask again before calling this; a bot that produces an illegal move has a bug and should hear about it immediately.

(4) Resolve, then place. Those are two steps because in Connect Four the square the piece occupies is not the square the player named.

(5) and (6) The log grows and the turn advances by modulo, so a three-player variant is the same code.

(7) Undo is popping the log and reversing one placement. This is the smallest possible version of the undo machinery in 9.7.12: the move is its own inverse information because placing a mark on an empty square is undone by emptying it. Games where a move captures pieces — chess in 9.7.7, or Othello — need the captured pieces recorded in the log entry too, and that is the moment the log entry stops being a coordinate and becomes a command object with an undo on it (9.4.15).

(8) Clearing the outcome matters and is easy to miss. Undoing the winning move puts the game back in play, and a stale outcome would leave it permanently over.

The move log is also the replay. Board plus rules plus the log reconstructs any position, so saving a game is saving a list of coordinates rather than a serialised board, and a game that ended strangely can be replayed move by move.

7. Snake and ladder: a game with no decisions in it

Now the second half of the family, and the reason it is worth teaching next to tic-tac-toe rather than on its own: snake and ladder has no player choice at all. You roll, you move, you jump if you land on a snake or a ladder. Every player is a spectator of their own dice.

That single fact removes most of what the previous six sections were about. There is no legal-move test, no bot strategy, no minimax. What remains is the modelling, and it is more interesting than it looks.

The board is not a grid. Drawing it as a 10×10 snaking grid is a display decision. The game is one line of a hundred squares with a jump map on top:

class SnakeAndLadderBoard {
  readonly size: number;
  #jumps: Map<number, number>;                        // (1) from square → to square

  constructor(size: number, jumps: ReadonlyArray<[number, number]>) {
    this.size = size;
    this.#jumps = new Map(jumps);
    this.#validate();                                 // (2)
  }

  destinationFrom(square: number): number {
    return this.#jumps.get(square) ?? square;         // (3)
  }
}

(1) One map holds both snakes and ladders. A snake is an entry whose value is smaller than its key, a ladder is one whose value is larger, and there is no reason for two separate structures — they behave identically. Candidates who build a Snake class and a Ladder class have written two classes with the same two fields and the same behaviour, which is the clearest possible example of inheritance being used for a label rather than for behaviour (9.2.4).

(2) The board has rules about itself, and validating them in the constructor is what stops an impossible board existing at all.

(3) One lookup, with the square itself as the answer when there is no jump. No branch, no null handling upstream.

The board validation is the part interviewers actually probe, because it is where the thinking is:

No square may be both the head of a jump and the tail of another. If square 34 is the top of a ladder and also the head of a snake, a player lands on 34, climbs to 56, and the question of whether the snake also applies has no obvious answer. Ban it in the constructor.

No jump may start or end on the first or last square. A ladder from square 1 is harmless but a snake to square 1 is a design decision; a jump ending on the winning square makes winning trivial. State which you allow.

No chains. If a ladder ends where another ladder starts, does the player climb twice? Real boards forbid it, and forbidding it in the constructor is one line. If the interviewer wants chaining, it becomes a loop in destinationFrom — and then you need a cycle check, because a ladder from 20 to 40 and a snake from 40 to 20 would loop forever. Naming that risk before it is asked about is a good moment in this question.

The turn is trivial and the edge case is not:

function advance(board: SnakeAndLadderBoard, from: number, roll: number): number {
  const target = from + roll;
  if (target > board.size) return from;               // (1) overshoot: no move
  return board.destinationFrom(target);               // (2) one jump, then stop
}

(1) The exact-landing rule. Most published rules say you must land exactly on the final square, so a roll that would take you past it does not move you at all. This is the single most common thing candidates forget, and it is worth asking about explicitly, because the alternative rule — you win by reaching or passing the last square — is also common and produces a different game.

(2) One jump per move. This is where the chaining decision from the board validation shows up in the code.

The genuinely interesting question this game asks: can a player be stuck forever? For a normal board the answer is no, and the argument is worth having ready. Every roll of at least one moves you forward, snakes move you back a bounded amount, and there is always a nonzero chance of a run of rolls that reaches the end, so the game finishes with probability one. It can take a very long time — the expected number of turns on a standard board is around 39 — but it cannot be infinite. Where it can break is a badly built board: a snake whose head is one square past a point you must pass, positioned so that the exact-landing rule plus the snake creates a region you can never leave. This is why the board validates itself, and saying that connects the two halves of the answer.

Multiple players are a queue, and the only shared state is the board, which nobody writes to. Each player has a position; a turn reads the shared board and writes one player's position. That is the least contended design in this whole chapter, and it is worth noticing why: the board is immutable after construction. When the shared thing never changes, concurrency questions mostly disappear (9.5.1).

8. The dice, and why it is an interface

interface RandomSource {
  nextInt(bound: number): number;      // 0 <= result < bound
}

class Dice {
  constructor(private random: RandomSource, private sides = 6) {}
  roll(): number { return this.random.nextInt(this.sides) + 1; }
}

This looks like ceremony around Math.random() and it is not, for three reasons that are all product features rather than internal tidiness.

Replay. A game is a seed plus a list of turns. Store the seed, and any game can be reconstructed exactly — which is how a player reports "this game cheated me" and you see precisely what they saw.

Variants. Two dice, a twelve-sided die, a rule where rolling a six grants another turn. All of them are the dice's business and none of them touch the board or the turn loop. The extra-turn rule is worth noticing because it is the one that leaks: the turn loop has to ask whether the roll grants a repeat, so the dice needs to return a small result object rather than a bare number if you want that rule to be swappable.

Fairness that can be inspected. A physical die is uniform; a naive Math.random() * 6 implementation is too, but a poorly written one using modulo on a bounded generator is not. Putting the source behind an interface means the one place that matters can be written once, carefully.

9. What the interviewer will push on

"Make it N×N with K in a row." The answer they want is that the win check never scans the board — it counts outward from the square just played along four axes, so the work is about 8K comparisons no matter how big the board is. The tell for a memorised answer is a candidate who says "I would loop over the rows and columns" and then patches it; the tell for an understood one is stating up front that a win must pass through the new piece.

"Now it is Connect Four." They are checking whether your design separates the move the player names from the square the piece occupies. If those are the same thing in your model, gravity forces a rewrite. If you have a resolve step, Connect Four is a new rules class and the win detector is untouched. The common wrong answer is a new board class with a dropPiece method, which duplicates everything the board already does.

"Add a computer player." Only one answer survives here: the player is an interface and the game asks it for a move. If the game reads input directly, there is nowhere for a bot to go. Volunteering that the interface is asynchronous, so a remote player over a network needs no change either, is the extra half-step.

"Undo the last move." Pop the move log, clear the square, step the turn back, and — the part people forget — clear the stored outcome, because undoing the winning move puts the game back in play. Then the follow-up worth pre-empting: in a game with captures, the log entry has to record what was captured, at which point the entry becomes a command object rather than a coordinate.

"Why is your snake and ladder board one map?" Because snakes and ladders behave identically — both move a player from one square to another. Two classes with the same two fields and the same behaviour is inheritance used as a label. Then give the validation rules: no square is both a jump start and a jump end, no chains without a cycle check, and jumps do not touch the first or last square.

"Can a snake and ladder game go on forever?" No, on a well-formed board: every roll advances, snakes cost a bounded amount, and a finishing run always has nonzero probability, so the game terminates with probability one. It can take a long time — around 39 turns on average for the standard board — and it can only truly break if the board itself is malformed, which is the argument for validating the board in its constructor.

The thing to volunteer that nobody asks for: the exact-landing rule. Ask whether a roll that overshoots the final square moves the player or not, because both rules are in common use and they produce measurably different games. Candidates implement whichever one they remember from childhood and never mention that there is a choice. Naming an ambiguity in a game everyone thinks they know is the strongest possible signal that you read requirements rather than assume them.

Recall

• A board game splits into three things: the board (storage), the rules (legality, resolution, outcome) and the game (turn order, move log, result). Every follow-up then lands in exactly one of them.
• Store the board as a flat array with one #index method. Return null for off-board reads — it deletes every boundary check downstream.
• A win must pass through the square just played. Count outward along four axes, both directions each, so a move costs about 8K comparisons regardless of board size. Never scan the board.
• A draw is "no winner and no legal move left" — track a filled counter, do not scan for an empty cell.
• Connect Four is tic-tac-toe with a different resolve: the player names a column, the piece lands in the lowest empty row. Separating the named move from the occupied square is what makes this free.
• The player is an interface returning a promise, so a bot and a network opponent are both drop-ins.
• Undo = pop the log, clear the square, step the turn back, and clear the stored outcome. With captures, the log entry becomes a command.
• Snake and ladder has no decisions. One jump map holds snakes and ladders together; the board validates itself (no square both start and end, no chains without a cycle check). The exact-landing rule is the ambiguity to ask about.
• The dice is an interface for replay, variants and inspectable fairness — not for tidiness.

Self-test: What are the three concerns and what does each not know? Why does win detection never scan the board? What single method makes Connect Four almost free? What does undo forget to reset? Why is one map right for snakes and ladders? Which rule of snake and ladder has two common versions?

Quiz Bank

FoundationalDesign tic-tac-toe so that changing the board to 10×10 with 5 in a row, adding a computer player, and adding undo each touch exactly one part of the design.

Start with the split, because it is the whole answer. Three concerns, and each is ignorant of one of the others.

The board is storage. It answers "what is at this square" and "put this mark here". It has no opinion about whether the move was allowed, and it holds its size as constructor arguments rather than as a literal, so a 10×10 board is a different argument rather than a different class.

The rules are a policy object with three questions on it: is this move legal, where does the piece actually land, and did that placement end the game. The win length K lives here as a field.

The game owns the turn order, the log of what has been played, and the result. It asks the rules; it never inspects the board.

Now walk the three follow-ups.

A 10×10 board with 5 in a row is two constructor arguments — the board's size and the rules' K. Nothing else changes, provided the win detector was written generally, which is the next point.

A computer player is a new class implementing the Player interface, which has one method: given a board and the rules, return a move. The game already calls that method, so it never learns that the thing on the other side stopped being a person. If the game read the keyboard directly, there would be nowhere for a bot to exist and the loop would have to be rewritten.

Undo is popping the move log, clearing the square that was filled, stepping the turn counter back, and clearing the stored outcome. That last piece is the one people miss: if the move being undone was the winning move, a stale outcome leaves the game permanently over.

Two details that make the design hold up.

The board should be a flat array of rows × cols with a single private method converting a row and column into an index, and reads for coordinates outside the board should return null rather than throwing. That second choice removes every boundary check from the win detector, which is exactly where off-by-one bugs would otherwise collect.

The cell type should be Mark | null where Mark is the union "X" | "O", not a character or a string. A wrong value becomes a compile error, which is the cheapest correctness available in this problem.

And the thing that makes the whole design worth having: each of the three follow-ups landed in a different one of the three parts. That is not a coincidence — it is why the split was chosen. When you can predict which piece a change will touch, you have divided the problem along the right lines (9.3.5).

AppliedWrite the win check for an N×N board with K in a row, and explain why it does not scan the board.

The claim it rests on: a move can only complete a line that passes through the square it just filled. Before the move, any line through a different set of squares was already complete or already broken, and neither changed. So there is no reason to look anywhere else.

Four axes, not eight directions. Left and right are the same axis walked two ways, so the table holds four offset pairs — (0,1) horizontal, (1,0) vertical, (1,1) and (1,-1) for the diagonals — and each is counted in both directions.

function isWinningMove(board: Board, r: number, c: number, k: number): boolean {
  const mark = board.at(r, c);
  if (mark === null) return false;
  for (const [dr, dc] of DIRECTIONS) {
    const run = 1
      + countRun(board, r, c,  dr,  dc, mark)
      + countRun(board, r, c, -dr, -dc, mark);
    if (run >= k) return true;
  }
  return false;
}

The run starts at one for the new mark itself, then grows by however many matching marks sit immediately either side along that axis.

The helper walks until something stops it:

function countRun(board, r, c, dr, dc, mark) {
  let n = 0, rr = r + dr, cc = c + dc;
  while (board.at(rr, cc) === mark) { n++; rr += dr; cc += dc; }
  return n;
}

Why there is no boundary check in it. board.at returns null for coordinates off the board, and null is never equal to a mark, so walking off an edge ends the loop naturally. Every version of this function that throws on out-of-range coordinates ends up wrapping the loop condition in an inside() call, and that is where the off-by-one bugs live.

The cost. Each direction walks at most K−1 squares, and there are eight walks, so a move costs roughly 8K comparisons. For 5-in-a-row that is about forty comparisons whether the board is 15×15 or 1000×1000. The naive alternative — scan every position in every direction after every move — is roughly 4N²K, which on a 1000×1000 board is twenty million comparisons per move. Same result, five orders of magnitude apart, and the difference is one observation about where a win can be.

Two things to add unprompted.

The draw test does not belong in here. A draw is "no winner and no legal move left", and the game already knows how many squares are filled. Comparing a counter against rows × cols beats scanning for an empty cell, and in Connect Four the same counter still works even though the legality test is different.

This exact function is Connect Four's win check too. The only difference between the two games is which square the piece lands on, and that is a separate concern. Passing k as a parameter rather than baking in three is what buys Gomoku, Connect Four and tic-tac-toe from one function.

InterviewYou have tic-tac-toe working. The interviewer says: now it is Connect Four. What changes?

Say the conclusion first: one new rules class, and nothing else. Then justify it, because the justification is the answer.

The one real difference between the two games is that in tic-tac-toe the player names the square the piece occupies, and in Connect Four the player names a column and gravity decides the row. If your design treats "the move" and "the square" as the same thing, that difference is a rewrite. If the rules object has a resolve step that maps a requested move to a placement, it is ten lines.

resolve(board: Board, move: Move): Placement {
  for (let r = board.rows - 1; r >= 0; r--) {
    if (board.at(r, move.col) === null) return { row: r, col: move.col };
  }
  throw new Error("column full");
}

Scan upward from the bottom for the first empty row. On a seven-by-six board that is at most six reads.

Legality changes shape too, and gets simpler. A column is playable exactly when its top cell is empty, which is a single read rather than a scan:

isLegal(board, move) {
  return move.col >= 0 && move.col < board.cols && board.at(0, move.col) === null;
}

What does not change, and this is the part worth stating deliberately. The board is the same class with different dimensions. The win detector is the same function with k = 4, because it already counts outward from the square that was played and already takes the run length as a parameter. The turn loop is untouched. The move log is untouched — and it works because it stores the placement rather than the requested move, so undo knows which square to clear even though the player only named a column.

The common wrong answer is a new ConnectFourBoard class with a dropPiece(column) method. It looks reasonable and it duplicates the board's storage, its bounds logic and often its win detection, so the next variant duplicates all of it again. The board did not change; the rule for where a piece lands did.

Two extras to volunteer.

The draw condition is now reachable differently. Connect Four fills exactly as many squares as tic-tac-toe does per move, so the filled counter still works, but a full column is a common state that must be handled long before the board is full — and that is isLegal, not the outcome check.

The same seam gives you the harder variants for free. "Pop out" Connect Four, where a player may remove one of their own pieces from the bottom of a column and everything above drops, is a rules change plus a move type. It is worth mentioning, because it demonstrates that you know where the next change would land — which is the actual thing being graded.

StaffTurn this into an online multiplayer game with matchmaking, reconnection and a spectator mode. What survives from the LLD, and what is new?

Start by naming what survives, because it is most of it. The board, the rules and the win detector are pure computation over data — no input, no output, no clock. That is exactly what makes them reusable on a server, and it is worth saying explicitly that this property was bought earlier, when the keyboard read was replaced by a Player interface.

What becomes new is everything about where the truth lives, and there is only one acceptable answer: the server holds the game. A client that owns the board is a client that can be edited to win. The client sends intended moves and renders server-confirmed state, and nothing else. This is the same rule as every claim in 9.7.9: the authoritative write is on the server and the client's view is a hint.

The game object becomes a small actor. One game, one mailbox, moves processed strictly one at a time (9.5.4). Two players cannot move at once because the rules already forbid it — but two messages can arrive at once, and serialising them per game removes the whole class of problem before it starts. Nothing about the rules changes to make this work, which is the payoff for having kept them free of state.

The move log stops being an undo mechanism and becomes the transport. Since board plus rules plus log reconstructs any position exactly:

Reconnection is replaying the log to a returning client, or sending a snapshot plus the moves after it if the log is long. The client rebuilds the position with the same rules code the server ran.

Spectators are subscribers to the log. They receive the same stream and need no special path, which is why spectator mode is nearly free in this design and expensive in one that pushes rendered board images.

Dispute resolution and replays are the same log again.

Matchmaking is a separate service and should be argued as such. It pairs waiting players by rating and by waiting time, and the only thing it hands the game service is a pair of player identities and the rules to use. Keeping it separate matters because its scaling shape is completely different: matchmaking is a queue with a global view, and games are independent shards with no view of each other. Fusing them gives you a system whose game load and whose queue load cannot be scaled apart.

The three things that will actually go wrong, and the design for each.

A player disconnects mid-game. The game needs a per-turn clock and a disconnect policy — a grace period, then a forfeit or an offer of a draw. This is a real state in the game's state machine, not an error path, exactly like the noShow state in 9.7.13. Model it as a state and the reconnect case has somewhere to land.

A move arrives twice, because a client retried on a flaky connection. Give each move a client-generated identifier and make applying a move idempotent per game, so the second copy is recognised and ignored rather than played. Without this, one dropped acknowledgement costs a player their turn.

A move arrives late, after the turn has passed or the game has ended. Every move carries the turn number it believes it is answering, and the server rejects any move whose turn number does not match the current one. This is optimistic concurrency in miniature, and it is what stops a delayed packet from playing a move the player no longer wants.

What I would watch in production, since this is where such a system decays quietly: the rate of rejected moves, which measures how stale clients are; time from matchmaking to first move, which is what players experience as "the game is dead"; and the distribution of game lengths, since a sudden shift usually means a rules deploy did something nobody intended.

And the boundary worth stating. Everything above is transport, identity and lifecycle. The rules object never learned that the game went online. If it had — if the win check needed a socket, or the board knew about players' connection state — the whole design would have to be argued again for every new client. The reason it does not is the split in section 1, which is the same reason the design absorbed Connect Four.

Flashcards

FlashThe three concerns

Board (storage, no rules), Rules (legality, resolution, outcome, no turn order), Game (turns, log, result, never inspects the board). Every follow-up then lands in exactly one place.

FlashWin detection

A win must pass through the square just played. Count outward along four axes, both directions each — about 8K comparisons per move, independent of board size. Never scan the board.

FlashConnect Four in one method

resolve maps the named move to the occupied square. Tic-tac-toe returns the square itself; Connect Four scans upward from the bottom for the first empty row. Board and win detector unchanged.

FlashWhat undo forgets

Clearing the stored outcome. Undoing the winning move puts the game back in play. Also: with captures, the log entry stops being a coordinate and becomes a command.

FlashSnakes and ladders in one map

Both move a player from one square to another, so one map holds both — a snake is an entry whose value is lower. Two classes with the same fields and the same behaviour is a label, not a design.

FlashThe ambiguity to ask about

Exact landing. Does a roll that overshoots the final square move the player at all? Both rules are in common use and they produce different games. Nobody mentions it unprompted.

Next: 9.7.15 — the traffic signal, where the state machine has a safety rule that must hold even when the software has crashed.