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;
``````