Alex Kozak provided another SQL puzzle to hone your SQL Skills with. Entries are now closed and the winner is announced at the end of the article
Many DBAs and developers, at least those that have their servers and applications well under control, may be familiar with the popular, and rather addictive, PC and Xbox games such as Bejeweled and Jewel Quest. They belong to the group of 'match 3' puzzles that are played on grids of different sizes, though typically 8x8. The grid cells are filled with tokens, such as gems or coins, of various shapes and colours and the basic idea is to create horizontal or vertical rows containing a minimum of three matching tokens, by swapping adjacent tokens in the grid. For example, in the 'bejewelled' puzzle shown in Figure 1, we can create a sequence of three blue stones in the second row of the grid by swapping the highlighted red stone with the blue one directly below it:
Figure 1. Bejeweled puzzle
All swaps must be done vertically or horizontally and only swaps that create a sequence of at least three tokens of the same kind, in a column or row, are permitted. When a successful swap is made, the sequence of collected tokens disappears, creating holes (gaps) in the grid. The tokens above these holes immediately cascade down to fill these holes, in turn creating holes in the top cells in the corresponding columns, which are filled by randomly-generated new tokens. The more tokens a player can make disappear in a single swap, the more points the player gets and the faster he can advance to the next level.
After each swap, the game engine assesses the situation on the game board and if no further valid moves can be made, the game is over. In timed variants, the game can be also terminated if time expires. If valid moves exist, but a player does not make it during a certain time, or if a player presses the "Hint" button, the game engine shows the move that can be made.
The SQL Puzzle
It occurred to me that it would be a very interesting challenge to recreate a bejewled-style puzzle and solve it using SQL!
Figure 2 shows a table, called bejewelled, which represents 9x9 Bejeweled grid:
|
# |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
8 |
5 |
2 |
8 |
6 |
8 |
9 |
9 |
1 |
|
2 |
3 |
8 |
6 |
4 |
9 |
3 |
6 |
9 |
6 |
|
3 |
2 |
8 |
9 |
3 |
4 |
3 |
7 |
4 |
9 |
|
4 |
1 |
9 |
4 |
5 |
7 |
9 |
9 |
5 |
6 |
|
5 |
7 |
6 |
2 |
9 |
7 |
9 |
9 |
6 |
8 |
|
6 |
5 |
2 |
9 |
6 |
5 |
8 |
6 |
8 |
9 |
|
7 |
4 |
4 |
2 |
5 |
9 |
5 |
8 |
6 |
9 |
|
8 |
5 |
9 |
9 |
3 |
7 |
7 |
6 |
2 |
6 |
|
9 |
2 |
3 |
2 |
7 |
9 |
6 |
6 |
2 |
9 |
Figure 2. Table bejeweled
The blue numbers from 1 to 9 symbolize nine different types of tokens. In this case, we are dealing only with a fixed grid, rather than one that continually adds randomly-generated tokens, but the goal is similar: you must swap adjacent tokens to create an island of three or more identical numbers in a row or column. For example, if you swap the values of columns 1 and 2 in row 1, you will create a sequence of three 8's in column 2 (rows 1, 2 and 3).
The Challenge!
So, here was the challenge! Using SQL or Transact-SQL, you needed to find all of the possible moves (horizontal and vertical) for the snapshot of Bejeweled table shown in Figure 2.
You had to present your solution in the following format:
|
Row number |
Column number |
Value |
|
1 |
1 |
8 |
|
5 |
4 |
9 |
|
Etc… |
… |
… |
You did not need to show where to move the value of the specific cell. Just show what value to move, and from what cell it should be moved.
There were no constraints on how you coded the solution: you could use any SQL and Transact-SQL statements, commands and build-in functions. SQL Server version–specific solutions (for instance, for SQL Server 2008 only) were also allowed. However you did it, you had to present your SQL code, along with a brief explanation of algorithm / implementation you used.
The script in Listing 1 allowed you to create and load table bejeweled:
Listing1. Create and load table bejewelled
IF EXISTS(SELECT * FROM sysobjects
WHERE ID = (OBJECT_ID('bejeweled')) AND xtype = 'U')
DROP TABLE bejeweled
GO
CREATE TABLE bejeweled(
[#] [tinyint] NULL,
[1] [tinyint] NULL,
[2] [tinyint] NULL,
[3] [tinyint] NULL,
[4] [tinyint] NULL,
[5] [tinyint] NULL,
[6] [tinyint] NULL,
[7] [tinyint] NULL,
[8] [tinyint] NULL,
[9] [tinyint] NULL
)
INSERT INTO bejeweled VALUES(1, 8, 5, 2, 8, 6, 8, 9, 9, 1);
INSERT INTO bejeweled VALUES(2, 3, 8, 6, 4, 9, 3, 6, 9, 6);
INSERT INTO bejeweled VALUES(3, 2 , 8, 9, 3, 4, 3, 7, 4, 9);
INSERT INTO bejeweled VALUES(4, 1, 9, 4, 5, 7, 9, 9, 5, 6);
INSERT INTO bejeweled VALUES(5, 7, 6, 2, 9, 7, 9, 9, 6, 8);
INSERT INTO bejeweled VALUES(6, 5, 2, 9, 6, 5, 8, 6, 8, 9);
INSERT INTO bejeweled VALUES(7, 4, 4, 2, 5, 9, 5, 8, 6, 9);
INSERT INTO bejeweled VALUES(8, 5, 9, 9, 3, 7, 7, 6, 2, 6);
INSERT INTO bejeweled VALUES(9, 2, 3, 2, 7, 9, 6, 6, 2, 9);
There were three winners:
- Timothy Walters - for his second solution with the offset table; He gets a $50 Amazon Voucher.
- Ryan Randall – for his first and second solutions; He gets a choice between a license for SQL Prompt and SQL Data Generator
- DrLechter – for his first and second solutions; He gets a choice between a license for SQL Prompt and SQL Data Generator
Timothy Walters's solution is very simple and elegant. Almost all of the logic has been implemented in the lookup table and that makes the solution portable and flexible.
In addition, his solution can be easiely modified in order to show the directions of the moves by adding one more column to the offset table.
Here is how it can be done:
--====== Table matches needs to be loaded only once
CREATE TABLE matches(offsetRow1 INT, offsetCol1 INT, offsetRow2 INT, ofsetCol2 INT, directions VARCHAR(20))
-- for horizontal
INSERT INTO matches VALUES(-1, -1, -1, -2, 'up')
INSERT INTO matches VALUES(-1, -1, -1, 1, 'up')
INSERT INTO matches VALUES(-1, 1, -1, 2, 'up')
INSERT INTO matches VALUES( 1, -1, 1, -2, 'down')
INSERT INTO matches VALUES( 1, -1, 1, 1, 'down')
INSERT INTO matches VALUES( 1, 1, 1, 2, 'down')
INSERT INTO matches VALUES( 0, -2, 0, -3, 'left')
INSERT INTO matches VALUES( 0, 2, 0, 3, 'right')
-- for verical
INSERT INTO matches VALUES(-2, -1, -1, -1, 'left')
INSERT INTO matches VALUES(-1, -1, 1, -1, 'left')
INSERT INTO matches VALUES( 1, -1, 2, -1, 'left')
INSERT INTO matches VALUES(-2, 1, -1, 1, 'right')
INSERT INTO matches VALUES(-1, 1, 1, 1, 'right')
INSERT INTO matches VALUES( 1, 1, 2, 1, 'right')
INSERT INTO matches VALUES(-2, 0, -3, 0, 'up')
INSERT INTO matches VALUES( 2, 0, 3, 0, 'down')
--==================================================
;WITH CTE
AS
(
SELECT
[Row] = CAST( [#] AS INT ),
[Col] = CAST( [Col] AS INT ),
[Value]
FROM bejeweled
UNPIVOT ([Value] FOR [Col] IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) unpvt
)
SELECT DISTINCT T.Row, T.Col, T.Value, directions
FROM CTE T
JOIN CTE T1
ON T.Value = T1.Value
JOIN CTE T2
ON T.Value = T2.Value
JOIN matches
ON (T1.Row - T.Row) = offsetRow1
AND (T1.Col - T.Col) = offsetCol1
AND (T2.Row - T.Row) = offsetRow2
AND (T2.Col - T.Col) = ofsetCol2
ORDER BY T.Row, T.Col
There is one more person – AmandaS that should be specially mentioned. Her second solution was very similar to Timothy Walters' and Ryan Randall's solutions, but was submitted five days later.
A few more people should be mentioned as well:
- Saharafrog – interesting solution
- Doug Stewart
- Steve Munson - his solution shows the coordinates of the cells that should be moved and the coordinates of destination cells
- RBarry Young
- Dennis A
- SkyBeaver