Привет хабр! Приближается день программиста, и я спешу поделиться своими ненормальными наработками. Японский кроссворд — NP-полная задача, как и задача коммивояжёра, укладки рюкзака и др. Когда ее решает человек, следует последовательно определять гарантированно заполненные и пустые ячейки. Одну за другой вычеркивать колонки и строки, пока не сложится весь рисунок. Как же возможно запрограммировать решение подобной задачи на языке, который официально даже не является языком программирования, не содержит циклов и переменных? SQL — язык запросов, его главная задача — выбирать строки. Вот мы и будем генерировать множество всех возможных перестановок и, словно скульптор, отсекать все лишнее.
Для воспроизведения запроса потребуется Oracle Database 11g или выше (12-ый на подходе). Более ранние версии не подойдут из-за применения аналитической функции listagg. Возможно использование Express Edition (XE), но этот огрызок use up to 1GB of memory, так что максимальный размер поля, которое может перелопатить эта версия — 5×4. Уже на поле 5×5 лимит памяти заканчивается.
Запрос не использует никаких реальных таблиц базы данных, готовить для него ничего не надо. Входные данные передаются в подзапросе WITH. Можно использовать предложенный кроссворд или составить свой. Для этого следует описать задание – список чисел над и слева от кроссворда, указать размер поля. Также можно по своему вкусу указать символы для заполненных и пустых ячеек.
В процессе работы строк перебрать придется много, нереально много! Поле состоит из ячеек, общим числом кол-во строк * кол-во колонок. Каждая ячейка может быть заполненной (1) или пустой (0). Тогда количество всех возможных перестановок растет нелинейно по формуле 2^(кол-во ячеек). А так как размер поля заранее не фиксирован, каждая ячейка представляется отдельной строкой. В итоге полученное число перестановок нужно умножить еще на количество ячеек. Вот, например, несколько квадратных полей:
3×3 = 4 608
4×4 = 1 048 576
5×5 = 838 860 800
6×6 = 412 316 860 416
8×8 = 1 180 591 620 717 411 303 424
Положительная сторона полного перебора – найдутся все решения. Так что, если у вас простаивают вычислительные мощности, теперь вы знаете чем их занять! Про алгоритм не рассказываю – читать нужно с конца, каждый подзапрос прокомментирован.
with INPUT as ( ----------------------------- Входные данные --------------------------------- -- Укажите список чисел задания для колонок и строк. Каждую колонку или строку -- разделяйте запятой. Группы (не более 5) внутри - пробелом. -- Если необходимо, скорректируйте размер игрового поля. -- Опционально можно указать символы-заполнители. select '2, 1 1, 1 2, 3' as FIELD_COLS, -- значения колонок слева направо '2, 1 1, 1 2, 3' as FIELD_ROWS, -- значения строк сверху вниз 4 as COL_COUNT, -- количество колонок игрового поля 4 as ROW_COUNT, -- количество строк игрового поля '#' as FILL, -- символ-заполнитель заполненной ячейки ' ' as EMPT -- символ-заполнитель пустой ячейки from dual ) -------------------------------------------------------------------------------- -- Вывод: для каждой перестановки выбирается только одна строка с ответом. select max(RES) as SOLUTION from ( -- Склейка строки с ответом (каждая ячейка перестановки содержит одно и то же) select PERM, listagg( decode(VAL, '1', FILL, EMPT) || decode(mod(CELL, COL_COUNT), 0, chr(13)) ) within group (order by PERM, CELL) over (partition by PERM) as RES from ( -- Фильтрация только возможных перестановок. select CELL, PERM, VAL from ( -- По значениям строки или колонки создается правило, например -- '1011001110' -> '1 2 3', полученное правило сверяется с исходным. -- Если правила по колонке и строке ячейки совпали, ячейка помечается -- как возможная 1, иначе 0. Если в перестановке есть хоть одна -- невозможная ячейка, все ячейки перестановки помечаются невозможными. select CELL, PERM, VAL, min( case when nvl(trim(replace( length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 1)) || ' ' || length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 2)) || ' ' || length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 3)) || ' ' || length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 4)) || ' ' || length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 5)) ,' 0', '' )), '0') = RULE_COL and nvl(trim(replace( length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 1)) || ' ' || length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 2)) || ' ' || length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 3)) || ' ' || length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 4)) || ' ' || length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 5)) ,' 0', '' )), '0') = RULE_ROW then 1 else 0 end ) over (partition by PERM) as IS_PERM_VALID from ( -- Получение значений всех ячеек, составляющих строку и колонку -- для каждой перестановки по оси X и Y, например '1011001110'. select CELL, RULE_COL, RULE_ROW, PERM, VAL, listagg(VAL) within group (order by PERM, X, CELL) over (partition by PERM, X) as VALUES_COL, listagg(VAL) within group (order by PERM, Y, CELL) over (partition by PERM, Y) as VALUES_ROW, '0*(1*)0*(1*)0*(1*)0*(1*)0*(1*)0*' as REG from ( -- Строки ячеек умножаются на строки перестановок. -- Генерация значений (1/0) каждой ячейки для каждой перестановки. select CELL, X, Y, RULE_COL, RULE_ROW, PERM, to_char(mod(trunc(PERM / power(2, CELL -1)), 2)) as VAL from ( -- Каждой ячейке выбирается соответствующее ей правило по осям X и Y -- путем извлечения подстроки динамически строящимся рег. выражением select CELL, X, Y, trim(regexp_substr( FIELD_COLS, substr(rpad('s', X * length(REG) +1, REG), 3), 1, 1, 'c', X )) as RULE_COL, trim(regexp_substr( FIELD_ROWS, substr(rpad('s', Y * length(REG) +1, REG), 3), 1, 1, 'c', Y )) as RULE_ROW from ( -- Точка входа здесь! -- Получение строк в количестве ячеек игрового поля, -- рассчет координат ячеек по осям X и Y. select LEVEL as CELL, -- номер поля mod(LEVEL -1, COL_COUNT) +1 as X, trunc((LEVEL -1) / COL_COUNT) +1 as Y, ',([^,]+)' as REG, FIELD_COLS, FIELD_ROWS from INPUT connect by LEVEL <= COL_COUNT * ROW_COUNT ) ), ( -- Генерация строк всех возможных перестановок select LEVEL -1 as PERM -- номер перестановки, начиная с 0 from INPUT connect by LEVEL <= power(2, COL_COUNT * ROW_COUNT) ) ) ) ) where IS_PERM_VALID = 1 ), ( -- Получение настроек для визуализации ответа select COL_COUNT, FILL, EMPT from INPUT ) ) group by PERM;
ссылка на оригинал статьи http://habrahabr.ru/post/192752/
Добавить комментарий