SQL Challenge: Generate All Tic‑Tac‑Toe Endgames and Determine Winning Strategies

The ITPUB community recently hosted the 3rd "Shengtou Media Cup" SQL database programming contest, attracting 27 participants and judged by three experts. The competition required contestants to solve two Oracle‑centric Tic‑Tac‑Toe problems.

Problem 1: List All Terminal Games

Players X (first) and O alternate placing marks on a 3×3 grid. A MOVES string records the order of moves (positions 1‑9); a BOARD string shows the final board using X, O, and '-' for empty cells, and WINNER indicates X, O, or D (draw). The task is to generate every possible terminal MOVES (including those that end before nine moves) and the corresponding BOARD and WINNER, then insert all rows into a table.

Requirements:

Run on Oracle Database 10g or higher.

Avoid PL/SQL functions inside WITH subqueries (penalized 10 points).

Use LISTAGG for string concatenation; WM_CONCAT is prohibited.

Table definition:

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

The solution must be a single SQL statement that can be appended after INSERT INTO TICTACTOE to insert all valid rows in one execution.

Problem 2: Forced‑Win Analysis

Given a valid board state (e.g., V_BOARD='X-0------'), write an SQL query that determines which player has a forced winning strategy and the maximum number of additional moves that player needs to guarantee victory. The output format is a string such as X3 (X wins in at most three more moves), O0 if the winner is already decided, or D when no forced win exists (e.g., an empty board). The query should be executed in sqlplus after declaring the variable:

VAR v_BOARD VARCHAR2(9);
EXEC :v_BOARD := 'X-O------';
-- then run the query that returns the result string

Additional Challenge

If the same SQL logic can handle the generic m,n,k game (any board size m×n where a line of k marks wins) for k≥3, an extra 10 points are awarded.

Solution Highlights from a Contestant

The author initially tried a recursive WITH approach combined with BITAND to detect the eight possible winning lines, and experimented with board rotations for efficiency. Later, recognizing that self‑joins outperform recursive queries, they switched to a self‑join solution that builds temporary tables and uses UNION ALL to generate all endgames.

For the second problem, after several failed attempts, they adopted a weight‑based heuristic inspired by minimax strategies found online, encoding the board into numeric weights to decide the forced winner. Although the implementation is verbose, it produces the required Xn / On / D output without relying on PL/SQL functions.

Overall, the contestant reflected that the contest sharpened both SQL programming skills and algorithmic thinking.