Задача о восьми Ферзях на Oracle SQL (другое решение)

[maovrn]

Выглядит компактно и работает шустро. На моей машинке 0.12 секунды. На ней же предыдущее решение 16.87 секунд. Круто!

[JuraZ]

Красивое решение, спасибо. Для тех кто на MS SQL:

WITH CTE AS (
  SELECT 1 as n
  UNION ALL
  SELECT n+1
  FROM CTE 
  WHERE n < 8
)

SELECT A.n as 'A', B.n as 'B', C.n as 'C', D.n as 'D', E.n as 'E', F.n as 'F', G.n as 'G', H.n as 'H'
FROM CTE AS A
CROSS JOIN CTE AS B
CROSS JOIN CTE AS C
CROSS JOIN CTE AS D
CROSS JOIN CTE AS E
CROSS JOIN CTE AS F
CROSS JOIN CTE AS G
CROSS JOIN CTE AS H
WHERE A.n NOT IN (B.n,C.n,D.n,E.n,F.n,G.n,H.n,B.n+1,C.n+2,D.n+3,E.n+4,F.n+5,G.n+6,H.n+7,B.n-1,C.n-2,D.n-3,E.n-4,F.n-5,G.n-6,H.n-7)
  AND B.n NOT IN (C.n,D.n,E.n,F.n,G.n,H.n,C.n+1,D.n+2,E.n+3,F.n+4,G.n+5,H.n+6,C.n-1,D.n-2,E.n-3,F.n-4,G.n-5,H.n-6)
  AND C.n NOT IN (D.n,E.n,F.n,G.n,H.n,D.n+1,E.n+2,F.n+3,G.n+4,H.n+5,D.n-1,E.n-2,F.n-3,G.n-4,H.n-5)
  AND D.n NOT IN (E.n,F.n,G.n,H.n,E.n+1,F.n+2,G.n+3,H.n+4,E.n-1,F.n-2,G.n-3,H.n-4)
  AND E.n NOT IN (F.n,G.n,H.n,F.n+1,G.n+2,H.n+3,F.n-1,G.n-2,H.n-3)
  AND F.n NOT IN (G.n,H.n,G.n+1,H.n+2,G.n-1,H.n-2)
  AND G.n NOT IN (H.n,H.n+1,H.n-1)
ORDER BY A.n,B.n,C.n,D.n,E.n,F.n,G.n

[Ildarovich]

Вот гораздо более короткое и гибкое решение (легко подстраивается под размер доски)

with 
    x(i) as (select level from dual connect by level <= 8),
    q(z, w) as (select '0', '' from dual 
                union all 
                select z || i, w || substr('abcdefgh', length(z), 1) || i || ' ' from q cross join x 
                    where length(z) <= 8 
                    and 0 = (select count(*) from x y 
                             where length(z) > y.i
                             and (to_number(substr(z, y.i + 1, 1)) - x.i) / (length(z) - y.i) IN (-1, 0, 1))) 

cycle z set cyclemark to 'X' default '-'

select w from q where length(z) - 1 = 8

.

[Apkc]

Класс, а можете детально рассказать что и какой кусок делает? А то сложно разобраться немного…

[Ildarovich]

Остовом запроса является конструкция

with 
    x(i) as (select level from dual connect by level <= 8),
    q(z) as (select '.' from dual 
                union all 
                select z || i from q inner join x 
                    on length(z) < 8) 

select * from q

Она позволяет перечислить все пути дерева поиска. Конкретный путь представляет собой строку, цифры которой обозначают положение ферзя в соответствующей линии.
Первый запрос определяет таблицу х чисел от 1 до 8.
Второй запрос — собственно рекурсия, которая на каждом шаге продолжает пути (дополняет строки) всеми вариантами из таблицы х.
В полученной таблице q в виде строк находятся все возможные пути длины до 8 включительно.
Условие

where length(z) - 1 = 8

позволяет выделить полные пути, где расположены все восемь ферзей.
Усложнение основного запроса связано с проверкой, чтобы положение ферзя в текущей линии не пересекалось с уже зафиксированными в дополняемой строке положениями других ферзей на предыдущих линиях.
Это выполняется путем проверки

not 1 in (select 1 from x y 
              where length(z) > y.i
              and (x.i - substr(z, y.i + 1, 1)) / (length(z) - y.i) IN (-1, 0, 1))

Смысл проверки в том, что положение ферзя в каждой из позиций y.i + 1 строки z, вычтенное из положения последнего ферзя, деленное на расстояние между колонками ферзей length(z) — y.i, не должно давать 1, 0 или -1.
Иначе они будут стоять по основной диагонали, в одной строке ил по побочной диагонали. Если ни одного такого ферзя не найдется, то результат запроса будет пустым и проверка выполнится — будет найдено разрешенное положение размещаемого ферзя.
Длину уже можно не проверять — так как больше 8 ферзей в 8-ми колонках не разместить.
Получаем

with 
    x(i) as (select level from dual connect by level <= 8),
    q(z) as (select '.' from dual 
                union all 
                select z || i from q inner join x 
                    on not 1 in (select 1 from x y 
                                     where length(z) > y.i
                                     and (x.i - substr(z, y.i + 1, 1)) / (length(z) - y.i) IN (-1, 0, 1))) 

select * from q where length(z) - 1 = 8

Ну и напоследок вводится поле w = w || substr('abcdefgh', length(z), 1) || i || ' ', в котором путь параллельно выращивается в требуемом формате.
В итоге получаем

with 
    x(i) as (select level from dual connect by level <= 8),
    q(z, w) as (select '.', '' from dual 
                union all 
                select z || i, w || substr('abcdefgh', length(z), 1) || i || ' ' from q inner join x 
                    on not 1 in (select 1 from x y 
                                     where length(z) > y.i
                                     and (x.i - substr(z, y.i + 1, 1)) / (length(z) - y.i) IN (-1, 0, 1))) 

cycle z set cyclemark to 'X' default '-'

select w from q where length(z) - 1 = 8

Конструкция

cycle z set cyclemark to 'X' default '-'

служит для контроля зацикленности рекурсии.

[Apkc]

Спасибо огромное! По этой Вашей наводке сейчас строю решение ещё одной задачки попутно изучая рекурсию.

[Ildarovich]

После небольшого рефакторинга запрос стал еще проще

with 
    x(i) as (select level from dual connect by level <= 8),
    q(z, j) as (select '', 1 from dual 
                union all 
                select z || y.i, j + 1 from q inner join x y 
                    on not exists(select 1 from x where i < j and (y.i - substr(z, i, 1)) / (j - i) IN (-1, 0, 1))) 

cycle z set cyclemark to 'X' default '-'

select translate('a1 b2 c3 d4 e5 f6 h7 g8', '12345678', z) from q where j = 8 + 1