Pull to refresh

Решение японских кроссвордов одним запросом SQL

Reading time 4 min
Views 59K
Привет хабр! Приближается день программиста, и я спешу поделиться своими ненормальными наработками.

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



Для воспроизведения запроса потребуется Oracle Database 11g или выше (12-ый на подходе). Более ранние версии не подойдут из-за применения аналитической функции listagg. Возможно использование Express Edition (XE), но этот огрызок use up to 1GB of memory, так что максимальный размер поля, которое может перелопатить эта версия — 5x4. Уже на поле 5x5 лимит памяти заканчивается.

Запрос не использует никаких реальных таблиц базы данных, готовить для него ничего не надо. Входные данные передаются в подзапросе WITH. Можно использовать предложенный кроссворд или составить свой. Для этого следует описать задание – список чисел над и слева от кроссворда, указать размер поля. Также можно по своему вкусу указать символы для заполненных и пустых ячеек.

В процессе работы строк перебрать придется много, нереально много! Поле состоит из ячеек, общим числом кол-во строк * кол-во колонок. Каждая ячейка может быть заполненной (1) или пустой (0). Тогда количество всех возможных перестановок растет нелинейно по формуле 2^(кол-во ячеек). А так как размер поля заранее не фиксирован, каждая ячейка представляется отдельной строкой. В итоге полученное число перестановок нужно умножить еще на количество ячеек. Вот, например, несколько квадратных полей:
3x3 = 4 608
4x4 = 1 048 576
5x5 = 838 860 800
6x6 = 412 316 860 416
8x8 = 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;

Tags:
Hubs:
+158
Comments 26
Comments Comments 26

Articles