Design tic-tac-toe: an N-by-N game with win detection

Design an N-by-N tic-tac-toe game for two players in code. Players take turns placing their mark; a player wins by filling a whole row, column or either diagonal. After each move the game must say whether that move won, drew or neither, and that check should be O(1), not a scan of the board.

Requirements

• Functional: create a game with board size n; move(row, col) places the current player's mark and returns the result (in progress, X wins, O wins, draw); reject moves out of range, on a taken cell, or after the game ended; turns alternate.
• Non-functional: checking a win after a move is O(1); the classes make it easy to change the win rule or add a computer player.

Interface

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

• Game(n: int); move(row: int, col: int) -> str returns "in_progress", "X_wins", "O_wins" or "draw".

g = Game(3)
g.move(0, 0) -> "in_progress"   # X
g.move(1, 1) -> "in_progress"   # O
g.move(0, 1) -> "in_progress"   # X
g.move(2, 2) -> "in_progress"   # O
g.move(0, 2) -> "X_wins"        # top row

Clarifying questions

• Does a player need n in a row, or k in a row on a larger board?
• Who goes first, and can players choose their marks?
• Should the game report a draw as soon as no one can win, or only when the board is full?
• Is undo needed?
• Is a computer opponent in scope?

What a strong answer covers

• Core classes: Game (board, players, current turn, status), Board (cells, place, is_full), Player (mark, and a MoveStrategy for human or computer), and WinChecker.
• O(1) win detection: counters per row, per column and for the two diagonals, +1 for X and -1 for O; a counter reaching n or -n means a win.
• Draw when the move count reaches n * n without a win.
• Validation and clear errors for illegal moves, and the game status as a small state machine.
• Tests: wins on a row, a column and both diagonals, a draw, a move after the game ended.

Follow-ups

• Change the rule to k in a row on an m x n board. Why do the counters no longer work, and what replaces them?
• Add a computer player that never loses on a 3x3 board.
• Add undo.