<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

289. Challenging Tic-Tac-Toe
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Qc and He play the famous game of Tic-Tac-Toe. The game is played on a 3x3 board. Qc plays with X-s, He plays with 0-s. The players make moves in turn, Qc moves first. The object of the game is to get three of your marks in a row. If there is no empty square to put the mark to, the game ends in a draw.
Given the position in a game and assuming that both Qc and He play perfectly, you have to detect who would win the game, or that the game would end in a draw. If the position given is illegal, that is, it cannot occur in the game, you must report so.

Input
The input file contains one or more test cases. Each test case consists of four lines. Each of the first three lines contains three characters, these lines describe the position on the board. The fourth line of each test case is empty.
The position on the board is specified using characters "X", "0" (zero), and "." (dot). The input file is terminated by the string containing the word "Qc" on a line by itself. You may assume that no position occurs in the input file more than once.

Output
Print one statement for each test case. Refer to the sample output for exact statements.

Sample test(s)

Input
..X
.X0
...

..X
.0.
XX0

X0X
X0.
0X.

X0X
X0X
X0X

X0X
0X0
X0X

Qc

Output
X wins.
0 wins.
Game is a draw.
Illegal position.
X wins.

<|response|>
## 1) Abridged problem statement (concise)

You are given multiple 3×3 Tic-Tac-Toe positions. Player **X** moves first, player **0** moves second, and they alternate. Both play perfectly.

For each position, output:

- `X wins.` if X will win with perfect play,
- `0 wins.` if 0 will win with perfect play,
- `Game is a draw.` if the game will end in a draw with perfect play,
- `Illegal position.` if the position cannot occur in any real game sequence (with correct turns and stopping immediately when someone wins).

Input ends with a line containing only `Qc`.

---

## 2) Key observations

1. **Tiny state space**: Each of 9 cells is `{., X, 0}` ⇒ at most \(3^9 = 19683\) boards. This is small enough to precompute.

2. **Legality is tricky to validate with ad-hoc rules** (counts, “both win”, moves after win, etc.).  
   A robust method: **generate all legal positions from the empty board** by simulating legal moves in order. Any position not generated is illegal.

3. **Perfect play = minimax**:
   - X tries to maximize outcome.
   - 0 tries to minimize outcome.

4. **Turn is determined by piece count**:
   - If number of placed marks is even ⇒ X to move.
   - If odd ⇒ 0 to move.

---

## 3) Full solution approach

### A) Encode a board as an integer (base-3)
Index cells 0..8 (row-major). Represent a board as 9 base-3 digits:

- `0` = empty `.`
- `1` = `X`
- `2` = `0`

So `state` is in `[0, 3^9)`.  
Operations needed:
- `get_cell(state, i)` = i-th base-3 digit
- `set_cell(state, i, v)` = create new state with digit i set to v (only from 0)

### B) Detect a winner
Check the 8 lines (3 rows, 3 cols, 2 diagonals).  
Return:
- `1` if X has three-in-a-row
- `2` if 0 has three-in-a-row
- `0` otherwise

### C) Precompute two arrays via DFS from the empty board
We compute for all *reachable* states:

- `reachable[state]`: can occur in a real game (legal sequence from empty, correct player order, and game stops once someone wins).
- `dp[state]`: minimax result under perfect play:
  - `1`  ⇒ X will win
  - `0`  ⇒ draw
  - `-1` ⇒ 0 will win

DFS logic from a state:
1. If already has winner: terminal `dp = 1` or `-1`, do not expand.
2. If board full: terminal `dp = 0`.
3. Else determine player by parity of placed marks:
   - If X to move: `dp[state] = max(dp[next])` over all legal moves.
   - If 0 to move: `dp[state] = min(dp[next])`.

While exploring moves, mark each `next` as reachable and DFS it once.

### D) Answer each test case
1. Encode the input board into `state`.
2. If `reachable[state] == false` ⇒ `Illegal position.`
3. Else print based on `dp[state]`.

Complexity:
- Precomputation explores only a few thousand reachable states (≪ 19683).
- Each query is O(9) to encode + O(1) lookup.

---

## 4) C++ implementation (detailed comments)

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

// Total states: 3^9
static const int STATES = 19683;

// All winning lines in flattened indexing 0..8
static const int LINES[8][3] = {
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // rows
    {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, // cols
    {0, 4, 8}, {2, 4, 6}             // diagonals
};

// dp[state] =  1 => X wins with perfect play from this position
//           =  0 => draw
//           = -1 => 0 wins
int dp[STATES];

// reachable[state] = true if this state can appear in a legal game sequence
bool reachable[STATES];

// Return i-th base-3 digit of state: 0 empty, 1 X, 2 0
int get_cell(int state, int i) {
    while (i--) state /= 3;
    return state % 3;
}

// Set i-th digit to v by adding v * 3^i (only valid if digit was 0).
int set_cell(int state, int i, int v) {
    int pw = 1;
    for (int k = 0; k < i; k++) pw *= 3;
    return state + v * pw;
}

// Return winner: 1 for X, 2 for 0, 0 for none.
int check_winner(int state) {
    for (auto &ln : LINES) {
        int a = get_cell(state, ln[0]);
        int b = get_cell(state, ln[1]);
        int c = get_cell(state, ln[2]);
        if (a != 0 && a == b && b == c) return a;
    }
    return 0;
}

// Count occupied cells (X or 0)
int count_pieces(int state) {
    int cnt = 0;
    for (int i = 0; i < 9; i++) {
        if (get_cell(state, i) != 0) cnt++;
    }
    return cnt;
}

// Precompute dp and reachable by DFS from empty board.
void precompute() {
    memset(reachable, 0, sizeof(reachable));
    reachable[0] = true;

    function<void(int)> dfs = [&](int state) {
        // Terminal: already has a winner => game would have ended earlier
        int w = check_winner(state);
        if (w != 0) {
            dp[state] = (w == 1) ? 1 : -1;
            return;
        }

        int cnt = count_pieces(state);
        // Terminal: full board => draw
        if (cnt == 9) {
            dp[state] = 0;
            return;
        }

        // Determine whose turn based on parity
        int player = (cnt % 2 == 0) ? 1 : 2; // 1 = X, 2 = 0

        // Initialize to an extreme, then minimax update.
        if (player == 1) {
            // X tries to maximize
            dp[state] = -2;
            for (int i = 0; i < 9; i++) {
                if (get_cell(state, i) == 0) {
                    int nxt = set_cell(state, i, 1);
                    if (!reachable[nxt]) {
                        reachable[nxt] = true;
                        dfs(nxt);
                    }
                    dp[state] = max(dp[state], dp[nxt]);
                }
            }
        } else {
            // 0 tries to minimize
            dp[state] = 2;
            for (int i = 0; i < 9; i++) {
                if (get_cell(state, i) == 0) {
                    int nxt = set_cell(state, i, 2);
                    if (!reachable[nxt]) {
                        reachable[nxt] = true;
                        dfs(nxt);
                    }
                    dp[state] = min(dp[state], dp[nxt]);
                }
            }
        }
    };

    dfs(0);
}

// Encode input board (3 strings of length 3) into base-3 state
int encode_board(const array<string,3>& b) {
    int state = 0;
    for (int i = 0; i < 9; i++) {
        char ch = b[i / 3][i % 3];
        if (ch == 'X') state = set_cell(state, i, 1);
        else if (ch == '0') state = set_cell(state, i, 2);
        // '.' => leave 0
    }
    return state;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    array<string,3> b;
    while (true) {
        if (!(cin >> b[0])) return 0;
        if (b[0] == "Qc") break;
        cin >> b[1] >> b[2];

        int state = encode_board(b);

        if (!reachable[state]) {
            cout << "Illegal position.\n";
        } else if (dp[state] == 1) {
            cout << "X wins.\n";
        } else if (dp[state] == -1) {
            cout << "0 wins.\n";
        } else {
            cout << "Game is a draw.\n";
        }
    }
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
sys.setrecursionlimit(1_000_000)

STATES = 3 ** 9  # 19683

LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),  # rows
    (0, 3, 6), (1, 4, 7), (2, 5, 8),  # cols
    (0, 4, 8), (2, 4, 6)              # diagonals
]

# Precompute powers of 3 to access base-3 digits quickly
pow3 = [1] * 9
for i in range(1, 9):
    pow3[i] = pow3[i - 1] * 3

# dp[state] in {1,0,-1}: X win / draw / 0 win under perfect play
dp = [0] * STATES

# reachable[state] true iff state is achievable by legal play from empty board
reachable = [False] * STATES


def get_cell(state: int, i: int) -> int:
    """Return the i-th base-3 digit: 0 empty, 1 X, 2 0."""
    return (state // pow3[i]) % 3


def set_cell(state: int, i: int, v: int) -> int:
    """
    Return new state with i-th digit set to v (assumes it was 0).
    Because digit was 0, setting is just adding v * 3^i.
    """
    return state + v * pow3[i]


def check_winner(state: int) -> int:
    """Return 1 if X wins, 2 if 0 wins, else 0."""
    for a, b, c in LINES:
        va = get_cell(state, a)
        if va != 0 and va == get_cell(state, b) and va == get_cell(state, c):
            return va
    return 0


def count_pieces(state: int) -> int:
    """Count how many cells are non-empty."""
    cnt = 0
    for i in range(9):
        if get_cell(state, i) != 0:
            cnt += 1
    return cnt


def precompute():
    """
    DFS from the empty board:
    - marks exactly the legal reachable states,
    - computes minimax dp value for each visited state.
    """
    reachable[0] = True

    def dfs(state: int):
        w = check_winner(state)
        if w != 0:
            # Terminal: someone already won
            dp[state] = 1 if w == 1 else -1
            return

        cnt = count_pieces(state)
        if cnt == 9:
            # Terminal: full board => draw
            dp[state] = 0
            return

        player = 1 if (cnt % 2 == 0) else 2  # 1=X, 2=0

        if player == 1:
            best = -2
            for i in range(9):
                if get_cell(state, i) == 0:
                    nxt = set_cell(state, i, 1)
                    if not reachable[nxt]:
                        reachable[nxt] = True
                        dfs(nxt)
                    best = max(best, dp[nxt])
            dp[state] = best
        else:
            best = 2
            for i in range(9):
                if get_cell(state, i) == 0:
                    nxt = set_cell(state, i, 2)
                    if not reachable[nxt]:
                        reachable[nxt] = True
                        dfs(nxt)
                    best = min(best, dp[nxt])
            dp[state] = best

    dfs(0)


def encode_board(rows) -> int:
    """Convert 3 strings into a base-3 state integer."""
    state = 0
    for i in range(9):
        ch = rows[i // 3][i % 3]
        if ch == 'X':
            state = set_cell(state, i, 1)
        elif ch == '0':
            state = set_cell(state, i, 2)
    return state


def main():
    precompute()

    lines = sys.stdin.read().splitlines()
    out = []
    i = 0
    while i < len(lines):
        row0 = lines[i].strip()
        i += 1
        if row0 == "Qc":
            break

        row1 = lines[i].strip(); i += 1
        row2 = lines[i].strip(); i += 1

        # There is an empty separator line per test case (as stated),
        # but be tolerant if it's missing at EOF.
        if i < len(lines) and lines[i].strip() == "":
            i += 1

        state = encode_board([row0, row1, row2])

        if not reachable[state]:
            out.append("Illegal position.")
        else:
            if dp[state] == 1:
                out.append("X wins.")
            elif dp[state] == -1:
                out.append("0 wins.")
            else:
                out.append("Game is a draw.")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()
```

If you want, I can also provide a short “sanity-check” section explaining why reachability-from-empty correctly captures all legality rules (including “no moves after someone already won”).