Enumerate 4x4 Tic-Tac-Toe Games

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. ```hint 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 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 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 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. ``` ### 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? ### What a Strong Answer Covers - A clear **board representation** and a justification for it (2D list, flat array, or bitmasks) with the trade-offs around mutate-and-undo vs. copy. - **Correct terminal logic**: stops immediately on a win, distinguishes win / draw, and never recurses past a terminal state. - **Efficient win detection**: only re-checks lines through the last move, or uses bitmask line tests; correctly accounts for all 24 length-3 lines on a $4\times4$ board with no off-by-one on the windows. - Textbook **backtracking discipline**: state is mutated in place and restored exactly, leaving the board unchanged for the caller. - An honest **complexity analysis**: an upper bound near $16!$ on the unpruned tree, why the "stop on win" pruning cuts this substantially, and why the result is still very large — plus the count-vs-materialize trade-off. - Awareness that the count depends entirely on the *definition* (ordered sequences vs. unique boards; three vs. four in a row) and a sanity check against a known case. ### 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?