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

    Привет хабр! Приближается день программиста, и я спешу поделиться своими ненормальными наработками.

    Японский кроссворд — 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;
    

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 26

      +53
      Месье знает толк…
        +36
        Месье крут.
          +5
          Согласен. Это гениально!
            +8
            Самый смешной и оригинальный комментарий, который только можно встретить в блоге «Ненормальное программирование».

            Пусть уже НЛО его автоматически отправляет после каждого поста.
            +9
            Брутфорс японского кроссворда?
              +2
              Да. Только обычно при брутфорсе генерируется предположение, если не проходит проверку — отбрасывается, затем следующее. В итоге времени занимает много, памяти мало. А тут и времени, и памяти требуется сразу много.
                +7
                image
              +1
              #1064 — You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'INPUT as


              Хотите нас на Oracle подсадить?

              Вопрос про возведение в степень двойки — оно работает натурально быстро в этой SQL?
                +6
                В большом количестве используются исключительно Oracle-фишки: аналитические функции, виртуальные таблицы, иерархические запросы. В других СУБД работать не будет, к сожалению. А возведение в степень далеко не самая тяжелая операция в этом запросе. Обработка регулярных выражений на миллионах строк куда весомей.

                Для отладки использовал тот самый огрызок Oracle 11 XE на домашнем компьютере (далеко не сервер). Поле 3x3 обсчитывается за 1.5 секунды, 4x4 за 6.5 минут, 5x4 почти два часа, а 5x5 я уже не смог рассчитать.
                  0
                  На какой машине?
                    0
                    Intel Core i5 2.8Ghz (XE использует только одно ядро из 4-х), про память вообще писать бессмысленно — XE использует только 1Gb, хотя в наличии все 8.
                      +2
                      Судя по всему, наш клон слабее вашей машины раза в 3)
                    +2
                    На Постгресе запуститься после подпиливания.
                  –1
                  Это круто=)
                    +12
                    Новая задача на собеседование =)
                      +6
                      На Хабре нельзя шутить на такие темы… :/ PS Плюсанул.
                        +1
                        Спасибо. В принципе у меня тоже были тяжёлые собеседования, но я отношусь к этому с юмором.
                      0
                      Мне сразу вспомнилось из «Пароль Рыба-Меч»: «А теперь взломай 1024 шифр, и у тебя 40 секунд» )

                      st-im.kinopoisk.ru/im/kadr/1/5/0/kinopoisk.ru-Swordfish-15072.jpg
                        0
                        у вас явно нехватает нагрузки на работе :)
                          +2
                          Помнится, видел решение судоку на SQL.Ru, средствами DB2. Вот
                            0
                            Автор этого решения вообще маньяк (в хорошем смысле)! Одна запись запроса весит 33 kb без комментариев, мне терпения не хватило разобрать его.
                            0
                            Круто… плюс
                              +1
                              Хм. Мсье действительно знает толк, но, учитывая, что мы говорим о oracle-sql, я бы напомнил, что даже в 10-ке есть итерации и я бы решал эту задачу посредством конструкции MODEL (если бы вообще решал её в SQL, конечно). Думаю что получилось бы эффективнее и не так нагруженно по использованию памяти. Конечно, model нельзя назвать совсем чистым sql-ем, но для этой задачи, на мой взгляд, очень даже подходит.

                              Но метод написанный автором красив.

                              PS: И, кстати, 12-ка не на подходе, она уже здесь, уже 2 месяца как.
                                0
                                Спасибо за комплимент и интересный отзыв. Если я правильно понял, конструкция MODEL помогла бы более эффективно сгенерировать строки со значениями. На asktom приведен шикарный пример расчета чисел Фибоначчи. Но не избавила бы от необходимости перебирать все перестановки, чтобы потом отфильтровать только возможные. А именно огромное число перестановок — главный тормоз. Надо бы поразбираться, никогда не применял эту конструкцию на практике.

                                В Oracle 10 отсутствует функция listagg, которая склеивает строки по группе. Можно написать ее аналог на PL/SQL. Но это убивает весь спортивный интерес. А как иначе получить все значения строки или колонки в перестановке я не придумал.

                                О, 12-ка вышла! Что-то я отстал. Специально перерыл весь спам, который мне с oracle.com шлется — ничего. Неправильный спам какой-то.
                                0
                                model очень богат разнообразным функционалом. в том числе в нём конструкция iterate, которая позволила бы организовать цикл. Reference model я бы использовал чтобы задать исходные условия задачи, основную модель с dimension (x,y) measure (val) — дал бы на основное поле. Потом задаём набор правил по которым будем решать задачу и итерируем пока не закроем всё поле. Как ие правила зададите — зависит только от вас. Я бы не делал чистый перебор, ибо это неэффективно (то что ваш метод не решил поле большее чем 5*5 в разумные сроки на приемлимом компьютере это доказывает). Кстати, oracle xe использует только одно ядро (это тоже одно из ограничений лицензии).
                                listagg (или stragg, как её знают по Кайтовскому исполнению) можно было бы действительно сделать самостоятельно, неспортивности не вижу… но можно попробовать обойти и его отсутсвие другими методами.
                                В целом — было бы лишних пару часиков — попробовал бы реализовать на model и выдать ответ, но увы, сегодня этого времени нету, потому пока только дал наводку вам на ключевые слова. Вот ещё где можно подробнее почитать про то что оно такое, хотя, конечно линк не оригинален :)
                                docs.oracle.com/cd/B19306_01/server.102/b14223/sqlmodel.htm
                                Конечно, в любом случае будет перебор (даже когда вы сами решаете «аналитически» — это тоже в некоторой мере перебор). Просто не стоит делать чистый brute-force. Можно итеративно пробегать что можно заполнить хотя-бы на уровне каждой строки-колонки (учитывая задание и уже заполненные ячейки — как мы делаем при «аналитическом» поиске), а потом уже добить результат брут-форсом. Хотя, как я уже сказал, спортивный интерес это понизит, т.к. этот sql уже не настолько «sql» как в вашем решении.

                                А 12-ка, да. 29-го июня. С 30-го уже скачал и установил себе на виртуалку. Но писать статьи о новых фичах руки почти не доходят. Надеюсь что скоро исправлюсь.

                              Only users with full accounts can post comments. Log in, please.