SQL HowTo: решаем головоломку «Небоскрёбы» почти без перебора

    Многие знают правила этой головоломки (Skyscrapers):

    Перед вами вид сверху на городской квартал. В каждой клетке стоит "небоскреб" высотой, равной числу в этой клетке. Числа с боков сетки означают количество "небоскребов", видимых из соответствующей строки или столбца, если смотреть от этого числа.

    Задача: заполнить сетку числами так, чтобы в каждой строке и в каждом столбце каждое число использовалось лишь единожды.

    Понятно, что алгоритмом полного перебора можно решить что угодно, но - за экспоненциальное время. Поэтому мы попробуем написать такой SQL-запрос, который решит нам такую головоломку за приемлемое время.

    Зачем же делать это на SQL? Потому что можем! А заодно потому что это позволит научиться конструировать "очень сложные запросы", что может пригодиться и в обычной работе.

    Возьмем реальный пример

    Любой хоть сколько-то сложный SQL-запрос лучше всего конструируется на конкретном примере. Давайте возьмем для него с сайта playsudoku.ru один из "сложных" вариантов этой головоломки в размере 9x9:

    TL; DR - не заглядывайте без подготовки!
    WITH RECURSIVE src AS (
      SELECT
        x - 1 x
      , y - 1 y
      , nullif(n, '.')::integer n
      FROM
        (VALUES(
    -- http://www.playsudoku.ru/skyscrapers/sky_9_3_01.html
    $$
    . 4 . 3 3 2 1 3 5 2 .
    . . 2 . . . . . . . 3
    3 . . . . . . . . . 1
    3 2 . 6 . 7 . 4 . . 3
    2 . . 1 . . . 6 . 7 2
    3 . . . 4 . 7 . . . 4
    2 3 . 2 . . . 5 . . 2
    1 . . 5 . 6 . 2 . 4 3
    4 . . . . . . . . . .
    4 . . . . . . . 7 . 3
    . 3 3 2 3 4 6 1 2 5 .
    $$
        )) T(s)
      , LATERAL
          regexp_split_to_table(regexp_replace(s, '(^\n|\n$)', '', 'g'), '\n+')
            WITH ORDINALITY AS L(line, y)
      , LATERAL
          regexp_split_to_table(line, '\s+')
            WITH ORDINALITY AS C(n, x)
    )
    -- формируем "боковые" ограничения
    , side AS (
      SELECT
        m - 1 m
      , Y.*
      FROM
        (
          SELECT
            max(x) m
          FROM
            src
        ) X
      , LATERAL (
          SELECT
            array_agg(n ORDER BY x) FILTER(WHERE y = 0 AND x > 0 AND x < m) u
          , array_agg(n ORDER BY x) FILTER(WHERE y = m AND x > 0 AND x < m) d
          , array_agg(n ORDER BY y) FILTER(WHERE x = 0 AND y > 0 AND y < m) l
          , array_agg(n ORDER BY y) FILTER(WHERE x = m AND y > 0 AND y < m) r
          FROM
            src
        ) Y
    )
    -- собираем фиксированные разрешения
    , fix AS (
      SELECT
        x
      , y
      , array_agg(n) FILTER(
          WHERE
            coalesce( -- защита от незаданного бокового ограничения
              NOT(
                -- единичка на стороне => максимум в соседней ячейке
                (l[y] = 1 AND x = 1 AND n < m) OR
                (r[y] = 1 AND x = m AND n < m) OR
                (u[x] = 1 AND y = 1 AND n < m) OR
                (d[x] = 1 AND y = m AND n < m) OR
                -- расстояние до "борта"
                l[y] + n > m + x OR
                u[x] + n > m + y OR
                r[y] + n > m + (m - x + 1) OR
                d[x] + n > m + (m - y + 1)
              )
            , TRUE
            )
        ) cell
      FROM
        side
      , LATERAL
          generate_series(1, m) x -- "цикл" по X
      , LATERAL
          generate_series(1, m) y -- "цикл" по Y
      , LATERAL
          generate_series(1, m) n -- "цикл" по значениям
      GROUP BY
        x, y
    )
    , base AS (
      SELECT
        x
      , y
      , CASE
          WHEN n IS NOT NULL THEN ARRAY[n] -- подставляем фиксированные значения
          ELSE cell
        END cell
      FROM
        fix
      NATURAL LEFT JOIN
        src
      ORDER BY
        x, y
    )
    , rec_03 AS (
      SELECT
        '{}'::json[] fixpath
      , json_agg(row_to_json(T)) matrix
      , NULL::json result
      , TRUE has_many
      , FALSE has_none
      FROM
        base T
    UNION ALL
      (
        WITH mv AS (
          TABLE rec_03
        )
        (
          -- вычисление результата "вычеркиваний"
          SELECT
            mv.fixpath
          , mv.matrix
          , T.result
          , T.has_many
          , T.has_none
          FROM
            mv
          , LATERAL (
              WITH RECURSIVE unpack AS (
                SELECT
                  *
                FROM
                  json_to_recordset(coalesce(result, matrix)) unpack(x bigint, y bigint, cell bigint[])
              )
              , rec_02 AS (
                SELECT
                  0 lvl
                , *
                FROM
                  unpack
              UNION ALL
                -- "вычеркивание" значений
                (
                  WITH RECURSIVE mv AS (
                    TABLE rec_02
                  )
                  , rec_01 AS (
                    TABLE mv
                  UNION ALL
                    (
                      WITH mv AS (
                        TABLE rec_01
                      )
                      , step0 AS (
                        SELECT
                          *
                        , cell cell_new
                        FROM
                          mv
                        WHERE
                          NOT EXISTS(
                            SELECT
                              NULL
                            FROM
                              mv
                            WHERE
                              cell = '{}'
                          )
                      )
                      -- ограничение по столбцу/строке от зафиксированных значений
                      , heur_a AS (
                        SELECT
                          x
                        , y
                        , array_agg(DISTINCT cell_new[1]) cell_cross
                        FROM
                          step0
                        WHERE
                          array_length(cell, 1) = 1 -- единственное значение в точке
                        GROUP BY
                          GROUPING SETS((x), (y))   -- группируем одновременно в двух разрезах
                      )
                      , step1 AS (
                        SELECT
                          lvl
                        , s.x
                        , s.y
                        , cell
                        , CASE
                            -- вычисляем новое значение только для незафиксированных ячеек
                            WHEN array_length(cell_new, 1) > 1 THEN
                              ARRAY( -- разность множеств
                                SELECT
                                  unnest(s.cell)
                              EXCEPT
                                SELECT
                                  unnest(hx.cell_cross)
                              EXCEPT
                                SELECT
                                  unnest(hy.cell_cross)
                              )
                            ELSE cell_new
                          END cell_new
                        FROM
                          step0 s
                        LEFT JOIN
                          heur_a hx
                            ON hx.x = s.x
                        LEFT JOIN
                          heur_a hy
                            ON hy.y = s.y
                      )
                      -- единственная доступная позиция для значения - нужная
                      , heur_b AS (
                        SELECT DISTINCT
                          s.x
                        , s.y
                        , ARRAY[n] cell_single
                        FROM
                          (
                            SELECT
                              *
                            FROM
                              step1
                            WHERE
                              array_length(cell_new, 1) > 1
                          ) s
                        JOIN
                          (
                            SELECT
                              x
                            , y
                            , unnest(cell_new) n
                            FROM
                              step1
                            GROUP BY
                              GROUPING SETS((n, x), (n, y)) -- группируем по значению и строке/столбцу
                            HAVING
                              count(*) = 1 -- единственность позиции значения в группе
                          ) T
                            ON
                              n = ANY(cell_new) AND
                              (T.x = s.x OR T.y = s.y)
                      )
                      , step2 AS (
                        SELECT
                          lvl
                        , x
                        , y
                        , cell
                        , coalesce(cell_single, cell_new) cell_new
                        FROM
                          step1
                        NATURAL LEFT JOIN
                          heur_b
                      )
                      SELECT
                        lvl + 1
                      , x
                      , y
                      , cell_new cell
                      FROM
                        step2
                      WHERE
                        -- итерируем, пока хоть что-то "вычеркивается"
                        EXISTS(
                          SELECT
                            NULL
                          FROM
                            step2
                          WHERE
                            array_length(cell_new, 1) < array_length(cell, 1)
                        )
                    )
                  )
                  -- последний шаг рекурсии
                  , step3 AS (
                    SELECT
                      *
                    FROM
                      rec_01
                    WHERE
                      lvl = (SELECT max(lvl) FROM rec_01)
                  )
                  -- ограничение видимости по столбцам
                  , heur_cx AS (
                    -- генерируем всевозможные комбинации без повторов
                    WITH RECURSIVE gen AS (
                      SELECT
                        generate_series(1, m) x
                      , 0::bigint y
                      , '{}'::bigint[] comb
                      FROM
                        side
                    UNION ALL
                      SELECT
                        s.x
                      , s.y
                      , comb || n
                      FROM
                        gen
                      JOIN
                        step3 s
                          ON (s.x, s.y) = (gen.x, gen.y + 1)
                      JOIN LATERAL
                        unnest(cell) n
                          ON n <> ALL(comb) -- запрет повтора значения
                    )
                    SELECT
                      gen.x
                    , ord.y
                    , array_agg(DISTINCT n) cell_y
                    FROM
                      side
                    JOIN
                      gen
                        ON array_length(comb, 1) = m -- оставляем только итоговые комбинации полного размера
                    JOIN LATERAL ( -- вычисление по массиву значений "видимости"
                        SELECT
                          sum((comb[n] > ALL(comb[:n-1]))::integer) vu
                        , sum((comb[n] > ALL(comb[n+1:]))::integer) vd
                        FROM
                          generate_series(1, m) n
                      ) T
                        ON (vu, vd) = (coalesce(u[x], vu), coalesce(d[x], vd)) -- оставляем только подходящие
                    , LATERAL
                        unnest(comb)
                          WITH ORDINALITY ord(n, y)
                    GROUP BY
                      1, 2
                  )
                  -- ограничение видимости по строкам
                  , heur_cy AS (
                    WITH RECURSIVE gen AS (
                      SELECT
                        0::bigint x
                      , generate_series(1, m) y
                      , '{}'::bigint[] comb
                      FROM
                        side
                    UNION ALL
                      SELECT
                        s.x
                      , s.y
                      , comb || n
                      FROM
                        gen
                      JOIN
                        step3 s
                          ON (s.x, s.y) = (gen.x + 1, gen.y)
                      JOIN LATERAL
                        unnest(cell) n
                          ON n <> ALL(comb)
                    )
                    SELECT
                      ord.x
                    , gen.y
                    , array_agg(DISTINCT n) cell_x
                    FROM
                      side
                    JOIN
                      gen
                        ON array_length(comb, 1) = m
                    JOIN LATERAL (
                        SELECT
                          sum((comb[n] > ALL(comb[:n-1]))::integer) vl
                        , sum((comb[n] > ALL(comb[n+1:]))::integer) vr
                        FROM
                          generate_series(1, m) n
                      ) T
                        ON (vl, vr) = (coalesce(l[y], vl), coalesce(r[y], vr))
                    , LATERAL
                        unnest(comb)
                          WITH ORDINALITY ord(n, x)
                    GROUP BY
                      1, 2
                  )
                  , step4 AS (
                    SELECT
                      lvl
                    , x
                    , y
                    , cell
                      -- значения должны удовлетворять условиям и по строке, и по столбцу
                    , ARRAY(
                        SELECT
                          unnest(cell)
                      INTERSECT
                        SELECT
                          unnest(cell_x)
                      INTERSECT
                        SELECT
                          unnest(cell_y)
                      ) cell_new
                    FROM
                      step3
                    NATURAL LEFT JOIN
                      heur_cx
                    NATURAL LEFT JOIN
                      heur_cy
                  )
                  SELECT
                    lvl + 1
                  , x
                  , y
                  , cell_new cell
                  FROM
                    step4
                  WHERE
                    EXISTS(
                      SELECT
                        NULL
                      FROM
                        step4 s
                      JOIN
                        mv
                          USING(x, y)
                      WHERE
                        array_length(s.cell_new, 1) < array_length(mv.cell, 1)
                    )
                )
              )
              , last_iter AS (
                SELECT
                  x
                , y
                , cell
                FROM
                  rec_02
                WHERE
                  lvl = (SELECT max(lvl) FROM rec_02) AND
                  lvl > 0
              )
              SELECT
                coalesce(json_agg(row_to_json(T)), '[]') result
              , bool_or(array_length(cell, 1) > 1) has_many   -- есть ячейки с несколькими значениями
              , bool_or(coalesce(cell, '{}') = '{}') has_none -- есть пустые ячейки
              FROM
                last_iter T
            ) T
          WHERE
            -- нечетный шаг
            mv.result IS NULL
        UNION ALL
          -- фиксация значений ячейки
          SELECT
            T.fixpath
          , T.matrix
          , NULL
          , mv.has_many
          , mv.has_none
          FROM
            mv
          , LATERAL (
              WITH unpack AS (
                SELECT
                  *
                FROM
                  json_to_recordset(coalesce(result, matrix)) unpack(x bigint, y bigint, cell bigint[])
              )
              SELECT
                -- добавляем фиксируемую ячейку к json[] и превращаем в '[]'::json
                to_json(matrix_flt || vn) matrix
              , fixpath || vn fixpath
              FROM
                -- определяем фиксируемую ячейку
                (
                  SELECT
                    *
                  FROM
                    unpack
                  WHERE
                    array_length(cell, 1) > 1
                  ORDER BY
                    array_length(cell, 1), x, y
                  LIMIT 1
                ) fix
                -- собираем отфильтрованный json без этой ячейки
              , LATERAL (
                  SELECT
                    array_agg(row_to_json(T)) FILTER(WHERE (x, y) <> (fix.x, fix.y)) matrix_flt
                  FROM
                    unpack T
                ) T0
                -- организуем перебор вариантов значений
              , LATERAL
                  unnest(cell) n
                -- формируем json-представление этой ячейки с конкретным значением
              , LATERAL (
                  SELECT
                    row_to_json(T) vn
                  FROM
                    (
                      SELECT
                        x
                      , y
                      , ARRAY[n] cell
                    ) T
                ) T1
            ) T
          WHERE
            -- четный шаг
            mv.result IS NOT NULL AND
            -- пока нет пустых ячеек, но есть незафиксированные
            mv.has_many AND
            NOT mv.has_none
        )
      )
    )
    -- находим и распаковываем запись с решением
    , unpack AS (
      SELECT
        *
      FROM
        json_to_recordset((
          SELECT
            result
          FROM
            rec_03
          WHERE
            NOT has_many AND -- нет вариативности
            NOT has_none     -- нет занулений
          LIMIT 1
        )) unpack(x bigint, y bigint, cell bigint[])
    )
    -- собираем в матрицу
    SELECT
      string_agg(
        lpad(cell[1]::text, (SELECT length(m::text) FROM side))
      , ' '
      ORDER BY x
      ) line
    FROM
      unpack
    GROUP BY
      y
    ORDER BY
      y;

    Из псевдоматрицы - в рекордсет

    Как это можно представить в SQL? Давайте договоримся, что пустая клетка у нас будет обозначена точкой, а заполненная - стоящим в ней числом. Тогда всю матрицу можно представить как единое текстовое значение и разобрать на строки-столбцы с помощью пары регулярных выражений:

    WITH src AS (
      SELECT
        x - 1 x
      , y - 1 y
      , nullif(n, '.')::integer n
      FROM
        (VALUES(
    -- http://www.playsudoku.ru/skyscrapers/sky_9_3_01.html
    $$
    . 4 . 3 3 2 1 3 5 2 .
    . . 2 . . . . . . . 3
    3 . . . . . . . . . 1
    3 2 . 6 . 7 . 4 . . 3
    2 . . 1 . . . 6 . 7 2
    3 . . . 4 . 7 . . . 4
    2 3 . 2 . . . 5 . . 2
    1 . . 5 . 6 . 2 . 4 3
    4 . . . . . . . . . .
    4 . . . . . . . 7 . 3
    . 3 3 2 3 4 6 1 2 5 .
    $$
        )) T(s)
      , LATERAL
          regexp_split_to_table(regexp_replace(s, '(^\n|\n$)', '', 'g'), '\n+')
            WITH ORDINALITY AS L(line, y)
      , LATERAL
          regexp_split_to_table(line, '\s+')
            WITH ORDINALITY AS C(n, x)
    )

    Получаем уже пронумерованный за счет использования WITH ORDINALITY рекордсет из 11 x 11 строк - внутренний квадрат 9 x 9, плюс значения "видимости" сверху-снизу и слева-справа:

     x | y | n
     0 | 0 | -
     1 | 0 | 4
     2 | 0 | -
     3 | 0 | 3
     4 | 0 | 3
     5 | 0 | 2
     6 | 0 | 1
     7 | 0 | 3
     8 | 0 | 5
     9 | 0 | 2
    10 | 0 | -
     0 | 1 | -
     1 | 1 | -
     2 | 1 | 2
     ...

    Поскольку мы "строим" заведомо достаточно сложный запрос, то использование CTE (Common Table Expression) вместо вложенных запросов - это именно та "фишка", которая сразу позволяет значительно упростить его "сборку".

    Теперь из этого выделим массивы, которые будут хранить количество "видимых небоскребов" в каждой позиции каждой из 4 сторон квадрата:

    -- формируем "боковые" ограничения
    , side AS (
      SELECT
        m - 1 m
      , Y.*
      FROM
        (
          SELECT
            max(x) m
          FROM
            src
        ) X
      , LATERAL (
          SELECT
            array_agg(n ORDER BY x) FILTER(WHERE y = 0 AND x > 0 AND x < m) u
          , array_agg(n ORDER BY x) FILTER(WHERE y = m AND x > 0 AND x < m) d
          , array_agg(n ORDER BY y) FILTER(WHERE x = 0 AND y > 0 AND y < m) l
          , array_agg(n ORDER BY y) FILTER(WHERE x = m AND y > 0 AND y < m) r
          FROM
            src
        ) Y
    )

    Бонусом мы вычислили m - размер стороны нашего квадрата:

    m | u                      | d                   | l                      | r
    9 | {4,NULL,3,3,2,1,3,5,2} | {3,3,2,3,4,6,1,2,5} | {NULL,3,3,2,3,2,1,4,4} | {3,1,3,2,4,2,3,NULL,3}"

    В некоторых позициях оказался NULL, но нас это не должно смущать, поскольку мы действительно ничего не знаем о значениях в этих ячейках.

    Базовые ограничения

    Первое соображение достаточно простое: если на стороне стоит значение 1, то в соседней с ним ячейке может стоять только максимальное из возможных значений, то есть m, потому что иначе этот "самый высокий небоскреб" будет все равно "просвечивать" через любой другой и мы должны будем "увидеть" значение не меньше 2:

    Если видно только один "небоскреб", то только самый высокий
    Если видно только один "небоскреб", то только самый высокий

    Второе ограничение чуть сложнее. Рассмотрим на примере квадрата со стороной 4, при каком значении "сбоку", какие "небоскребы" где стоять точно не могут:

    Запрет позиций на основе значения "видимости"
    Запрет позиций на основе значения "видимости"

    Очевидно, что если мы видим максимальное для такого квадрата значение 4, то единственная допустимая комбинация: 1, 2, 3, 4. Если же значение 3, то не существует ни одной расстановки, где в первой клетке стояло бы 3, или 4 в любой из первых двух. Аналогично для 2 и значения 4 в первой ячейке.

    Теперь выразим это на SQL:

    -- собираем фиксированные разрешения
    , fix AS (
      SELECT
        x
      , y
      , array_agg(n) FILTER(
          WHERE
            coalesce( -- защита от незаданного бокового ограничения
              NOT(
                -- единичка на стороне => максимум в соседней ячейке
                (l[y] = 1 AND x = 1 AND n < m) OR
                (r[y] = 1 AND x = m AND n < m) OR
                (u[x] = 1 AND y = 1 AND n < m) OR
                (d[x] = 1 AND y = m AND n < m) OR
                -- расстояние до "борта"
                l[y] + n > m + x OR
                u[x] + n > m + y OR
                r[y] + n > m + (m - x + 1) OR
                d[x] + n > m + (m - y + 1)
              )
            , TRUE
            )
        ) cell
      FROM
        side
      , LATERAL
          generate_series(1, m) x -- "цикл" по X
      , LATERAL
          generate_series(1, m) y -- "цикл" по Y
      , LATERAL
          generate_series(1, m) n -- "цикл" по значениям
      GROUP BY
        x, y
    )

    В результате, мы определили для каждой клетки набор значений, которые там вообще могут стоять:

    x | y | cell
    1 | 1 | {1,2,3,4,5,6}
    1 | 2 | {1,2,3,4,5,6,7}
    1 | 3 | {1,2,3,4,5,6,7}
    1 | 4 | {1,2,3,4,5,6,7,8}
    1 | 5 | {1,2,3,4,5,6,7}
    1 | 6 | {1,2,3,4,5,6,7,8}
    1 | 7 | {9}
    1 | 8 | {1,2,3,4,5,6}
    1 | 9 | {1,2,3,4,5,6}

    Теперь к этому мы легко добавляем исходно известные фиксированные позиции из самого квадрата, представив их в виде массива из единственного возможного значения:

    , step0 AS (
      SELECT
        x
      , y
      , CASE
          WHEN n IS NOT NULL THEN ARRAY[n] -- подставляем фиксированные значения
          ELSE cell
        END cell
      FROM
        fix
      NATURAL LEFT JOIN
        src
      ORDER BY
        x, y
    )
    x | y | cell
    1 | 1 | {1,2,3,4,5,6}
    1 | 2 | {1,2,3,4,5,6,7}
    1 | 3 | {2}
    1 | 4 | {1,2,3,4,5,6,7,8}
    1 | 5 | {1,2,3,4,5,6,7}
    1 | 6 | {3}
    1 | 7 | {9}
    1 | 8 | {1,2,3,4,5,6}
    1 | 9 | {1,2,3,4,5,6}
    Применение базовых ограничений к исходной матрице
    Применение базовых ограничений к исходной матрице

    Это состояние станет "нулевым" шагом нашего алгоритма.

    Эвристика "A": ход ладьей

    Теперь вспомним, что по условию задачи, все значения в каждой строке и каждом столбце различны. Это значит, что если мы уже достоверно определились, что в каких-то клетках находятся конкретные значения, то их не может быть больше нигде в этой же строке/столбце, и их можно "вычеркнуть".

    Запрет повторения в строке/столбце
    Запрет повторения в строке/столбце
    -- ограничение по столбцу/строке от зафиксированных значений
    , heur_a AS (
      SELECT
        x
      , y
      , array_agg(DISTINCT cell[1]) cell_cross
      FROM
        step0
      WHERE
        array_length(cell, 1) = 1 -- единственное значение в точке
      GROUP BY
        GROUPING SETS((x), (y))   -- группируем одновременно в двух разрезах
    )
    x | y | cell_cross
    1 | - | {2,3,9}
    2 | - | {2}
    3 | - | {1,2,5,6}
    4 | - | {4}
    5 | - | {6,7}
    6 | - | {7,9}
    7 | - | {2,4,5,6,9}
    8 | - | {7}
    9 | - | {4,7,9}
    - | 1 | {2,9}
    - | 2 | {9}
    - | 3 | {2,4,6,7}
    - | 4 | {1,6,7}
    - | 5 | {4,7}
    - | 6 | {2,3,5}
    - | 7 | {2,4,5,6,9}
    - | 9 | {7,9}
    , step1 AS (
      SELECT
        s.x
      , s.y
      , cell
      , CASE
          -- вычисляем новое значение только для незафиксированных ячеек
          WHEN array_length(cell, 1) > 1 THEN
            ARRAY( -- разность множеств
              SELECT
                unnest(s.cell)
            EXCEPT
              SELECT
                unnest(hx.cell_cross)
            EXCEPT
              SELECT
                unnest(hy.cell_cross)
            )
          ELSE cell
        END cell_new
      FROM
        step0 s
      LEFT JOIN
        heur_a hx
          ON hx.x = s.x
      LEFT JOIN
        heur_a hy
          ON hy.y = s.y
    )
    x | y | cell              | cell_new
    1 | 1 | {1,2,3,4,5,6}     | {4,6,1,5}
    1 | 2 | {1,2,3,4,5,6,7}   | {4,6,7,1,5}
    1 | 3 | {2}               | {2}
    1 | 4 | {1,2,3,4,5,6,7,8} | {4,5,8}
    1 | 5 | {1,2,3,4,5,6,7}   | {6,1,5}
    1 | 6 | {3}               | {3}
    1 | 7 | {9}               | {9}
    1 | 8 | {1,2,3,4,5,6}     | {4,6,1,5}
    1 | 9 | {1,2,3,4,5,6}     | {4,6,1,5}
    ...

    Здесь мы использовали достаточно распространенную в PostgreSQL технику вычисления операций над массивами как множествами в силу отсутствия таких встроенных функций:

    -- объединение
    arraySetA + arraySetB =
      ARRAY(
        SELECT unnest(arraySetA)
      UNION
        SELECT unnest(arraySetB)
      )
    -- исключение
    arraySetA - arraySetB = ARRAY(... EXCEPT ...)
    -- пересечение
    arraySetA * arraySetB = ARRAY(... INTERSECT ...)

    Посмотрим, что получилось:

    Применение ограничений по строке/столбцу
    Применение ограничений по строке/столбцу

    Эвристика "B": один в поле не воин

    Обратим внимание на первую же строку:

    Из всех оставшихся комбинаций лишь в одной незафиксированной ячейке может находиться значение 8. А, раз по условию задачи, все значения в строке/столбце различны - значит, именно там оно и находится.

    В коде это будет выглядеть так:

    -- единственная доступная позиция для значения - нужная
    , heur_b AS (
      SELECT DISTINCT
        s.x
      , s.y
      , ARRAY[n] cell_single
      FROM
        (
          SELECT
            *
          FROM
            step1
          WHERE
            array_length(cell_new, 1) > 1
        ) s
      JOIN
        (
          SELECT
            x
          , y
          , unnest(cell_new) n
          FROM
            step1
          GROUP BY
            GROUPING SETS((n, x), (n, y)) -- группируем по значению и строке/столбцу
          HAVING
            count(*) = 1 -- единственность позиции значения в группе
        ) T
          ON
            n = ANY(cell_new) AND
            (T.x = s.x OR T.y = s.y)
    )

    За основу мы берем уже не исходное значение cell, а cell_new, полученное на предыдущем шаге алгоритма.

    x | y | cell_single
    1 | 2 | {7}
    1 | 4 | {8}
    3 | 5 | {9}
    3 | 9 | {8}
    4 | 3 | {9}
    5 | 1 | {8}
    8 | 8 | {9}
    9 | 6 | {8}
    Ограничение по единственно возможной позиции
    Ограничение по единственно возможной позиции
    , step2 AS (
      SELECT
        x
      , y
      , cell
      , coalesce(cell_single, cell_new) cell_new
      FROM
        step1
      NATURAL LEFT JOIN
        heur_b
    )

    После наложения ограничений получаем:

    Применение ограничений по единственно возможной позиции
    Применение ограничений по единственно возможной позиции

    Организуем рекурсивные циклы

    Теперь самое время заметить, что часть определенных на втором шаге значений позволяет снова "вычеркнуть" часть комбинаций точно так же, как мы сделали это на первом шаге (если значение было единственным по строке, то его можно убрать из столбца и наоборот), а потом опять поискать "единственные", и снова, и опять... - то есть нам нужен цикл! А на SQL циклы организуются с помощью рекурсивных запросов.

    Самое главное в таких запросах - правильно подобрать условие выхода из рекурсии. Подробно я останавливался на этой теме в статьях "PostgreSQL Antipatterns: «Бесконечность — не предел!», или Немного о рекурсии" и "SQL HowTo: ломаем мозг об дерево — упорядочиваем иерархию с рекурсией и без".

    Для данной задачи нам понадобится использование техник нумерации уровня рекурсии и "материализации" рекурсивной части выборки, чтобы к ней можно было обращаться неоднократно. Модифицируем наш запрос:

    WITH RECURSIVE src AS (
    -- ...
    -- вместо step0
    , base AS (
      SELECT
        x
      , y
      , CASE
          WHEN n IS NOT NULL THEN ARRAY[n] -- подставляем фиксированные значения
          ELSE cell
        END cell
      FROM
        fix
      NATURAL LEFT JOIN
        src
      ORDER BY
        x, y
    )
    -- рекурсивный цикл
    , rec AS (
      SELECT
        0 lvl
      , *
      FROM
        base
    UNION ALL
      (
        WITH step0 AS (
          SELECT
            *
          , cell cell_new
          FROM
            rec
        )
    -- ... все те же heur_a, step1, heur_b, step2, только с "протаскиванием" lvl
        SELECT
          lvl + 1
        , x
        , y
        , cell_new cell
        FROM
          step2
        WHERE
          -- итерируем, пока хоть что-то "вычеркивается"
          EXISTS(
            SELECT
              NULL
            FROM
              step2
            WHERE
              array_length(cell_new, 1) < array_length(cell, 1)
          )
      )
    )
    Полный текст запроса
    WITH RECURSIVE src AS (
      SELECT
        x - 1 x
      , y - 1 y
      , nullif(n, '.')::integer n
      FROM
        (VALUES(
    -- http://www.playsudoku.ru/skyscrapers/sky_9_3_01.html
    $$
    . 4 . 3 3 2 1 3 5 2 .
    . . 2 . . . . . . . 3
    3 . . . . . . . . . 1
    3 2 . 6 . 7 . 4 . . 3
    2 . . 1 . . . 6 . 7 2
    3 . . . 4 . 7 . . . 4
    2 3 . 2 . . . 5 . . 2
    1 . . 5 . 6 . 2 . 4 3
    4 . . . . . . . . . .
    4 . . . . . . . 7 . 3
    . 3 3 2 3 4 6 1 2 5 .
    $$
        )) T(s)
      , LATERAL
          regexp_split_to_table(regexp_replace(s, '(^\n|\n$)', '', 'g'), '\n+')
            WITH ORDINALITY AS L(line, y)
      , LATERAL
          regexp_split_to_table(line, '\s+')
            WITH ORDINALITY AS C(n, x)
    )
    -- формируем "боковые" ограничения
    , side AS (
      SELECT
        m - 1 m
      , Y.*
      FROM
        (
          SELECT
            max(x) m
          FROM
            src
        ) X
      , LATERAL (
          SELECT
            array_agg(n ORDER BY x) FILTER(WHERE y = 0 AND x > 0 AND x < m) u
          , array_agg(n ORDER BY x) FILTER(WHERE y = m AND x > 0 AND x < m) d
          , array_agg(n ORDER BY y) FILTER(WHERE x = 0 AND y > 0 AND y < m) l
          , array_agg(n ORDER BY y) FILTER(WHERE x = m AND y > 0 AND y < m) r
          FROM
            src
        ) Y
    )
    -- собираем фиксированные разрешения
    , fix AS (
      SELECT
        x
      , y
      , array_agg(n) FILTER(
          WHERE
            coalesce( -- защита от незаданного бокового ограничения
              NOT(
                -- единичка на стороне => максимум в соседней ячейке
                (l[y] = 1 AND x = 1 AND n < m) OR
                (r[y] = 1 AND x = m AND n < m) OR
                (u[x] = 1 AND y = 1 AND n < m) OR
                (d[x] = 1 AND y = m AND n < m) OR
                -- расстояние до "борта"
                l[y] + n > m + x OR
                u[x] + n > m + y OR
                r[y] + n > m + (m - x + 1) OR
                d[x] + n > m + (m - y + 1)
              )
            , TRUE
            )
        ) cell
      FROM
        side
      , LATERAL
          generate_series(1, m) x -- "цикл" по X
      , LATERAL
          generate_series(1, m) y -- "цикл" по Y
      , LATERAL
          generate_series(1, m) n -- "цикл" по значениям
      GROUP BY
        x, y
    )
    , base AS (
      SELECT
        x
      , y
      , CASE
          WHEN n IS NOT NULL THEN ARRAY[n] -- подставляем фиксированные значения
          ELSE cell
        END cell
      FROM
        fix
      NATURAL LEFT JOIN
        src
      ORDER BY
        x, y
    )
    -- рекурсивный цикл
    , rec AS (
      SELECT
        0 lvl
      , *
      FROM
        base
    UNION ALL
      (
        WITH step0 AS (
          SELECT
            *
          , cell cell_new
          FROM
            rec
        )
        -- ограничение по столбцу/строке от зафиксированных значений
        , heur_a AS (
          SELECT
            x
          , y
          , array_agg(DISTINCT cell_new[1]) cell_cross
          FROM
            step0
          WHERE
            array_length(cell, 1) = 1 -- единственное значение в точке
          GROUP BY
            GROUPING SETS((x), (y))   -- группируем одновременно в двух разрезах
        )
        , step1 AS (
          SELECT
            lvl
          , s.x
          , s.y
          , cell
          , CASE
              -- вычисляем новое значение только для незафиксированных ячеек
              WHEN array_length(cell_new, 1) > 1 THEN
                ARRAY( -- разность множеств
                  SELECT
                    unnest(s.cell)
                EXCEPT
                  SELECT
                    unnest(hx.cell_cross)
                EXCEPT
                  SELECT
                    unnest(hy.cell_cross)
                )
              ELSE cell_new
            END cell_new
          FROM
            step0 s
          LEFT JOIN
            heur_a hx
              ON hx.x = s.x
          LEFT JOIN
            heur_a hy
              ON hy.y = s.y
        )
        -- единственная доступная позиция для значения - нужная
        , heur_b AS (
          SELECT DISTINCT
            s.x
          , s.y
          , ARRAY[n] cell_single
          FROM
            (
              SELECT
                *
              FROM
                step1
              WHERE
                array_length(cell_new, 1) > 1
            ) s
          JOIN
            (
              SELECT
                x
              , y
              , unnest(cell_new) n
              FROM
                step1
              GROUP BY
                GROUPING SETS((n, x), (n, y)) -- группируем по значению и строке/столбцу
              HAVING
                count(*) = 1 -- единственность позиции значения в группе
            ) T
              ON
                n = ANY(cell_new) AND
                (T.x = s.x OR T.y = s.y)
        )
        , step2 AS (
          SELECT
            lvl
          , x
          , y
          , cell
          , coalesce(cell_single, cell_new) cell_new
          FROM
            step1
          NATURAL LEFT JOIN
            heur_b
        )
        SELECT
          lvl + 1
        , x
        , y
        , cell_new cell
        FROM
          step2
        WHERE
          -- итерируем, пока хоть что-то "вычеркивается"
          EXISTS(
            SELECT
              NULL
            FROM
              step2
            WHERE
              array_length(cell_new, 1) < array_length(cell, 1)
          )
      )
    )
    TABLE rec ORDER BY lvl DESC, x, y;

    После 3 таких итераций "вычеркивания" наша матрица примет следующий вид:

    Применение ограничений пересечения и единственности в цикле
    Применение ограничений пересечения и единственности в цикле

    Можно заметить, что дополнительно у нас зафиксировалось в предпоследнем столбце значение 8, но дальше мы уперлись.

    Эвристика "C": посмотри по сторонам

    Давайте взглянем внимательно на третью строку:

    По условию единственности каждого значения в строке, мы можем получить следующие комбинации расстановок и результирующие значения "видимости":

    3 | 2 1 6 9 7 8 4 3 5 | 3 +
    3 | 2 1 6 9 7 8 4 5 3 | 4 -
    3 | 2 8 6 9 7 1 4 3 5 | 3 +
    3 | 2 8 6 9 7 1 4 5 3 | 4 -
    3 | 2 8 6 9 7 3 4 1 5 | 3 +
    3 | 2 8 6 9 7 3 4 5 1 | 4 -
    3 | 2 8 6 9 7 5 4 1 3 | 5 -
    3 | 2 8 6 9 7 5 4 3 1 | 6 -

    Как видим, далеко не все расстановки удовлетворяют известным нам значениям 3 и 3. Давайте оставим только те, которые допустимы, и посмотрим, на каких перебираемых позициях какие значения возможны:

      *       *   * *
    2 1 6 9 7 8 4 3 5
    2 8 6 9 7 1 4 3 5
    2 8 6 9 7 3 4 1 5

    Оказывается, на первой такой позиции могут стоять только 1 и 8, но никак не 3 и 5, а на последней - наоборот, только 5:

    Ограничение по значениям "видимости"
    Ограничение по значениям "видимости"

    Проведя аналогичный анализ по всем строкам и столбцам мы дополнительно сократим пространство возможных значений:

    -- ограничение видимости по столбцам
    , heur_cx AS (
      -- генерируем всевозможные комбинации без повторов
      WITH RECURSIVE gen AS (
        SELECT
          generate_series(1, m) x
        , 0::bigint y
        , '{}'::bigint[] comb
        FROM
          side
      UNION ALL
        SELECT
          s.x
        , s.y
        , comb || n
        FROM
          gen
        JOIN
          step3 s
            ON (s.x, s.y) = (gen.x, gen.y + 1)
        JOIN LATERAL
          unnest(cell) n
            ON n <> ALL(comb) -- запрет повтора значения
      )
      SELECT
        gen.x
      , ord.y
      , array_agg(DISTINCT n) cell_y
      FROM
        side
      JOIN
        gen
          ON array_length(comb, 1) = m -- оставляем только итоговые комбинации полного размера
      JOIN LATERAL ( -- вычисление по массиву значений "видимости"
          SELECT
            sum((comb[n] > ALL(comb[:n-1]))::integer) vu
          , sum((comb[n] > ALL(comb[n+1:]))::integer) vd
          FROM
            generate_series(1, m) n
        ) T
          ON (vu, vd) = (coalesce(u[x], vu), coalesce(d[x], vd)) -- оставляем только подходящие
      , LATERAL
          unnest(comb)
            WITH ORDINALITY ord(n, y)
      GROUP BY
        1, 2
    )

    Абсолютно симметрично то же самое проделываем для строк:

    -- ограничение видимости по строкам
    , heur_cy AS (
      WITH RECURSIVE gen AS (
        SELECT
          0::bigint x
        , generate_series(1, m) y
        , '{}'::bigint[] comb
        FROM
          side
      UNION ALL
        SELECT
          s.x
        , s.y
        , comb || n
        FROM
          gen
        JOIN
          step3 s
            ON (s.x, s.y) = (gen.x + 1, gen.y)
        JOIN LATERAL
          unnest(cell) n
            ON n <> ALL(comb)
      )
      SELECT
        ord.x
      , gen.y
      , array_agg(DISTINCT n) cell_x
      FROM
        side
      JOIN
        gen
          ON array_length(comb, 1) = m
      JOIN LATERAL (
          SELECT
            sum((comb[n] > ALL(comb[:n-1]))::integer) vl
          , sum((comb[n] > ALL(comb[n+1:]))::integer) vr
          FROM
            generate_series(1, m) n
        ) T
          ON (vl, vr) = (coalesce(l[y], vl), coalesce(r[y], vr))
      , LATERAL
          unnest(comb)
            WITH ORDINALITY ord(n, x)
      GROUP BY
        1, 2
    )
    , step4 AS (
      SELECT
        x
      , y
      , cell
        -- значения должны удовлетворять условиям и по строке, и по столбцу
      , ARRAY(
          SELECT
            unnest(cell)
        INTERSECT
          SELECT
            unnest(cell_x)
        INTERSECT
          SELECT
            unnest(cell_y)
        ) cell_new
      FROM
        step3
      NATURAL LEFT JOIN
        heur_cx
      NATURAL LEFT JOIN
        heur_cy
    )
    Применение ограничений по значениям "видимости"
    Применение ограничений по значениям "видимости"

    Ну, а теперь снова хочется "повычеркивать" и поискать единственные...

    Можно бы и в первый рекурсивный блок включить применение этого ограничения, но тогда оно будет применяться на каждом шаге рекурсии, а не только когда уже все вычеркнуто - значит, генерируемых комбинаций будет еще слишком много, что печально скажется на времени выполнения запроса.

    Поэтому по использованной выше методике "обрекурсивливания" заворачиваем запросы один в другой:

    -- ...
    , rec_02 AS (
      SELECT
        0 lvl
      , *
      FROM
        base
    UNION ALL
      (
        WITH RECURSIVE rec_01 AS (
          SELECT
            *
          FROM
            rec_02
        UNION ALL
          (
            WITH step0 AS (
              SELECT
                *
              , cell cell_new
              FROM
                rec_01
            )
    -- ...
    Полный текст запроса
    WITH RECURSIVE src AS (
      SELECT
        x - 1 x
      , y - 1 y
      , nullif(n, '.')::integer n
      FROM
        (VALUES(
    -- http://www.playsudoku.ru/skyscrapers/sky_9_3_01.html
    $$
    . 4 . 3 3 2 1 3 5 2 .
    . . 2 . . . . . . . 3
    3 . . . . . . . . . 1
    3 2 . 6 . 7 . 4 . . 3
    2 . . 1 . . . 6 . 7 2
    3 . . . 4 . 7 . . . 4
    2 3 . 2 . . . 5 . . 2
    1 . . 5 . 6 . 2 . 4 3
    4 . . . . . . . . . .
    4 . . . . . . . 7 . 3
    . 3 3 2 3 4 6 1 2 5 .
    $$
        )) T(s)
      , LATERAL
          regexp_split_to_table(regexp_replace(s, '(^\n|\n$)', '', 'g'), '\n+')
            WITH ORDINALITY AS L(line, y)
      , LATERAL
          regexp_split_to_table(line, '\s+')
            WITH ORDINALITY AS C(n, x)
    )
    -- формируем "боковые" ограничения
    , side AS (
      SELECT
        m - 1 m
      , Y.*
      FROM
        (
          SELECT
            max(x) m
          FROM
            src
        ) X
      , LATERAL (
          SELECT
            array_agg(n ORDER BY x) FILTER(WHERE y = 0 AND x > 0 AND x < m) u
          , array_agg(n ORDER BY x) FILTER(WHERE y = m AND x > 0 AND x < m) d
          , array_agg(n ORDER BY y) FILTER(WHERE x = 0 AND y > 0 AND y < m) l
          , array_agg(n ORDER BY y) FILTER(WHERE x = m AND y > 0 AND y < m) r
          FROM
            src
        ) Y
    )
    -- собираем фиксированные разрешения
    , fix AS (
      SELECT
        x
      , y
      , array_agg(n) FILTER(
          WHERE
            coalesce( -- защита от незаданного бокового ограничения
              NOT(
                -- единичка на стороне => максимум в соседней ячейке
                (l[y] = 1 AND x = 1 AND n < m) OR
                (r[y] = 1 AND x = m AND n < m) OR
                (u[x] = 1 AND y = 1 AND n < m) OR
                (d[x] = 1 AND y = m AND n < m) OR
                -- расстояние до "борта"
                l[y] + n > m + x OR
                u[x] + n > m + y OR
                r[y] + n > m + (m - x + 1) OR
                d[x] + n > m + (m - y + 1)
              )
            , TRUE
            )
        ) cell
      FROM
        side
      , LATERAL
          generate_series(1, m) x -- "цикл" по X
      , LATERAL
          generate_series(1, m) y -- "цикл" по Y
      , LATERAL
          generate_series(1, m) n -- "цикл" по значениям
      GROUP BY
        x, y
    )
    , base AS (
      SELECT
        x
      , y
      , CASE
          WHEN n IS NOT NULL THEN ARRAY[n] -- подставляем фиксированные значения
          ELSE cell
        END cell
      FROM
        fix
      NATURAL LEFT JOIN
        src
      ORDER BY
        x, y
    )
    , rec_02 AS (
      SELECT
        0 lvl
      , *
      FROM
        base
    UNION ALL
      (
        WITH RECURSIVE rec_01 AS (
          SELECT
            *
          FROM
            rec_02
        UNION ALL
          (
            WITH step0 AS (
              SELECT
                *
              , cell cell_new
              FROM
                rec_01
            )
            -- ограничение по столбцу/строке от зафиксированных значений
            , heur_a AS (
              SELECT
                x
              , y
              , array_agg(DISTINCT cell_new[1]) cell_cross
              FROM
                step0
              WHERE
                array_length(cell, 1) = 1 -- единственное значение в точке
              GROUP BY
                GROUPING SETS((x), (y))   -- группируем одновременно в двух разрезах
            )
            , step1 AS (
              SELECT
                lvl
              , s.x
              , s.y
              , cell
              , CASE
                  -- вычисляем новое значение только для незафиксированных ячеек
                  WHEN array_length(cell_new, 1) > 1 THEN
                    ARRAY( -- разность множеств
                      SELECT
                        unnest(s.cell)
                    EXCEPT
                      SELECT
                        unnest(hx.cell_cross)
                    EXCEPT
                      SELECT
                        unnest(hy.cell_cross)
                    )
                  ELSE cell_new
                END cell_new
              FROM
                step0 s
              LEFT JOIN
                heur_a hx
                  ON hx.x = s.x
              LEFT JOIN
                heur_a hy
                  ON hy.y = s.y
            )
            -- единственная доступная позиция для значения - нужная
            , heur_b AS (
              SELECT DISTINCT
                s.x
              , s.y
              , ARRAY[n] cell_single
              FROM
                (
                  SELECT
                    *
                  FROM
                    step1
                  WHERE
                    array_length(cell_new, 1) > 1
                ) s
              JOIN
                (
                  SELECT
                    x
                  , y
                  , unnest(cell_new) n
                  FROM
                    step1
                  GROUP BY
                    GROUPING SETS((n, x), (n, y)) -- группируем по значению и строке/столбцу
                  HAVING
                    count(*) = 1 -- единственность позиции значения в группе
                ) T
                  ON
                    n = ANY(cell_new) AND
                    (T.x = s.x OR T.y = s.y)
            )
            , step2 AS (
              SELECT
                lvl
              , x
              , y
              , cell
              , coalesce(cell_single, cell_new) cell_new
              FROM
                step1
              NATURAL LEFT JOIN
                heur_b
            )
            SELECT
              lvl + 1
            , x
            , y
            , cell_new cell
            FROM
              step2
            WHERE
              -- итерируем, пока хоть что-то "вычеркивается"
              EXISTS(
                SELECT
                  NULL
                FROM
                  step2
                WHERE
                  array_length(cell_new, 1) < array_length(cell, 1)
              )
          )
        )
        -- последний шаг рекурсии
        , step3 AS (
          SELECT
            lvl
          , x
          , y
          , cell
          FROM
            rec_01
          WHERE
            lvl = (SELECT max(lvl) FROM rec_01)
        )
        -- ограничение видимости по столбцам
        , heur_cx AS (
          -- генерируем всевозможные комбинации без повторов
          WITH RECURSIVE gen AS (
            SELECT
              generate_series(1, m) x
            , 0::bigint y
            , '{}'::bigint[] comb
            FROM
              side
          UNION ALL
            SELECT
              s.x
            , s.y
            , comb || n
            FROM
              gen
            JOIN
              step3 s
                ON (s.x, s.y) = (gen.x, gen.y + 1)
            JOIN LATERAL
              unnest(cell) n
                ON n <> ALL(comb) -- запрет повтора значения
          )
          SELECT
            gen.x
          , ord.y
          , array_agg(DISTINCT n) cell_y
          FROM
            side
          JOIN
            gen
              ON array_length(comb, 1) = m -- оставляем только итоговые комбинации полного размера
          JOIN LATERAL ( -- вычисление по массиву значений "видимости"
              SELECT
                sum((comb[n] > ALL(comb[:n-1]))::integer) vu
              , sum((comb[n] > ALL(comb[n+1:]))::integer) vd
              FROM
                generate_series(1, m) n
            ) T
              ON (vu, vd) = (coalesce(u[x], vu), coalesce(d[x], vd)) -- оставляем только подходящие
          , LATERAL
              unnest(comb)
                WITH ORDINALITY ord(n, y)
          GROUP BY
            1, 2
        )
        -- ограничение видимости по строкам
        , heur_cy AS (
          WITH RECURSIVE gen AS (
            SELECT
              0::bigint x
            , generate_series(1, m) y
            , '{}'::bigint[] comb
            FROM
              side
          UNION ALL
            SELECT
              s.x
            , s.y
            , comb || n
            FROM
              gen
            JOIN
              step3 s
                ON (s.x, s.y) = (gen.x + 1, gen.y)
            JOIN LATERAL
              unnest(cell) n
                ON n <> ALL(comb)
          )
          SELECT
            ord.x
          , gen.y
          , array_agg(DISTINCT n) cell_x
          FROM
            side
          JOIN
            gen
              ON array_length(comb, 1) = m
          JOIN LATERAL (
              SELECT
                sum((comb[n] > ALL(comb[:n-1]))::integer) vl
              , sum((comb[n] > ALL(comb[n+1:]))::integer) vr
              FROM
                generate_series(1, m) n
            ) T
              ON (vl, vr) = (coalesce(l[y], vl), coalesce(r[y], vr))
          , LATERAL
              unnest(comb)
                WITH ORDINALITY ord(n, x)
          GROUP BY
            1, 2
        )
        , step4 AS (
          SELECT
            lvl
          , x
          , y
          , cell
            -- значения должны удовлетворять условиям и по строке, и по столбцу
          , ARRAY(
              SELECT
                unnest(cell)
            INTERSECT
              SELECT
                unnest(cell_x)
            INTERSECT
              SELECT
                unnest(cell_y)
                order by 1
            ) cell_new
          FROM
            step3
          NATURAL LEFT JOIN
            heur_cx
          NATURAL LEFT JOIN
            heur_cy
        )
        SELECT
          lvl + 1
        , x
        , y
        , cell_new cell
        FROM
          step4
        WHERE
          EXISTS(
            SELECT
              NULL
            FROM
              step4
            WHERE
              array_length(cell_new, 1) < array_length(cell, 1)
          )
      )
    )
    TABLE rec_02 ORDER lvl DESC, x, y;

    Да здравствует брутфорс!

    Вот мы и пришли к ситуации, когда единственный возможный шаг - прямое моделирование с последующей проверкой условий. И таки да, в такую ситуацию мы можем попасть не раз, поэтому - снова рекурсия.

    Чтобы не пришлось перебирать много, на каждом таком шаге мы возьмем самую первую ячейку, где меньше всего вариантов значений, и поочередно попробуем подставить каждое из них.

    json_to_recordset

    Но как передать целую матрицу между шагами рекурсии, да еще и с подменой значения в ячейке? Тут нам придут на помощь операции над json:

    -- "упаковка" матрицы
    SELECT
      json_agg(row_to_json(T)) result
    FROM
      last_iter T
    -- "распаковка" матрицы
    , unpack AS (
      SELECT
        *
      FROM
        json_to_recordset(result) unpack(x bigint, y bigint, cell bigint[])
    )

    Тогда наша "пересборка" матрицы с фиксацией значения в ячейке будет выглядеть примерно так:

    SELECT
      -- добавляем фиксируемую ячейку к json[] и превращаем в '[]'::json
      to_json(matrix_flt || vn) matrix
    FROM
      -- определяем фиксируемую ячейку
      (
        SELECT
          *
        FROM
          unpack
        WHERE
          array_length(cell, 1) > 1
        ORDER BY
          array_length(cell, 1), x, y
        LIMIT 1
      ) fix
      -- собираем отфильтрованный json без этой ячейки
    , LATERAL (
        SELECT
          array_agg(row_to_json(T)) FILTER(WHERE (x, y) <> (fix.x, fix.y)) matrix_flt
        FROM
          unpack T
      ) T0
      -- организуем перебор вариантов значений
    , LATERAL
        unnest(cell) n
      -- формируем json-представление этой ячейки с конкретным значением
    , LATERAL (
        SELECT
          row_to_json(T) vn
        FROM
          (
            SELECT
              x
            , y
            , ARRAY[n] cell
          ) T
      ) T1

    Причем, наша рекурсия должна работать "в два хода" - сначала вычисляя результат по уже зафиксированным значениям, а потом генерируя подстановки для следующего шага, примерно как в статье "SQL HowTo: пишем while-цикл прямо в запросе, или «Элементарная трехходовка»". Для этого воспользуемся UNION ALL с противоположными условиями:

    , rec_03 AS (
      SELECT
        '{}'::json[] fixpath
      , json_agg(row_to_json(T)) matrix
      , NULL::json result
      , TRUE has_many
      , FALSE has_none
      FROM
        base T
    UNION ALL
      (
        -- "материализуем" рекурсивную часть, чтобы обращаться к ней многократно
        WITH mv AS (
          TABLE rec_03
        )
        (
          -- вычисление результата "вычеркиваний"
          SELECT
            mv.fixpath
          , mv.matrix
          , T.result
          , T.has_many
          , T.has_none
          FROM
            mv
          , LATERAL (
              WITH RECURSIVE unpack AS (
                SELECT
                  *
                FROM
                  json_to_recordset(coalesce(result, matrix)) unpack(x bigint, y bigint, cell bigint[])
              )
              , rec_02 AS (
                SELECT
                  1 lvl
                , *
                FROM
                  unpack
              UNION ALL
                -- ...
              )
              , last_iter AS (
                SELECT
                  x
                , y
                , cell
                FROM
                  rec_02
                WHERE
                  lvl = (SELECT max(lvl) FROM rec_02)
              )
              SELECT
                json_agg(row_to_json(T)) result
              , bool_or(array_length(cell, 1) > 1) has_many   -- есть ячейки с несколькими значениями
              , bool_or(coalesce(cell, '{}') = '{}') has_none -- есть пустые ячейки
              FROM
                last_iter T
            ) T
          WHERE
            -- нечетный шаг
            mv.result IS NULL
        UNION ALL
          -- фиксация значений ячейки
          SELECT
            T.fixpath
          , T.matrix
          , NULL
          , mv.has_many
          , mv.has_none
          FROM
            mv
          , LATERAL (
              WITH unpack AS (
                SELECT
                  *
                FROM
                  json_to_recordset(coalesce(result, matrix)) unpack(x bigint, y bigint, cell bigint[])
              )
              -- ... пересборка матрицы
            ) T
          WHERE
            -- четный шаг
            mv.result IS NOT NULL AND
            -- пока нет пустых ячеек, но есть незафиксированные
            mv.has_many AND
            NOT mv.has_none
        )
      )
    )

    Обратите внимание, что unpack хоть и выглядит полностью одинаково, не может быть "вынесен за скобки", поскольку тогда будет применяться ко всем записям рекурсивного сегмента mv - а их там после unnest предыдущего шага заведомо несколько. А так использование LATERAL позволяет нам "распаковывать" каждую строку отдельно.

    Рисуем итоговую картинку

    -- находим запись с решением
    , unpack AS (
      SELECT
        *
      FROM
        json_to_recordset((
          SELECT
            result
          FROM
            rec_03
          WHERE
            NOT has_many AND -- нет вариативности
            NOT has_none     -- нет занулений
          LIMIT 1
        )) unpack(x bigint, y bigint, cell bigint[])
    )
    -- собираем в матрицу
    SELECT
      string_agg(
        lpad(cell[1]::text, (SELECT length(m::text) FROM side))
      , ' '
      ORDER BY x
      ) line
    FROM
      unpack
    GROUP BY
      y
    ORDER BY
      y;

    Общее время работы этого адового запроса - всего 250ms, ну, а полный его текст вы уже видели в начале статьи. (:

    Надеюсь, что-то для себя новое или интересное в нем найдете и вы.

    Тензор
    Разработчик системы СБИС

    Комментарии 8

      +6

      Во всём этом я не могу понять настроения. Это хорошо и здорово? Код по аннотированности находится где-то между ассемблером и брейнфаком. Имён мало, цикломатическая сложность зашкаливает, средств отладки и декомпозиции никаких....

        0
        За брейнфак не поручусь, но и asm имеет свои области применения, где иначе получается много хуже.
        Можно ведь и запросы писать много без чего — без рекурсии, CTE, LATERAL, да даже без JOIN можно — все вытаскивать на БЛ, а там обрабатывать. Но как-то это не очень эффективно бывает.
          +2
          Да, с этим кодом надо классику вспомнить:

          То мне страшно, то мне грустно, то теряю свой покой.
          Небоскребы, небоскребы, а я маленький такой.
            0

            Решать всякие судоку в принципе бессмысленно. От этого же нет никакой заметной пользы. И тем не менее многие залипают и получают удовольствие.

            0
            Я это прочитал? Да. Почувствовал себя овощем. Спасибо.
              +2

              Пора звать испанскую инквизицию. Без сделки с дьяволом тут точно не обошлось.

                +1
                Если это имеется ввиду в вакансиях когда пишется «Необходим опыт написания сложных запросов», то это совсем печально.
                  0

                  Смотрел на запрос, и почему-то вспомнилось вот это

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое