SQL HowTo: Black and White (Puzzle Hunt 2010)

Некоторые головоломки можно решать на SQL just for fun, а часть получается выразить на этом декларативном языке даже эффективнее других, императивных.

Попробовать сделать более наглядное решение, а заодно познакомить с некоторыми нетривиальными возможностями PostgreSQL меня натолкнул пост о решении на Python задачи Black and White.

Начнем «собирать» CTE для запроса-решателя с перечисления всех допустимых полосок:

-- перечисляем возможные по условию полоски , blks AS ( SELECT * FROM unnest(ARRAY['www', 'wwb', 'wbw', 'wbb', 'bwb', 'bbb', 'ww', 'wb', 'bb']) WITH ORDINALITY T(blk, i) -- автонумерация строк )

Мы воспользовались функцией unnest для перевода массива в список строк с их автонумерацией с помощью WITH ORDINALITY:

blk  | i text | bigint www  | 1 wwb  | 2 wbw  | 3 wbb  | 4 bwb  | 5 bbb  | 6 ww   | 7 wb   | 8 bb   | 9

Я целенаправленно вынес вперед более длинные «полоски» по 3 клетки, чтобы уменьшить объем перебора, — ведь их размещений их на поле заведомо меньше, чем у коротких.

Матрица поля

-- переводим "матрицу" в координаты , grid AS ( SELECT x ,y ,c[1] FROM ( VALUES(' bwwbb bwwbw wbwbw bwbbb bwbww ') -- исходная "матрица" поля ) T(src) ,regexp_matches(src, '[bw]+', 'g') WITH ORDINALITY y(line, y) -- выделяем и нумеруем строки ,regexp_matches(line[1], '[bw]', 'g') WITH ORDINALITY x(c, x) -- нумеруем клетки и получаем их значения )

Регулярными выражениями (функция regexp_matches) мы получаем из текстового представления поля значения в каждой координатной клетке:

x      | y      | c bigint | bigint | text      1 |      1 | b      2 |      1 | w      3 |      1 | w      4 |      1 | b      5 |      1 | b      1 |      2 | b      2 |      2 | w      3 |      2 | w      4 |      2 | b ...

Строки «по столбцам»

Чтобы удобнее определять наложение полосок на поле не только «по горизонтали», но и «по вертикали», сформируем текстовое представление для каждого из столбцов (ну и для строк заодно):

-- формируем массивы строк/столбцов , grid_both AS ( SELECT array_agg(line ORDER BY x) FILTER(WHERE y IS NOT NULL) gridh ,array_agg(line ORDER BY y) FILTER(WHERE x IS NOT NULL) gridv FROM ( SELECT x ,y ,string_agg(c, '' ORDER BY x, y) line FROM grid GROUP BY GROUPING SETS (x, y) ) T )

С помощью наборов группирования мы «сложили» строки сразу в обеих проекциях:

x      | y      | line bigint | bigint | text      1 |        | bbwbb      2 |        | wwbww      3 |        | wwwbb      4 |        | bbbbw      5 |        | bwwbw        |      1 | bwwbb        |      2 | bwwbw        |      3 | wbwbw        |      4 | bwbbb        |      5 | bwbww

… а затем превратили их в два массива, разложив на строки сразу и оригинальную «матрицу» и транспонированную:

gridh                           | gridv text[]                          | text[] {bwwbb,bwwbw,wbwbw,bwbbb,bwbww} | {bbwbb,wwbww,wwwbb,bbbbw,bwwbw}

Возможные размещения

Вместо попыток «положить» плитку на подходящие по узору клетки поля мы будем решать обратную задачу — для каждой клетки сформируем все возможные горизонтальные/вертикальные полоски длин 2 и 3

-- формируем для каждой координаты все варианты горизонтальных (вправо) и вертикальных (вниз) полосок длин 2 и 3 , placement AS ( SELECT x ,y ,ln ,d ,blk FROM grid_both ,generate_subscripts(gridh, 1) y -- перебираем индексы массивов ,generate_subscripts(gridv, 1) x ,unnest(ARRAY[2, 3]) ln ,LATERAL ( VALUES ('h', substr(gridh[y], x, ln)) -- формируем горизонтальную ... ,('v', substr(gridv[x], y, ln)) -- ... и вертикальную полоски ) T(d, blk) WHERE length(blk) = ln -- отсекаем "вылезшие" за границы поля )

Поскольку «полоску» мы нарезали функцией substr, то при выходе за границы поля, ее длина окажется меньше желаемой, и лишнее сразу отсекается:

x | y | ln | d | blk 1 | 1 |  2 | h | bw 1 | 1 |  3 | h | bww 1 | 1 |  2 | v | bb 1 | 1 |  3 | v | bbw 1 | 2 |  2 | h | bw 1 | 2 |  3 | h | bww 1 | 2 |  2 | v | bw ...

Рекурсивный перебор возможных размещений

Итак, для каждой полоски в исходном наборе мы можем попробовать «положить» ее в доступное место в «прямом» или «зеркальном» положении. Для подходящего размещения заполним массив занимаемых ячеек и их принадлежность. Применим тот же подход, что и в предыдущем решении: если у массивов уже занятых и занимаемых на этом шаге ячеек нет пересечений — можно разместить полоску, а координаты ее ячеек — добавить:

-- рекурсивно для каждой полоски перебираем варианты ее размещения , r AS ( SELECT 1::bigint i ,'{}'::text[] acc_cell -- массив занятых ячеек ,'{}'::text[] acc_blk -- принадлежность занятых ячеек UNION ALL SELECT i + 1 ,acc_cell || fill_cell ,acc_blk || fill_blk FROM r JOIN blks USING(i) JOIN placement p ON p.blk IN (blks.blk, reverse(blks.blk)) -- прямое и зеркальное размещение , LATERAL ( SELECT array_agg(ARRAY[cx, cy]::text) fill_cell ,array_agg(ARRAY[cx, cy, i]::text) fill_blk FROM -- набор координат ячеек, занимаемых полоской generate_series(0, ln - 1) j ,LATERAL ( SELECT CASE d WHEN 'h' THEN x + j WHEN 'v' THEN x END cx ,CASE d WHEN 'h' THEN y WHEN 'v' THEN y + j END cy ) T ) T WHERE NOT (fill_cell && acc_cell) -- планируемое размещение не имеет пересечений )

Массив занятых ячеек содержит текстовые преставления пар координат [x, y], а принадлежность ячейки конкретной полоске определяется триплетом [x, y, i]:

i      | acc_cell                              | acc_blk bigint | text[]                                | text[]      1 | {}                                    | {}      2 | {{3,1},{3,2},{3,3}}                   | {{3,1,1},{3,2,1},{3,3,1}}      3 | {{3,1},{3,2},{3,3},{2,1},{2,2},{2,3}} | {{3,1,1},{3,2,1},{3,3,1},{2,1,2},{2,2,2},{2,3,2}} ...

Как можно заметить, первая полоска www легла в единственное допустимое место по координатам [3;1] вертикально вниз, а следующая wwb — в [2;1].

Матрица заполнения

Пойдем на допущение, что искомая комбинация размещения — единственная. Тогда достаточно взять массив принадлежности из строки с наибольшим номером и «развернуть» в строки-ячейки:

-- переводим массив в координаты , grid_fill AS ( SELECT cell[1] x ,cell[2] y ,cell[3] i FROM unnest(( -- разворачиваем финальное размещение SELECT acc_blk FROM r ORDER BY i DESC LIMIT 1 )) ,LATERAL ( SELECT unnest::integer[] cell -- превращаем текстовый массив в целочисленный ) T ) 

x       | y       | i integer | integer | integer       3 |       1 |       1       3 |       2 |       1       3 |       3 |       1       2 |       1 |       2       2 |       2 |       2       2 |       3 |       2       2 |       5 |       3 ...

Вывод матрицы

Можно просто определить координаты «отсутствующей» клетки, но мы для самопроверки соберем красивый вывод, демонстрируя какой полоской какая ячейка накрыта, на забыв подменить единственную незаполненную ячейку на '.':

SELECT string_agg(coalesce(i::text, '.') || c, ' ' ORDER BY x) FROM grid NATURAL LEFT JOIN grid_fill GROUP BY y ORDER BY y;

string_agg text 4b 2w 1w 9b 9b 4b 2w 1w 6b 7w 4w 2b 1w 6b 7w 5b 5w 5b 6b 8b .b 3w 3b 3w 8w

Итоговый запрос-решатель выглядит ничуть не сложнее кода на Python из оригинального поста.

-- перечисляем возможные по условию полоски WITH RECURSIVE blks AS ( SELECT * FROM unnest(ARRAY['www', 'wwb', 'wbw', 'wbb', 'bwb', 'bbb', 'ww', 'wb', 'bb']) WITH ORDINALITY T(blk, i) -- автонумерация строк ) -- переводим "матрицу" в координаты , grid AS ( SELECT x ,y ,c[1] FROM ( VALUES(' bwwbb bwwbw wbwbw bwbbb bwbww ') -- исходная "матрица" поля ) T(src) ,regexp_matches(src, '[bw]+', 'g') WITH ORDINALITY y(line, y) -- выделяем и нумеруем строки ,regexp_matches(line[1], '[bw]', 'g') WITH ORDINALITY x(c, x) -- нумеруем клетки и получаем их значения ) -- формируем массивы строк/столбцов , grid_both AS ( SELECT array_agg(line ORDER BY x) FILTER(WHERE y IS NOT NULL) gridh ,array_agg(line ORDER BY y) FILTER(WHERE x IS NOT NULL) gridv FROM ( SELECT x ,y ,string_agg(c, '' ORDER BY x, y) line FROM grid GROUP BY GROUPING SETS (x, y) ) T ) -- формируем для каждой координаты все варианты горизонтальных (вправо) и вертикальных (вниз) полосок длин 2 и 3 , placement AS ( SELECT x ,y ,ln ,d ,blk FROM grid_both ,generate_subscripts(gridh, 1) y -- перебираем индексы массивов ,generate_subscripts(gridv, 1) x ,unnest(ARRAY[2, 3]) ln ,LATERAL ( VALUES ('h', substr(gridh[y], x, ln)) -- формируем горизонтальную ... ,('v', substr(gridv[x], y, ln)) -- ... и вертикальную полоски ) T(d, blk) WHERE length(blk) = ln -- отсекаем "вылезшие" за границы поля ) -- рекурсивно для каждой полоски перебираем варианты ее размещения , r AS ( SELECT 1::bigint i ,'{}'::text[] acc_cell -- массив занятых ячеек ,'{}'::text[] acc_blk -- принадлежность занятых ячеек UNION ALL SELECT i + 1 ,acc_cell || fill_cell ,acc_blk || fill_blk FROM r JOIN blks USING(i) JOIN placement p ON p.blk IN (blks.blk, reverse(blks.blk)) -- прямое и зеркальное размещение , LATERAL ( SELECT array_agg(ARRAY[cx, cy]::text) fill_cell ,array_agg(ARRAY[cx, cy, i]::text) fill_blk FROM -- набор координат ячеек, занимаемых полоской generate_series(0, ln - 1) j ,LATERAL ( SELECT CASE d WHEN 'h' THEN x + j WHEN 'v' THEN x END cx ,CASE d WHEN 'h' THEN y WHEN 'v' THEN y + j END cy ) T ) T WHERE NOT (fill_cell && acc_cell) -- планируемое размещение не имеет пересечений ) -- переводим массив в координаты , grid_fill AS ( SELECT cell[1] x ,cell[2] y ,cell[3] i FROM unnest(( -- разворачиваем финальное размещение SELECT acc_blk FROM r ORDER BY i DESC LIMIT 1 )) ,LATERAL ( SELECT unnest::integer[] cell -- превращаем текстовый массив в целочисленный ) T ) SELECT string_agg(coalesce(i::text, '.') || c, ' ' ORDER BY x) FROM grid NATURAL LEFT JOIN grid_fill GROUP BY y ORDER BY y;