Bejeweled Puzzle Database - How Does This Solution Work?
I am interested in the programming problem presented by the game Bejeweled. It looks like a simple game, but programmatically harder than it looks.
In my quest for clues on how the board is scored, I came across this QUIZ that the good people put on Simple- Talk.They posted an answer to win, but I'm wetted and feathered if I can really understand how the solution works. I see that it has something to do with matrices and groups the cell values along with their rows and columns, but that is what I got so far. Can anyone break it down a little further for me?
REPORTING DECISION (details of the quiz are on the link above):
--====== 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
source to share
The univot function turns the original data into a linear list, not a matrix. For example, since the value of 1.1 in the original column is 8, the first row of the new table is 1.1.8. Likewise, since the second column of the first row of the original table was 5, the second row of our new table is 1,2,5.
"With CTE" effectively creates an in-memory table named CTE, so this new three-column table with 81 rows is called CTE.
The logic happens with an inner join: every cell in the CTE is joined to every cell in the CTE where the values match, and again to itself where the values match. This means that every cell in the original table knows about all three possible matches. That is, each permutation of the list of 3 cells containing the value "1" (for example) is returned.
Let's look at the value 2. In (6,2) there is another: another in (5.3) and another in (7.3), so one of the possible values of the inner union will have T. Row be 6, T. Col be 2 , T1.Row be 5, T1.Col be 3, T2.Row be 7 and T2.Col - 3. We know from looking at this that replacing (6,2) with (6,3) would put three in a row. But how is the JOIN statement known?
Well, the valid move is the one that puts T between T1 and T2. The easiest way to determine if our combination matches 3 is to check the offsets and compare them to a list of relative positions that work. T1 is above and to the right of T (-1,1) and T2 is below and to the right of T (1,1). We check if (-1,1,1,1) is a valid match. This means that it passes the JOIN criteria and is saved as a result.
source to share