Katkat
Back

Enumerate 4x4 Tic-Tac-Toe Games

DecagonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of recursion and backtracking, exhaustive game-tree enumeration, and state representation for combinatorial game analysis.

You are given an empty $4 \times 4$ board. Two players, X and O, alternate turns with X moving first. A player wins as soon as they place three of their marks consecutively in a row, a column, or a diagonal (i.e. three-in-a-row, not four). The moment a player wins, the game stops — no further moves are made.

Write a program that uses recursion and backtracking to enumerate every valid game sequence, starting from the empty board and ending at a terminal state. A state is terminal when it is:

  • a win for X,
  • a win for O, or
  • a completely full board with no three-in-a-row for either player (a draw).

Your function may return either:

  1. the total count of distinct valid game sequences (each ordered list of moves from empty board to terminal state counts once), or
  2. the actual terminal boards / move sequences.

Be ready to walk through your board representation, your win check, how the recursion explores the game tree, how backtracking undoes each move, and the worst-case time complexity.

Constraints & Assumptions

  • Board is $4 \times 4$ (16 cells); each cell is empty, X, or O. The win condition is three consecutive marks, not four.
  • X always moves first; players strictly alternate.
  • A win is a length-3 window, so a single row contains two distinct length-3 windows (columns 0–2 and 1–3); the same holds for columns, and both diagonal directions have length-3 windows.
  • Two game sequences that reach the same final board via different move orders are distinct sequences (you are counting ordered play-throughs, not unique final positions) — confirm this with your interviewer, as it changes the count by orders of magnitude.
  • The search space is large enough that fully materializing every sequence in memory is impractical; prefer counting (or streaming) over storing all sequences.
  • A single-threaded reference solution is expected; you may discuss memoization/symmetry as optimizations but must justify correctness.

Clarifying Questions to Ask

  • Does a win require exactly three consecutive marks, and do four consecutive marks (which contain two overlapping threes) also count as a win?
  • Are we counting ordered game sequences (distinct move orders) or distinct terminal board positions?
  • Should the game stop on the first completed line, even if a single move completes two lines at once? (Either way it is still one win.)
  • Do we need the breakdown by outcome (X wins / O wins / draws) or just the grand total?
  • Are board symmetries (rotations/reflections) considered the same game or different?
  • What is the expected output — a single number, a generator/stream, or the full list of boards?

Hints

Hint 1

Where to start: Model one *ply* (a single placement) as the recursive unit. At depth $d$ the player to move is `X` when $d$ is even and `O` when $d$ is odd, so you can derive the mark from the depth instead of passing it. Loop over every empty cell, place the current player's mark, recurse, then **remove the mark** before trying the next cell — that removal *is* the backtracking step. The three terminal conditions are the recursion's base cases.

Hint 2

Detecting a win: Pre-compute the list of all winning lines once: every run of 3 consecutive cells horizontally, vertically, and on both diagonal directions. On a $4\times4$ board with a length-3 win there are exactly **24** such lines (8 horizontal, 8 vertical, 4 "↘", 4 "↙"). After a move at cell $p$, you only need to re-check the lines that pass through $p$ — a win can only be created by the latest mark — not the whole board.

Hint 3

Stopping conditions (don't over-count): A branch terminates the instant the just-placed mark completes a line (record it and **do not recurse further** — the game is over) *or* when the board fills with no winner. Forgetting the "stop immediately on win" rule keeps filling cells past a win and double-counts sequences a real game would never reach.

Hint 4

Make it fast: Represent the board as two integer bitmasks (one per player) and each winning line as a bitmask. A win is then a single test: `(player_mask & line_mask) == line_mask`. This replaces per-cell scans with O(1) bitwise checks and makes the search dramatically faster than a nested-list scan.

Follow-up questions

  • How would you **validate** your enumerator against a known baseline, and what would that baseline be?
  • How would you split the outcome counts into `X` wins, `O` wins, and draws, and what should you expect about their relative sizes given `X` moves first?
  • The full $4\times4$ enumeration is expensive in an interpreted language. How would you make it tractable — bitmasks, exploiting board symmetry to collapse the first move into equivalence classes, parallelizing subtrees, or porting the inner loop to a compiled language?
  • If you only needed the count of distinct *terminal boards* (ignoring move order), how would your approach change, and how would you deduplicate, including under rotations/reflections?