Katkat
Back

Solve 3x3 Tic-Tac-Toe with Backtracking: Perfect-Play Result and Best Move

DecagonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Write a backtracking solver for 3x3 tic-tac-toe that determines the result of a given position under perfect play by both sides and returns a best move for the player to move. It tests win detection, recursive game-tree search, undoing moves correctly, and reasoning about search cost, memoization and pruning.

Write a program that solves 3×3 tic-tac-toe with backtracking, that is, by trying a move, searching everything that can follow it, and undoing the move before trying the next one.

The source reports only the game and that a standard backtracking solution was expected; the exact function contract is not reported. This practice version uses the common form of the task: given a position, determine the result of the game if both players play perfectly from that position on, and return a move for the player to move that achieves that result.

def solve(board: list[str]) -> tuple[str, tuple[int, int] | None]:
 ...
  • board holds three strings of three characters each: 'X', 'O', or '.' for an empty cell. Row 0 is the top row and column 0 is the leftmost column.
  • X always moves first, so X is to move when both players have the same number of marks, and O is to move when X has one more.
  • A player wins by filling a row, a column or a diagonal with their mark. The game ends at a win or when the board is full.
  • Return (result, move). result is "X" or "O" if that player wins with perfect play by both sides, and "draw" otherwise. move is the (row, col) of an empty cell where the player to move should play to achieve result, or None if the game is already over.

Examples:

board = ["XX.",
 "OO.",
 "..."]
result: ("X", (0, 2))

X is to move and completes the top row.

board = ["...",
 "...",
 "..."]
result: ("draw", any empty cell)

From the empty board neither player can force a win, so the result is a draw.

Constraints and Clarifications

  • Assume the position is reachable in a real game unless you choose to validate it.
  • If several moves achieve the best result, any one of them is acceptable unless you state a tie rule.

Clarifying Questions

  • Is the expected output the result of the position, a best move, both, or something else, such as the number of possible games? The source does not say.
  • Is a position given, or should the search always start from the empty board?
  • Should invalid positions be rejected, for example impossible mark counts or both players having three in a row?
  • When several moves achieve the same result, should the program prefer a faster win or a slower loss?

Hints

Hint 1

Value of a position: Define what a finished game is worth, then express what an unfinished position is worth in terms of the positions one move later, remembering whose turn it is.

Hint 2

One board, many tries: Keep a single board for the whole search. Make sure every mark you place is removed again on every path out of that step.

Follow-up questions

  • How many positions does the search visit from the empty board, and how would memoization or alpha-beta pruning change that?
  • How would you make the program prefer the fastest win and the slowest loss?
  • How would you generalize the solver to an n×n board where k in a row wins, and where does exhaustive search stop being practical?
  • Using the same backtracking, how would you count how many different complete games of tic-tac-toe can be played?