SQL Tic‑Tac‑Toe Challenge: Generate All Endgames and Find Forced Wins

Problem Overview

The 3rd ITPUB “Shengtou Media Cup” featured a SQL programming contest based on the classic 3×3 Tic‑Tac‑Toe game. Players alternate placing O (circle) and X (cross) on a 9‑cell board, with X always moving first. A MOVES string records the sequence of cell numbers (1‑9) played until a win or a full board; a BOARD string shows the final board using X, O and ‘‑’ for empty cells.

Task 1 – Enumerate All Terminal Games

Write a single Oracle‑SQL statement that creates the table

CREATE TABLE TICTACTOE (MOVES VARCHAR2(9) PRIMARY KEY, BOARD VARCHAR2(9), WINNER VARCHAR2(1));

and inserts every possible terminal MOVES string together with its corresponding BOARD and the winner (X, O, or D for draw). The solution must run on Oracle Database 10g or later, avoid PL/SQL functions inside WITH clauses, and use only standard functions such as LISTAGG for string aggregation.

Task 2 – Determine Forced Win Strategy

Given a valid board state (variable V_BOARD of type VARCHAR2(9)), write a query that returns a compact result string: Xn – X can force a win in n additional moves. On – O can force a win in n additional moves. D – No forced win exists (draw).

If the board already contains a winner, the output should be the winner’s symbol followed by 0 (e.g., X0). The query must assume both players play perfectly and should not count the opponent’s moves in the “remaining moves” count.

Environment and Constraints

Oracle Database 10g+; avoid PL/SQL in WITH clauses (penalized 10 points if used).

String concatenation must use LISTAGG; WM_CONCAT is prohibited.

If you lack an Oracle test environment, the Oracle 10g/11g download page is referenced.

Solution Approach (Summary of Author’s Method)

Model the board using regular expressions to count X and O pieces ( X_CNT, O_CNT) and determine the current player.

Recursively generate all possible continuations from the given board (similar to Task 1) using a hierarchical query; store each node’s move sequence ( MOVES) and board ( BOARD).

Apply pruning: discard branches where a player could win earlier than the recorded depth (e.g., a two‑move win that is delayed to three moves).

Use a minimax evaluation at leaf nodes: assign values X‑win = 3, draw = 1, O‑win = 0. Propagate these values upward, selecting the maximum for X’s turn and the minimum for O’s turn.

After computing node values, walk back from the root to determine the minimal number of additional moves required for the forced win, outputting the result in the required ‘Xn’/‘On’/‘D’ format.

The author notes that both tasks require careful handling of symmetry (rotations and reflections are considered distinct) and that the recursive SQL leverages the MODEL clause to simulate game tree expansion.