Mastering Tic‑Tac‑Toe with Oracle SQL: Generate All Endgames & Find Forced Wins

Problem Overview

The 3rd ITPUB "Shengtou Media Cup" SQL database programming contest posed two Oracle‑SQL problems based on the classic 3×3 Tic‑Tac‑Toe game. Participants must work within Oracle 10g+ without PL/SQL functions in WITH clauses, using only standard SQL features such as LISTAGG.

First Question (100 points)

Goal: generate every possible terminal move sequence ( MOVES) together with the final board layout ( BOARD) and the winner ( WINNER = X, O, or D for draw), and insert them in a single SQL statement into the table:

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

Requirements:

Only complete terminal games (no unfinished sequences) are included.

If two terminal games share the same BOARD but have different MOVES, both must appear.

Rotations or reflections that produce identical BOARD are still considered distinct if the MOVES differ.

Second Question (100 points)

Given a valid board string ( V_BOARD, 9 characters where ‘X’, ‘O’, and ‘-’ denote X, O, and empty cells), write a pure‑SQL query that determines:

The player with a forced win, if one exists.

The minimal number of additional moves the winner needs to guarantee victory (e.g., output X3 means X can force a win in at most three more moves).

Special cases:

If the board already contains a winner, output the winner with 0 moves (e.g., X0).

If no forced win exists (e.g., an empty board), output D.

The result string must not contain single quotes.

Solution Ideas for Question 1

Represent each board as a 9‑character string where positions are numbered 1‑9 left‑to‑right, top‑to‑bottom. A win occurs when any of the eight patterns (rows, columns, diagonals) appear: 123, 456, 789, 147, 258, 369, 159, 357 Using recursive SQL, enumerate all possible move orders:

Start with X placing a mark on any empty cell.

After each move, check if the current player has a winning pattern (using BITAND on a numeric board representation or string matching).

If not a terminal board, let the opponent place a mark on any remaining cell and continue recursively.

Stop when a win is detected or the board is full (draw).

During recursion store both a binary mask ( loc10 = 2^(position‑1)) and a string mask ( loc2) for each player. The combined masks ( board2, board10) allow fast win detection with BITAND(board10, baserslt) = baserslt. After generation, translate the binary masks back to the visual representation using: TRANSLATE(xloc2 || REPLACE(oloc2, '1', '2'), '012', '-XO') Finally, insert all rows with a single INSERT INTO TICTACTOE statement that selects the generated MOVES, BOARD, and WINNER.

Solution Ideas for Question 2

The forced‑win analysis proceeds in two stages:

Determine the winner for the given board by examining all possible continuations:

To compute the minimal number of moves needed, label each terminal board with WINNER plus the depth (e.g., X7 means X wins on the 7th move from the start). Propagate these labels backward through the recursion:

If the current player has at least one child labeled with its own win, choose the child with the smallest depth.

If only draw children exist, label the current board as D.

If only opponent‑win children exist, label with the opponent’s win and the largest depth (since the opponent will try to delay defeat).

Implementation in pure SQL mirrors the recursive generation from Question 1, but adds a GROUP BY on substrings of MOVES (from length 9 down to 1) to aggregate the forced‑win information for each intermediate board.

Key Technical Points

Avoid PL/SQL functions inside WITH clauses; use only built‑in SQL functions.

Use LISTAGG for string concatenation instead of the undocumented WM_CONCAT.

Leverage bitwise operations ( BITAND) for fast pattern matching.

Represent boards both as strings and as numeric bit masks to simplify recursion and win detection.