Geekly Articles each Day
📜 ⬆️ ⬇️

Solving Japanese crosswords with a single SQL query

Hi habr! The day of the programmer is approaching, and I am in a hurry to share my abnormal experiences.

Japanese Crossword - NP-complete task, as well as the task of a traveling salesman, laying a backpack, etc. When a person solves it, you should consistently determine the guaranteed filled and empty cells. One by one, cross out the columns and lines until the whole picture is folded. How is it possible to program the solution of a similar problem in a language that is not even officially a programming language, does not contain cycles 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 reproduce the request, you will need Oracle Database 11g or higher (12th on the way). Earlier versions are not suitable because of the use of the analytic function listagg. It is possible to use Express Edition (XE), but this stub is use up to 1GB of memory, so the maximum field size that this version can crack is 5x4. Already on the field 5x5 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 make your own. To do this, describe the task - a list of numbers above and to the left of the crossword, specify the size of the field. You can also specify the characters for filled and empty cells to your liking.

In the process of working lines will have to sort a lot, unrealistically 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 according to the formula 2 ^ (number of cells). And since the size of the field is not fixed in advance, each cell is represented by a separate line. As a result, the resulting number of permutations must be multiplied by the number of cells. Here, for example, 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 a complete search - there will be all solutions. So, if you have idle computing power, now you know what to do with them! I don’t tell about the algorithm - it’s necessary 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;

Source: https://habr.com/ru/post/192752/

More articles:


All Articles