SQL HowTo: Black and White (Puzzle Hunt 2010) / Хабр

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

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

Описание из исходного поста

Black and White — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2010 года. По сюжету игры вы преследуете загадочного участника ТВ‑шоу в надежде раскрыть его личность. Вам удается пробраться сначала на студию, а затем и в его гримерку.

«Разложите каждую из диаграмм ниже на полоски размером 1×1, 1×2 или 1×3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно‑белым паттерном, включая повороты».

Головоломка представляет собой 25 квадратных полей, расположенных в 5 рядов и 5 столбцов. В свою очередь, каждое поле разделено на 25 клеток горизонтальными и вертикальными линиями. Клетки имеют белый или черный фон, и каждая из них содержит по одной букве.

Воспользуемся рассуждениями из оригинала

Сначала определим, какие полоски мы можем использовать для решения этой задачи. Существует 6 различных полосок размером 1×3 (WWW, WWB, WBW, WBB, BWB и BBB), 3 различных полоски размером 1×2 (WW, WB и BB) и 2 различных полоски размером 1×1 (W и B). В сумме все эти полоски содержат 26 клеток. Это означает, что для разложения каждого поля придется использовать все полоски размером 1×3, все полоски размером 1×2 и только одну из полосок размером 1×1. Так как расположение полоски из 1 клетки вытекает из расположения остальных 9 полосок, то ее можно не учитывать при разложении. Стало быть, задачу можно переформулировать следующим образом: необходимо расположить на каждом поле 6 уникальных полосок размером 1×3 и 3 уникальных полоски размером 1×2 таким образом, чтобы цвета клеток поля и цвета клеток полосок совпадали.

Начнем "собирать" 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;

SQL HowTo: Black and White (Puzzle Hunt 2010)