SQL Tic Tac Toe Challenge

Find the winning move with SQL, for any combination!

Sep 02, 2023

The famous game of Tic Tac Toe provides a nice opportunity to practice some SQL =)

The Tic Tac Toe SQL Challenge

The challenge is to write SQL code which can indicate X’s next move - the winning move. This is for any combination on the table - horizontal, vertical or diagonal.

Gist

Some of the stuff you may expect to find in two optional solutions below:

Solution #1 uses:

CTE; Subquery; CONCAT; UNION.

It’s the simplest, most basic solution. Probably something one could be given to write during a job interview under limited time. Feel free to give yourself some 20-30 minutes to solve it if you wish to practice solving SQL question under time pressure.

Solution #2 uses:

ISNULL(); STRING_AGG(/group_concat); GROUP WITHIN; CHARINDEX; GROUP BY.

What is...?
* CHARINDEX: The CHARINDEX function searches for a substring inside a string and returns the starting position of the substring if it is found. If the substring is not found, it returns 0.

Syntax:
CHARINDEX ( substring , string [ , start_location ] )

- substring: The substring to find.
- string: The string to search within.
- start_location: Optional. The position to start searching for the substring within string.

Example: SELECT CHARINDEX('cat', 'concatenation');  -- Output: 4

What is...?
* STRING_AGG: In Transact-SQL (Microsoft SQL Server). In MySQL, it's group_concat. This function takes a column of values and concatenates them into a single string. It's useful for aggregation queries.

Syntax:
STRING_AGG ( expression, separator ) [ WITHIN GROUP ( <order_by_clause> ) ]
- expression: The expression to be concatenated.
- separator: The separator to be used between concatenated values.
- WITHIN GROUP: Optional. Sorts the values that are concatenated.

What is...?
* WITHIN GROUP: The clause is used to specify an order for an ordered-set aggregate function. This is often used in conjunction with aggregation functions like STRING_AGG to specify the order in which the aggregated strings should appear.

Syntax: 
WITHIN GROUP ( ORDER BY expression [ ASC | DESC ] )

Create & insert the data

This is the data you can use to check your code with. You may create your own as well.

As always, I use Microsoft’s SSMS (SQL Server Management Studio), so it’s in Transact SQL.

-- Create the database
CREATE DATABASE tic_tac_toe_challenge;
USE tic_tac_toe_challenge;
--
--drop table horizontal_win_1
-- Create the horizontal_win_1 table
CREATE TABLE horizontal_win_1 (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into horizontal_win_1
INSERT INTO horizontal_win_1 (row_num, A, B, C) VALUES
(1, 'O', 'X', NULL),
(2, 'X', 'X', NULL),
(3, 'O', 'O', NULL)
--
--drop table vertical_win_1
-- Create the vertical_win_1 table
CREATE TABLE vertical_win_1 (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into vertical_win_1
INSERT INTO vertical_win_1 (row_num, A, B, C) VALUES
(1, 'X', 'O', NULL),
(2, 'X', 'O', 'O'),
(3, NULL, NULL, 'X')
--
--
--drop table vertical_win_2
-- Create the vertical_win_2 table
CREATE TABLE vertical_win_2 (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into vertical_win_2
INSERT INTO vertical_win_2 (row_num, A, B, C) VALUES
(1, 'O', 'O', NULL),
(2, NULL, 'O', 'X'),
(3, 'X', NULL, 'X')
--
--drop table diagonal_win_1
-- Create the diagonal_win_1 table
CREATE TABLE diagonal_win_1 (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into diagonol_win_1
INSERT INTO diagonol_win_1 (row_num, A, B, C) VALUES
(1, 'X', 'O', NULL),
(2, 'X', 'X', 'O'),
(3, 'O', NULL, NULL)
--
--drop table diagonal_win_2
-- Create the diagonal_win_2 table
CREATE TABLE diagonal_win_2 (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into diagonal_win_2
INSERT INTO diagonal_win_2 (row_num, A, B, C) VALUES
(1, 'O', NULL, 'X'),
(2, NULL, 'X', NULL),
(3, NULL, NULL, 'O')
--
--drop table double_win_vertical_and_diagonal
-- Create the double_win_vertical_and_diagonal table
CREATE TABLE double_win_vertical_and_diagonal (
    row_num INT PRIMARY KEY,
    A VARCHAR(5),
    B VARCHAR(5),
    C VARCHAR(5)
);
-- Insert data into double_win_vertical_and_diagonal
INSERT INTO double_win_vertical_and_diagonal (row_num, A, B, C) VALUES
(1, 'X', 'X', 'O'),
(2, 'O', 'X', NULL),
(3, 'O', NULL, NULL)
;
----

SQL Solution #1

I suppose the thing about this solution is that it’s simple stupid. All you have to do is understand there are 3 options: horizontal wins, vertical wins, and diagonals. Then, there are 3 horizontal rows with 3 different options within each, and similarly same situation for the vertical ones. Finally, 2 diagonals, 3 scenarios each.

So once you write the solution for one horizontal solution, one vertical and one diagonal, you can copy paste the code and do minor edits to wrap it all up.

It’s doable for sharp cookies. Yet it would also allow managers to evaluate progress and planning, attention to details, thoroughness, cleanness of code (or ‘readability’, which could be a major factor in not making a silly mistake here), et cetera, for folks who wouldn’t necessarily finish it all up by the allotted time.

--CTE for solution breakdown and comfort
WITH tic_tac_toe AS (
SELECT *
FROM TABLE_NAME -- change name here once for chosen game table
)
, winning_move_checks AS (
-- Horizontal wins
SELECT CONCAT('PLAY ', row_num, 'A') AS WinningMove
FROM tic_tac_toe
WHERE A IS NULL AND B = 'X' AND C = 'X'
UNION
SELECT CONCAT('PLAY ', row_num, 'B') AS WinningMove
FROM tic_tac_toe
WHERE A = 'X' AND B IS NULL AND C = 'X'
UNION
SELECT CONCAT('PLAY ', row_num, 'C') AS WinningMove
FROM tic_tac_toe
WHERE A = 'X' AND B = 'X' AND C IS NULL
---- Vertical wins
-- for A column
UNION
SELECT 'PLAY 1A' AS WinningMove
FROM tic_tac_toe
WHERE A IS NULL AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 2A' AS WinningMove
FROM tic_tac_toe
WHERE A = 'X' AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 2) IS NULL AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 2) = 'X'
UNION
SELECT 'PLAY 3A' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT A FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 3) IS NULL
-- for B column
UNION
SELECT 'PLAY 1B' AS WinningMove
FROM tic_tac_toe
WHERE B IS NULL AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 2B' AS WinningMove
FROM tic_tac_toe
WHERE B = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) IS NULL AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X'
UNION
SELECT 'PLAY 3B' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT B FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 3) IS NULL
-- for C column
UNION
SELECT 'PLAY 1C' AS WinningMove
FROM tic_tac_toe
WHERE C IS NULL AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 2C' AS WinningMove
FROM tic_tac_toe
WHERE C = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 2) IS NULL AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 2) = 'X'
UNION
SELECT 'PLAY 3C' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT C FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 3) IS NULL
---- Diagonal wins
-- first diagonal
-- |[_]| ~ | ~ |
-- | ~ |[_]| ~ |
-- | ~ | ~ |[_]|
UNION
SELECT 'PLAY 1A' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT A FROM tic_tac_toe WHERE row_num = 1) IS NULL AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 2B' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT A FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) IS NULL AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 3C' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT A FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND 
	(SELECT C FROM tic_tac_toe WHERE row_num = 3) IS NULL
-- second diagonal
-- | ~ | ~ |[_]|
-- | ~ |[_]| ~ |
-- |[_]| ~ | ~ |
UNION
SELECT 'PLAY 1C' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT C FROM tic_tac_toe WHERE row_num = 1) IS NULL AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND
	(SELECT A FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 2B' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT C FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) IS NULL AND 
	(SELECT A FROM tic_tac_toe WHERE row_num = 3) = 'X'
UNION
SELECT 'PLAY 3A' AS WinningMove
FROM tic_tac_toe
WHERE (SELECT C FROM tic_tac_toe WHERE row_num = 1) = 'X' AND 
	(SELECT B FROM tic_tac_toe WHERE row_num = 2) = 'X' AND
	(SELECT A FROM tic_tac_toe WHERE row_num = 3) IS NULL
)
SELECT *
FROM winning_move_checks
;

--CTE for solution breakdown and comfort
WITH tic_tac_toe AS (
SELECT *
FROM TableName -- change name here once for chosen game table
)
-- For horizontal wins
, RowStrings AS (
    SELECT row_num,
           CONCAT(ISNULL(A, 'N'), ISNULL(B, 'N'), ISNULL(C, 'N')) AS row_string
    FROM tic_tac_toe
), horizontal_check AS (
SELECT 
    CASE 
        WHEN CHARINDEX('XXN', row_string) > 0 
         THEN CONCAT('PLAY ', row_num, 'C (horizontal)')
        WHEN CHARINDEX('XNX', row_string) > 0 
         THEN CONCAT('PLAY ', row_num, 'B (horizontal)')
        WHEN CHARINDEX('NXX', row_string) > 0 
         THEN CONCAT('PLAY ', row_num, 'A (horizontal)')
    END AS WinningMove
FROM RowStrings
WHERE row_string LIKE '%XXN%' OR 
	row_string LIKE '%XNX%' OR 
	row_string LIKE '%NXX%'
)
-- For vertical wins
, ColStrings AS (
    SELECT col_name
           ,STRING_AGG(CASE WHEN col IS NULL THEN 'N' ELSE col END, '') 
		WITHIN GROUP (ORDER BY row_num) AS col_string
    FROM (
        SELECT row_num, A as col, 'A' as col_name FROM tic_tac_toe
        UNION ALL
        SELECT row_num, B, 'B' FROM tic_tac_toe
        UNION ALL
        SELECT row_num, C, 'C' FROM tic_tac_toe
    ) AS subq
    GROUP BY col_name
)
, vertical_check AS (
SELECT CASE 
        WHEN CHARINDEX('XXN', col_string) > 0 
         THEN CONCAT('PLAY 3', col_name, ' (vertical)')
        WHEN CHARINDEX('XNX', col_string) > 0 
         THEN CONCAT('PLAY 2', col_name, ' (vertical)')
        WHEN CHARINDEX('NXX', col_string) > 0 
         THEN CONCAT('PLAY 1', col_name, ' (vertical)')
    END AS WinningMove
FROM ColStrings
WHERE col_string LIKE '%XXN%' OR 
	col_string LIKE '%XNX%' OR 
	col_string LIKE '%NXX%'
)
-- For diagonal wins
, DiagStrings AS (
-- MAIN diagonal
-- |[_]| ~ | ~ |
-- | ~ |[_]| ~ |
-- | ~ | ~ |[_]|
-- counter diagonal
-- | ~ | ~ |[_]|
-- | ~ |[_]| ~ |
-- |[_]| ~ | ~ |
SELECT 'Main' AS diag_type
, STRING_AGG(CASE WHEN col IS NULL THEN 'N' ELSE col END, '') 
	WITHIN GROUP (ORDER BY row_num) AS diag_string
    FROM (
        SELECT row_num, A as col FROM tic_tac_toe WHERE row_num = 1
        UNION ALL
        SELECT row_num, B FROM tic_tac_toe WHERE row_num = 2
        UNION ALL
        SELECT row_num, C FROM tic_tac_toe WHERE row_num = 3
    ) AS subq
    UNION ALL
SELECT 'Counter' AS diag_type
, STRING_AGG(CASE WHEN col IS NULL THEN 'N' ELSE col END, '') 
	WITHIN GROUP (ORDER BY row_num) AS diag_string
    FROM (
        SELECT row_num, C as col FROM tic_tac_toe WHERE row_num = 1
        UNION ALL
        SELECT row_num, B FROM tic_tac_toe WHERE row_num = 2
        UNION ALL
        SELECT row_num, A FROM tic_tac_toe WHERE row_num = 3
    ) AS subquery
)
, diagonal_check AS (
SELECT 
    CASE 
        WHEN diag_type = 'Main' AND CHARINDEX('XXN', diag_string) > 0 
         THEN 'PLAY 3C (main diagonal)'
        WHEN diag_type = 'Main' AND CHARINDEX('XNX', diag_string) > 0 
         THEN 'PLAY 2B (main diagonal)'
        WHEN diag_type = 'Main' AND CHARINDEX('NXX', diag_string) > 0 
         THEN 'PLAY 1A (main diagonal)'
        WHEN diag_type = 'Counter' AND CHARINDEX('XXN', diag_string) > 0 
         THEN 'PLAY 3A (counter diagonal)'
        WHEN diag_type = 'Counter' AND CHARINDEX('XNX', diag_string) > 0 
         THEN 'PLAY 2B (counter diagonal)'
        WHEN diag_type = 'Counter' AND CHARINDEX('NXX', diag_string) > 0 
         THEN 'PLAY 1C (counter diagonal)'
    END AS WinningMove
FROM DiagStrings
WHERE diag_string LIKE '%XXN%' OR 
	diag_string LIKE '%XNX%' OR 
	diag_string LIKE '%NXX%'
)
, winning_moves_checks AS (
SELECT *
FROM horizontal_check
union
SELECT *
FROM vertical_check
union
SELECT *
FROM diagonal_check
)
SELECT DISTINCT *
FROM winning_moves_checks
;

Share novsto

That’s it :) I hope you enjoyed it. Feel free to leave a comment if you’ve found an issue or got a suggestion. Alternatively, contact me via LinkedIn if you wish.