Используем TSQL для игры в «Судоку»

[shavluk]

10-15 секунд — как по мне, то долго
Вот мое решение
www.sql.ru/forum/925653/reshenie-sudoku-na-sql

[Leran2002]

Здесь, согласен с вами – для компьютера это очень долго.

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

Решение получено, теперь есть куда стремиться. ))
Думаю, основные тормоза происходят из-за выражения «t.VariantPath LIKE '%'+i.ID+'%'».

[Leran2002]

Добавив условие:

WHERE i.CellNo<@NextCellNo -- выше проверять нет смысла
  AND t.VariantPath LIKE '%'+i.ID+'%'

Уменьшил время выполнения почти в 2 раза:

• пример 1 — 6.157 сек.
• пример 2 — 6.607 сек.
• пример 3 — 4.847 сек.

[Leran2002]

Получил еще прирост в скорости, за счет уменьшения длины идентификатора варианта:

-- получаем допустимые цифры в пустых ячейках
SELECT
  -- формируем идентификатор варианта - укорачиваем его для более быстрого поиска
  RIGHT(CONCAT('0',CAST(CellNo AS varchar(2)),CHAR(ASCII('a')+Value-1)),3) ID,

Теперь решение находится в пределах 6 секунд:

• Пример 1: 4.547 сек.
• Пример 2: 5.317 сек.
• Пример 3: 3.690 сек.

Думаю, на этом поставлю точку.

[shavluk]

Проверил свое решение на ваших данных
1) 0.125 сек
2) 0.062 сек
3) 0.156 сек

Firebird 2.5

[galaxy]

Oracle, Postgres

[Leran2002]

Да, красивое и быстрое решение.
Проверил запрос для Oracle на тех же вариантах — решает в пределах 4-х секунд:
1) 1.079 сек. (мое решение — 10.930 сек.)
2) 2.991 сек. (мое решение — 12.970 сек.)
3) 3.037 сек. (мое решение — 9.047 сек.)

Oracle запрос...

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select '   15     34    89        3 2  6 8   47  9     9 2   11    2  5   9            74' sud from dual )
  --from ( select ' 71 9 8     3 6   49    7 5 1 9     9 2   6 3     8 2 8 5    76   6 7     7 4 35 ' sud from dual )
  --from ( select '      7     9 42 3 4 8 5     7 1 6  9          3    5262       7    3  9     8   ' sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0