Solving Japanese crosswords with a single SQL query

Hi Habr! The day of the programmer is approaching, and I hasten to share my abnormal developments.

The Japanese crossword puzzle is an NP-complete task, like the task of a salesman, backpack packing, etc. When a person solves it, it is necessary to determine guaranteedly filled and empty cells in succession. Cross out columns and rows one by one until the whole pattern is complete. How is it possible to program the solution of such a problem in a language that is not even officially a programming language, does not contain loops and variables? SQL is a query language; its main task is to select rows. So we will generate a lot of all possible permutations and, like a sculptor, cut off all unnecessary.



To play a query, you will need Oracle Database 11g or higher (12th on the way). Earlier versions will not work because of the use of the listagg analytic function. It is possible to use Express Edition (XE), but this bit is used up to 1GB of memory, so the maximum size of the field that this version can shovel is 5x4. Already on the 5x5 field, the memory limit ends.

The query does not use any real database tables; you do not need to prepare anything for it. Input data is passed in the WITH subquery. You can use the proposed crossword puzzle or compose your own. To do this, describe the task - a list of numbers above and to the left of the crossword puzzle, indicate the size of the field. You can also specify symbols for filled and empty cells to your liking.

In the process of working the lines will have to go through a lot, unrealistic a lot! The field consists of cells, the total number of rows * number of columns. Each cell can be filled (1) or empty (0). Then the number of all possible permutations grows nonlinearly by the formula 2 ^ (number of cells). And since the size of the field is not fixed in advance, each cell is represented as a separate line. As a result, the obtained number of permutations must be multiplied by the number of cells. Here, for example, are several square fields:
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

The positive side of exhaustive search - there are all solutions. So, if you have idle computing power, now you know what to do with it! I don’t tell about the algorithm - you need to read from the end, each subquery is commented.

Request itself
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;