Decagon AI Engineer Interview Experience — A Tic-Tac-Toe Sequence-Counting Problem in the Coding Round

I recently interviewed for Decagon's AI Engineer role, first round (the coding round), and got a question that doesn't have an exact match on LeetCode, so I wanted to share it.

Problem
Two players take turns placing marks on a 3x3 board, X goes first, then O, alternating. A game is the entire sequence of moves from an empty board to the end of the game. The game ends immediately as soon as one side gets three in a row (row, column, or diagonal), or the board fills up (a draw).

Question: how many distinct game sequences are there in total? (Order matters — even if two games end on the same final board, different move orders count as different sequences.)

Answer: 255168.

Approach
Standard backtracking / DFS over the game tree:

• Use the number of moves played so far to decide whose turn it is (even count means it's X's turn, odd count means it's O's turn)
• After each move, check whether the move just made completed a line — if so, count this as a finished game and return
• If the board is full (9 moves), count it as a draw and return
• Otherwise, recurse over all the empty squares

The number of leaves in the tree is far smaller than 9!, so it runs and returns instantly.

Follow-up: the interviewer had me estimate the order of magnitude first. Ignoring who wins and just filling the board every time gives 9! = 362880 possible sequences, as a rough upper bound.

Related problems: LC 794 / 1275 / 348.