How to Generate All Tic‑Tac‑Toe Endgames and Forced‑Win Analysis with Oracle SQL

Problem Overview

Two players (O and X) alternately mark a 3×3 grid; X always moves first. A terminal game (MOVES) records the sequence of moves from start until a win or a full board draw. Positions are numbered 1‑9 left‑to‑right, top‑to‑bottom. The board (BOARD) is a 9‑character string using X, O, and ‘-’ for empty cells.

Challenge Requirements

The solution must run on Oracle Database 10g or higher. SQL statements should avoid PL/SQL functions inside WITH clauses (penalized 10 points). String concatenation must use listagg; the undocumented wm_concat is prohibited. If an Oracle test environment is unavailable, a download link to the Oracle Enterprise Edition is provided.

Task 1 – Insert All Possible Endgames

Create the table:

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

Then write a single SQL query that can be placed after INSERT INTO TICTACTOE to populate the table with every legal terminal move sequence, including draws (WINNER = ‘D’). The query must generate all possible MOVES strings (length ≤ 9), compute the corresponding BOARD, and determine the winner. Identical final boards with different move orders are considered distinct and must both appear. Boards that are rotations or reflections of each other are also treated as distinct.

Task 2 – Determine Forced Win

Given a valid board string stored in the variable V_BOARD (e.g., V_BOARD := 'X-0------';), write an SQL statement that returns a result string without quotes: Xn – X can force a win in at most n additional moves. On – O can force a win in at most n additional moves. X0 or O0 – the board already contains a winning line. D – no forced win exists (e.g., an empty board).

The query must declare the variable in sqlplus (e.g., var v_BOARD varchar2(9); exec :v_BOARD := 'X-O------';) and then compute the result using a single SELECT that analyses remaining moves, evaluates win conditions, and selects the minimal forced‑win depth.

Solution Sketch

First task: Generate all 4‑move prefixes via combinatorial enumeration, store them with order. For each prefix, check whether a win already occurs; if so, prune the branch. Extend surviving prefixes step‑by‑step until a terminal state is reached, recording the full MOVES, the resulting BOARD, and the winner (X, O, or D). Finally, aggregate the rows with listagg to produce a single INSERT statement.

Second task: Convert V_BOARD into a board representation, list all empty cells, and simulate each possible next move. For each simulated board, assign a weight (rank) based on how quickly it leads to a win. Traverse the game tree using the highest‑rank moves first, stopping when a forced win is identified. The depth of that win is the number of additional moves required. The final SELECT concatenates the winner symbol with the depth (or returns ‘D’ if no forced win exists).