3CUnreviewed1800GPT-5.4 (high)

Tic-tac-toe

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force games implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

The board is ridiculously small. There are only $3^9 = 19683$ possible fillings, so maybe don’t write a 40-line jungle of special cases unless you enjoy pain.

A board is legal iff it can appear in some real game: players alternate, $X$ starts, and the moment someone makes a line, the game stops. That “stop immediately” rule is where a lot of fake positions die.

Try generating all legal positions by DFS/backtracking from the empty board. At each step, place the current mark in any empty cell and switch turns. But if the board already has a winner, do not continue from it.

For every reachable board, store its verdict right away: $X$ has a line $\Rightarrow$ the first player won, $0$ has a line $\Rightarrow$ the second player won, full board with no winner $\Rightarrow$ draw, otherwise it’s the current turn: first for $X$ , second for $0$ .

The whole trick is: precompute the set of all reachable boards once. Use a win(board, c) function over the $8$ possible lines. Then just look up the input board: if it was never generated, print illegal; otherwise print the stored verdict. Clean, tiny, and hard to screw up.

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:

If X already has a winning line, the game is over and the verdict is the first player won.
Else if 0 already has a winning line, the game is over and the verdict is the second player won.
Else if there is no empty cell, the verdict is draw.
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

unordered_map<string, int> state;

bool win(const string& s, char c) {
    static const int lines[8][3] = {
        {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
        {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
        {0, 4, 8}, {2, 4, 6}
    };
    for (int i = 0; i < 8; ++i) {
        if (s[lines[i][0]] == c && s[lines[i][1]] == c && s[lines[i][2]] == c) {
            return true;
        }
    }
    return false;
}

void dfs(string s, char turn) {
    if (state.count(s)) return;

    if (win(s, 'X')) {
        state[s] = 3;
        return;
    }
    if (win(s, '0')) {
        state[s] = 4;
        return;
    }
    if (s.find('.') == string::npos) {
        state[s] = 5;
        return;
    }

    state[s] = (turn == 'X' ? 1 : 2);

    for (int i = 0; i < 9; ++i) {
        if (s[i] == '.') {
            s[i] = turn;
            dfs(s, turn == 'X' ? '0' : 'X');
            s[i] = '.';
        }
    }
}

int main() {
    setIO();

    state.reserve(30000);
    dfs(".........", 'X');

    string board, row;
    for (int i = 0; i < 3; ++i) {
        cin >> row;
        board += row;
    }

    if (!state.count(board)) {
        cout << "illegal\n";
        return 0;
    }

    static const vector<string> ans = {
        "",
        "first",
        "second",
        "the first player won",
        "the second player won",
        "draw"
    };

    cout << ans[state[board]] << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

unordered_map<string, int> state;

bool win(const string& s, char c) {
    static const int lines[8][3] = {
        {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
        {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
        {0, 4, 8}, {2, 4, 6}
    };
    for (int i = 0; i < 8; ++i) {
        if (s[lines[i][0]] == c && s[lines[i][1]] == c && s[lines[i][2]] == c) {
            return true;
        }
    }
    return false;
}

void dfs(string s, char turn) {
    if (state.count(s)) return;

    if (win(s, 'X')) {
        state[s] = 3;
        return;
    }
    if (win(s, '0')) {
        state[s] = 4;
        return;
    }
    if (s.find('.') == string::npos) {
        state[s] = 5;
        return;
    }

    state[s] = (turn == 'X' ? 1 : 2);

    for (int i = 0; i < 9; ++i) {
        if (s[i] == '.') {
            s[i] = turn;
            dfs(s, turn == 'X' ? '0' : 'X');
            s[i] = '.';
        }
    }
}

int main() {
    setIO();

    state.reserve(30000);
    dfs(".........", 'X');

    string board, row;
    for (int i = 0; i < 3; ++i) {
        cin >> row;
        board += row;
    }

    if (!state.count(board)) {
        cout << "illegal\n";
        return 0;
    }

    static const vector<string> ans = {
        "",
        "first",
        "second",
        "the first player won",
        "the second player won",
        "draw"
    };

    cout << ans[state[board]] << '\n';
    return 0;
}

View on Codeforces Back to the list