База данных Bejeweled Puzzle - Как работает это решение?

Question

Меня интересует задача программирования, представленная игрой Bejeweled. Кажется, что это простая игра, но программно она сложнее, чем кажется.

В моем поиске подсказок о том, как оценивается доска, я наткнулся на этот тест , поставленный хорошими людьми в Simple-Talk. Они опубликовали выигрышный ответ, но я очень рад, если действительно смогу понять, как работает решение. Я вижу, что это как-то связано с матрицами и группировкой значений ячеек вместе с их строками и столбцами, но это все, что я получил до сих пор. Кто-нибудь может сломать это немного дальше для меня?

РАЗМЕЩЕННОЕ РЕШЕНИЕ (подробности теста по ссылке выше):

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

Функция unpivot превращает исходные данные в линейный список, а не в матрицу. Например, поскольку значение 1,1 в исходном столбце было 8, первая строка новой таблицы равна 1,1,8. Аналогично, поскольку второй столбец первой строки исходной таблицы был 5, второй ряд нашей новой таблицы равен 1,2,5.

С помощью CTE эффективно создается таблица в памяти с именем CTE, поэтому эта новая таблица из 81 строки с тремя столбцами называется CTE.

Логика происходит с внутренним соединением: каждая ячейка в CTE соединяется с каждой ячейкой в ​​CTE, где значения совпадают, и снова с самим собой, где значения совпадают. Это означает, что каждая ячейка в исходной таблице знает о любом другом возможном совпадении из трех элементов. То есть возвращается каждая перестановка списка из 3 ячеек, содержащего значение «1» (например).

Давайте посмотрим на значение 2. Есть одно в (6,2), другое в (5,3) и другое в (7,3), поэтому одно из возможных значений внутреннего соединения будет иметь T. Строка будет 6, T.Col будет 2, T1.Row будет 5, T1.Col будет 3, T2.Row будет 7, и T2.Col будет 3. Мы знаем, глядя на это, что обмен (6,2) с ( 6,3) поставил бы три в ряд. Но как знать оператор JOIN?

Ну, действительный ход это тот, который помещает T между T1 и T2. Самый простой способ определить, соответствует ли наша комбинация 3, проверяя смещения и сравнивая это со списком относительных положений, которые работают. T1 находится выше и справа от T (-1,1), а T2 находится ниже и справа от T (1,1). Мы проверяем и видим, является ли (-1,1,1,1) действительным совпадением. Он соответствует критериям JOIN и в результате сохраняется.