T-SQL Puzzle

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;GOCREATE 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, playerFROM dbo.Blockbusters) AS DPIVOT(MAX(player) FOR col IN ([1],[2],[3],[4],[5])) AS PRIGHT 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;GOCREATE FUNCTION dbo.IsCompleted(@player AS CHAR(1), @size AS INT) RETURNS BITASBEGIN  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 = colFROM dbo.BlockbustersWHERE player = @playerORDER 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 = colFROM dbo.Blockbusters AS BWHERE NOT EXISTS(SELECT * FROM @T AS TWHERE T.row = B.row AND T.col = B.col)AND player = @playerAND ( row = @prvrow AND col > @prvcolOR 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, @iterationFROM @T AS T1JOIN dbo.Blockbusters AS BON T1.iteration = @iteration - 1AND B.player = @playerAND ( ABS(T1.row - B.row) = 1 AND T1.col = B.colOR ABS(T1.col - B.col) = 1 AND T1.row = B.row)AND NOT EXISTS(SELECT *FROM @T AS T2WHERE 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.