Base de données Bejeweled Puzzle - Comment fonctionne cette solution?

Question

Je suis intéressé par le défi de programmation présenté par le jeu Bejeweled. Cela ressemble à un jeu simple mais par programmation c'est plus complexe que ça en a l'air.

Dans ma recherche de conseils sur la façon dont le conseil est évalué, je suis tombé sur this QUIZ mis par les gens de Simple-Talk. Ils ont posté la réponse gagnante, mais je suis goudronné et plumes si je peux vraiment comprendre comment la solution fonctionne. Je peux voir que cela a quelque chose à voir avec les matrices et le regroupement des valeurs des cellules avec leurs lignes et colonnes, mais c'est aussi loin que je l'ai fait jusqu'ici. Quelqu'un peut-il le décomposer un peu plus loin pour moi?

SOLUTION PUBLIÉE (les détails du questionnaire sont à la liaison ci-dessus):

--====== 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 

Answer 1

La fonction UNPIVOT transforme les données d'origine dans une liste linéaire plutôt qu'une matrice. Par exemple, puisque la valeur à 1,1 dans la colonne d'origine était 8, la première ligne de la nouvelle table est 1,1,8. De même, puisque la deuxième colonne de la première rangée de la table d'origine était un 5, la deuxième rangée de notre nouvelle table est 1,2,5. Le 'With CTE' crée effectivement une table en mémoire nommée CTE, de sorte que cette nouvelle table 81 colonnes à trois colonnes est appelée CTE.

La logique se produit avec la jointure interne: chaque cellule dans CTE est jointe à chaque cellule dans CTE où les valeurs correspondent, et encore avec lui-même où les valeurs correspondent. Cela signifie que chaque cellule de la table d'origine connaît toutes les autres correspondances possibles à trois éléments. C'est-à-dire que chaque permutation d'une liste de 3 cellules contenant la valeur '1' (par exemple) est retournée.

Regardons la valeur 2. Il y en a une à (6,2), une autre à (5,3) et une autre à (7,3), donc une des valeurs possibles de la jointure interne aurait T .Row être 6, T.Col être 2, T1.Row être 5, T1.Col être 3, T2.Row être 7, et T2.Col être 3. Nous savons en le regardant que l'échange (6,2) avec (6,3) mettrait les trois dans une rangée. Mais comment l'instruction JOIN sait-elle?

Eh bien, un mouvement valide est celui qui met T entre T1 et T2. La façon la plus simple de déterminer si notre combinaison de trois correspond à cela consiste à vérifier les décalages et à les comparer à une liste de positions relatives qui fonctionnent. T1 est au-dessus et à droite de T (-1,1), et T2 est en dessous et à droite de T (1,1). Nous vérifions et voyons si (-1,1,1,1) est une correspondance valide. Il est, donc il passe les critères JOIN et est conservé en conséquence.