Some time ago, I taught a T-SQL class in the UK. At the end of the class, a student named Paul Shipley presented me with a puzzle and asked whether I could find a T-SQL solution for it. I found the puzzle to be interesting and thought others would enjoy working on it as well. In this article, I'll present the puzzle and offer a possible solution in T-SQL. As always, I recommend that before you look at my solution you first try to come up with your own solution; otherwise, you won't enjoy the puzzle as much.
Related: T-SQL Challenge - Reoccurring Visits
Blockbusters Puzzle
The puzzle that's the focus of this article is related to a TV game show called TV game show called Blockbusters, which ran in the UK in the 1980s and early 1990s. For the purposes of this article, we'll use a modification of the game show.
In our version of the Blockbusters game show, two players take part. We'll call the players the vertical player and the horizontal player. The game involves a board of a certain dimension (e.g., 5 × 5); the tiles are square. (In the original game show, the board is 5 × 4 and the tiles are shaped as hexagons.) The tiles are marked with letters. To determine which player starts, a tile is chosen at random and a toss-up question related to the chosen letter is presented to the players. The player who buzzes first and answers the question correctly gets control over the board.
The player whose turn it is to play chooses the next tile, and the host presents a question related to that letter. If the player answers the question correctly, that tile is marked as his (we'll use the letter V to mark the tile as belonging to the vertical player and H as belonging to the horizontal player). Also, if the player answers the question correctly, he or she gets to choose the next tile. If the current player answers incorrectly, the other player gets a chance to answer the question. If neither player answers the question correctly, the host presents another trivia question related to that letter.
The goal of the game is to complete an unbroken path from one side of the board to the other. The vertical player needs to complete a vertical path (from top to bottom or bottom to top), and the horizontal player needs to complete a horizontal path (from left to right or right to left). As an example, Figure 1 shows a sample game in which the horizontal player completed a path (unbroken connection from left to right).
Figure 1: Sample Blockbusters Game
Our challenge is to write a T-SQL solution that checks whether a player completed an unbroken path. For sample data, use the code in Listing 1.
SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID('dbo.Blockbusters') IS NOT NULL DROP TABLE dbo.Blockbusters;
GO
CREATE TABLE dbo.Blockbusters
(
row INT NOT NULL
CONSTRAINT CHK_Blockbusters_row CHECK (row > 0),
col INT NOT NULL
CONSTRAINT CHK_Blockbusters_col CHECK (col > 0),
player CHAR(1) NOT NULL
CONSTRAINT CHK_Blockbusters_player CHECK (player IN ('V', 'H')),
CONSTRAINT PK_Blockbusters PRIMARY KEY(row, col)
);
CREATE UNIQUE INDEX idx_player_row_col ON dbo.Blockbusters(player, row, col);
INSERT INTO dbo.Blockbusters(row, col, player) VALUES
(1, 1, 'H'),
(1, 3, 'H'),
(1, 4, 'H'),
(1, 5, 'V'),
(2, 2, 'H'),
(2, 3, 'H'),
(2, 4, 'H'),
(2, 5, 'V'),
(3, 2, 'H'),
(3, 3, 'V'),
(3, 4, 'V'),
(3, 5, 'V'),
(4, 1, 'H'),
(4, 2, 'H'),
(4, 3, 'V'),
(4, 4, 'H'),
(4, 5, 'V'),
(5, 2, 'H'),
(5, 3, 'H'),
(5, 4, 'H'),
(5, 5, 'H');
This code creates a table called Blockbusters and populates it with data for tiles that already belong to the two players. Each row in the table holds the tile's row, col, and player (V for horizontal and H for vertical). You can use the following query to present the current state of the game pivoted:
SELECT F.row, [1],[2],[3],[4],[5] FROM (SELECT row, col, player FROM dbo.Blockbusters) AS D PIVOT(MAX(player) FOR col IN ([1],[2],[3],[4],[5])) AS P RIGHT OUTER JOIN (VALUES(1),(2),(3),(4),(5)) AS F(row) ON P.row = F.row;
This query generates the output in Figure 2.
Figure 2: Current State of Game
Your task is to write a user-defined function called IsCompleted that accepts two inputs: @player (V or H) and @size (how many rows in the board for a vertical player, or columns for a horizontal player). The function should return the bit 1 if the player in question completed an unbroken path and 0 otherwise.
Solution to Blockbusters Puzzle
You can find my complete solution with the definition of the IsCompleted function in Listing 2.
IF OBJECT_ID('dbo.IsCompleted') IS NOT NULL
DROP FUNCTION dbo.IsCompleted;
GO
CREATE FUNCTION dbo.IsCompleted(@player AS CHAR(1), @size AS INT) RETURNS BIT
AS
BEGIN
DECLARE
@grp AS INT = 0, -- each unbroken group of tiles gets a unique grp value
@iteration AS INT = 0, -- each iteration handles new neighbors of members of previous iteration
@currow AS INT = NULL,
@curcol AS INT = NULL,
@prvrow AS INT = NULL,
@prvcol AS INT = NULL;
DECLARE @T AS TABLE
(
row INT NOT NULL,
col INT NOT NULL,
grp INT NOT NULL,
iteration INT NOT NULL,
PRIMARY KEY(row, col),
UNIQUE(iteration, row, col)
);
-- find first tile of first path
SELECT TOP (1) @currow = row, @curcol = col
FROM dbo.Blockbusters
WHERE player = @player
ORDER BY row, col;
-- while a first tile of a next path exists find the related tiles in that path
WHILE @currow IS NOT NULL
BEGIN
SET @grp += 1;
SET @iteration += 1;
-- insert first tile in path
INSERT INTO @T(row, col, grp, iteration)
VALUES(@currow, @curcol, @grp, @iteration);
-- find related tiles
WHILE @@ROWCOUNT > 0
BEGIN
SET @iteration += 1;
INSERT INTO @T(row, col, grp, iteration)
SELECT DISTINCT B.row, B.col, @grp, @iteration
FROM @T AS T1
JOIN dbo.Blockbusters AS B
ON T1.iteration = @iteration - 1
AND B.player = @player
AND ( ABS(T1.row - B.row) = 1 AND T1.col = B.col
OR ABS(T1.col - B.col) = 1 AND T1.row = B.row)
AND NOT EXISTS
(SELECT *
FROM @T AS T2
WHERE T2.row = B.row AND T2.col = B.col);
END;
-- find first tile of next path
SET @prvrow = @currow;
SET @prvcol = @curcol;
SET @currow = NULL;
SET @curcol = NULL;
SELECT TOP (1) @currow = row, @curcol = col
FROM dbo.Blockbusters AS B
WHERE NOT EXISTS
(SELECT * FROM @T AS T
WHERE T.row = B.row AND T.col = B.col)
AND player = @player
AND ( row = @prvrow AND col > @prvcol
OR row > @prvrow )
ORDER BY row, col;
END;
-- if unbroken group of tiles starts with first row(for horizontal)/col(for vertical)
-- and ends with last row/col return a 1, otherwise a 0
RETURN
CASE
WHEN @player = 'H' THEN
CASE
WHEN EXISTS
(SELECT *
FROM @T
GROUP BY grp
HAVING MIN(col) = 1 AND MAX(col) = @size) THEN 1
ELSE 0
END
WHEN @player = 'V' THEN
CASE
WHEN EXISTS
(SELECT *
FROM @T
GROUP BY grp
HAVING MIN(row) = 1 AND MAX(row) = @size) THEN 1
ELSE 0
END
END;
END;
GO
The function's code assigns group numbers to the tiles of the input player and stores those values in a table variable called @T. Each unbroken group of tiles gets a unique group number. For example, suppose that the input player is the horizontal one. With the current state of the game, the function assigns group numbers for the tiles, as Figure 3 shows.
Figure 3: Group Assignment for Horizontal Player
The order in which the group numbers are assigned is based on the starting point of the group (based on row, then column order). The group whose first tile is in row 1, column 1 gets group number 1. The group whose first tile comes next (row 1, column 3) gets group number 2. And so on.
The @grp variable is used to keep track of the current group number. It's initialized with 0 and incremented whenever the code starts processing a new group. The code uses the following query to find the first tile in the first group:
SELECT TOP (1) @currow = row, @curcol = col FROM dbo.Blockbusters WHERE player = @player ORDER BY row, col;
Then it loops as long as a first tile of a new group is found (WHILE @currow IS NOT NULL). After the body of the loop is done handling the current group, the code uses the following query to get the first tile of the next group:
SELECT TOP (1) @currow = row, @curcol = col FROM dbo.Blockbusters AS B WHERE NOT EXISTS (SELECT * FROM @T AS T WHERE T.row = B.row AND T.col = B.col) AND player = @player AND ( row = @prvrow AND col > @prvcol OR row > @prvrow ) ORDER BY row, col;
The loop's body is responsible for finding all related tiles of the current group. It starts by incrementing the variables @grp and @iteration. Remember that @grp holds the current group number. Each group is handled by a number of iterations; each iteration deals with the neighbors of the tiles in the previous iteration that weren't already handled. The variable @iteration is used to associate tiles with the iteration in which they were handled.
The code continues by inserting into the table variable @T the information about the first tile in the current group:
INSERT INTO @T(row, col, grp, iteration) VALUES(@currow, @curcol, @grp, @iteration);
Next, the code uses an inner loop that in each iteration looks for neighbors of the tiles from the previous round. It iterates as long as the tiles are found in the previous round (@@ROWCOUNT > 0).
The inner loop's body increments the @iteration variable by 1. It then uses the following code to insert into the table variable @T direct neighbors of the tiles handled in the previous iteration that weren't handled before:
INSERT INTO @T(row, col, grp, iteration) SELECT DISTINCT B.row, B.col, @grp, @iteration FROM @T AS T1 JOIN dbo.Blockbusters AS B ON T1.iteration = @iteration - 1 AND B.player = @player AND ( ABS(T1.row - B.row) = 1 AND T1.col = B.col OR ABS(T1.col - B.col) = 1 AND T1.row = B.row) AND NOT EXISTS (SELECT * FROM @T AS T2 WHERE T2.row = B.row AND T2.col = B.col);
Finally, after all tiles are assigned with group numbers, the code uses a CASE expression that checks whether the input player completed an unbroken path or not. It does so by grouping the tiles by the group number and computing the minimum and maximum column numbers for a horizontal player and the minimum and maximum row numbers for a vertical player. If the minimum is equal to 1 and the maximum is equal to @size, the player completed an unbroken path. In such a case, the CASE expression returns a 1; otherwise it returns a 0.
Use the following code to test the function for both players:
SELECT dbo.IsCompleted('H', 5) AS Horizontal,
dbo.IsCompleted('V', 5) AS Vertical;
The code generates the output in Figure 4, correctly indicating that the horizontal player completed an unbroken path and the vertical player didn't.
Figure 4: State of Players
Sharpen Your Skills
Solving puzzles with T-SQL is fun and allows you to sharpen your T-SQL skills. I'd like to thank Paul for sharing this puzzle with me. I hope you had fun trying to solve it. If you're looking for another challenging puzzle, try to solve the following: Write a function that checks whether the state of the game is such that a player cannot complete an unbroken path.
