Ultimate tic-tac-toe game engine with nested boards

Implement ultimate tic-tac-toe. The board is a 3 x 3 grid of small 3 x 3 boards. Each move is placed in a cell of a small board, and the position of that cell decides which small board the opponent must play in next. Winning a small board claims its spot on the big board; three claimed spots in a row win the game.

Part 1: classic tic-tac-toe

• winner(board: list[list[str | None]]) -> str | None returns "X" or "O" when that player has three in a row on a 3 x 3 board, else None.

Part 2: the full game

Unless you agree on a different interface with the interviewer, assume:

• Small boards and cells are numbered 0..8 row by row. X moves first, then players alternate.
• play(board: int, cell: int) -> str | None makes the current player's move and returns "X" or "O" when that move wins the game, "draw" when no move is left, else None. It raises ValueError for an illegal move.
• The first move can go anywhere. After that, the player must play in the small board whose number equals the cell just played. If that board is already won or full, they may play in any open board.
• A small board is won with three in a row and then takes no more moves. A full small board with no winner belongs to nobody.

Example

play(4, 0)  ->  None         # X, centre board, top-left cell; O must play in board 0
play(0, 4)  ->  None         # O; X must play in board 4
play(3, 0)  ->  ValueError   # X tried board 3, but board 4 is required
play(4, 4)  ->  None         # X; O must play in board 4

Clarifying questions

• When the target board is won or full, may the player choose any open board?
• Does a drawn small board count for anyone on the big board?
• What should an illegal move do: raise, or return an error?
• Is there a UI, or only the game engine?

What a strong answer covers

• A clean model: nine small boards, a big board of results, whose turn it is and which board is required next.
• Move validation in one place: right board, empty cell, game not over.
• Win checks that only look at the lines through the last move, and reusing the same check for small boards and the big board.
• Edge cases: being sent to a won or full board, a draw on a small board, a move after the game ends.
• Tests for each rule, including a full game played to a win and one to a draw.

Follow-ups

• Add undo.
• Write a simple computer player. How would you search ahead?
• Generalize to N x N boards with K in a row.