Tic-tac-toe

Observation

This problem looks like a gross case-analysis mess: count $X$’s, count $0$’s, check winners, then remember the “game stops immediately” rule, then try not to lie to yourself. That approach works, but it’s easy to step on a rake.

The better idea is brutally simple:

• the board is only $3 \times 3$;
• each cell has $3$ states (X, 0, .);
• so there are only $$3^9 = 19683$$ possible boards.

That’s microscopic. So instead of reasoning about all legal positions, we can just generate every legal position from the rules of the game.

Generate all legal states

Start from the empty board and simulate the game with DFS/backtracking.

Let the current state be:

• a board $s$ of length $9$,
• the player to move, X or 0.

For this board:

1. If X already has a winning line, the game is over and the verdict is the first player won.
2. Else if 0 already has a winning line, the game is over and the verdict is the second player won.
3. Else if there is no empty cell, the verdict is draw.
4. Otherwise the game is still running, so the verdict is:
   • first if the next move is by X,
   • second if the next move is by 0.

Then, only in case 4, try placing the current mark into every empty cell and recurse.

The key rule is this:

Never continue from a board that already has a winner.

That automatically enforces the “game ends immediately after a win” condition. No extra garbage moves sneak in.

Why this is correct

1. Every generated board is legal

We start from the empty board, which is obviously legal.

Each DFS step:

• places the correct player’s mark in an empty cell,
• alternates turns,
• and stops the moment someone has won.

So every board we ever store is reachable in a valid game. No cheating, no post-win nonsense.

2. Every legal board is generated

Take any legal board from a real game. That game is some sequence of valid moves from the empty board.

Our DFS tries all possible moves from each non-terminal state, so it includes that exact sequence too. Therefore it will eventually generate that board.

So the set of boards produced by DFS is exactly the set of legal boards.

3. The stored verdict is the correct answer

Once a reachable board is known:

• winner exists $\Rightarrow$ corresponding player has just won;
• full and no winner $\Rightarrow$ draw;
• otherwise game is ongoing, and the DFS knows whose turn is next.

That is literally what the statement asks us to print.

So if the input board is not in the generated set, it is illegal. Otherwise, print the stored verdict.

Winning-line check

There are only $8$ lines to test:

• $3$ rows,
• $3$ columns,
• $2$ diagonals.

So win(board, c) is just checking whether any of those $8$ triples are all equal to c.

Complexity

Let $S$ be the number of distinct reachable states. Clearly,

$$S \le 3^9 = 19683.$$

Each state is processed once, and for each state we:

• check at most $8$ winning lines,
• try at most $9$ cells.

So the total complexity is

$$O(3^9),$$

with memory

$$O(3^9).$$

In human terms: instant. The board is tiny; the computer won’t even break a sweat.

Implementation notes

A neat way is to store a map:

• 1 $\to$ first
• 2 $\to$ second
• 3 $\to$ the first player won
• 4 $\to$ the second player won
• 5 $\to$ draw

Then:

• run DFS once from ......... with X to move,
• read the input board,
• if it is absent from the map, print illegal,
• otherwise print the stored verdict.

Short, clean, and way less bullshit than trying to manually plug every corner case.