Пользователь
0,0
рейтинг
2 июля 2014 в 12:09

Разработка → Задача о восьми Ферзях на Oracle SQL (другое решение) из песочницы

В ответ на это решение, хотелось бы указать своё, несколько более простое к восприятию.

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

select *
from
  (select level as A from Dual connect by level<=8) A
  cross join
  (select level as B from Dual connect by level<=8) B
  cross join
  (select level as C from Dual connect by level<=8) C
  cross join
  (select level as D from Dual connect by level<=8) D
  cross join
  (select level as E from Dual connect by level<=8) E
  cross join
  (select level as F from Dual connect by level<=8) F
  cross join
  (select level as G from Dual connect by level<=8) G
  cross join
  (select level as H from Dual connect by level<=8) H;


А вот дальше я решил двигаться несколько более простым методом. Сформировав указанным методом массив мы, да, получили доски, где в каждой вертикали находится по одному ферзю. Соответственно необходимо отфильтровать только горизонтали и диагонали. И здесь я решил воспользоваться конструкцией not x in (y,z). Для горизонталей всё просто:

where
  not A in (B,C,D,E,F,G,H)
  and not B in (A,C,D,E,F,G,H)
...
  and not H in (A,B,C,D,E,F,G)


Эту конструкцию так же можно сократить, поскольку not A in (B) = not B in (A) и т.д., получаем:

where
  not A in (B,C,D,E,F,G,H)
  and not B in (C,D,E,F,G,H)
...
  and not G in (H)


Минус одна строка, и вообще в два раза меньше сравнений.

Далее диагонали — таким же самым методом с учётом построчного сдвига:

where
  not A in (B+1,C+2,D+3,E+4,F+5,G+6,H+7)
  and not B in (A-1,C+1,D+2,E+3,F+4,G+5,H+6)
...
  and not H in (A-7,B-6,C-5,D-4,E-3,F-2,G-1)


И так же, т.к. not A in (B+1) = not B in (A-1) убираем лишние сравнения:

where
  not A in (B+1,C+2,D+3,E+4,F+5,G+6,H+7)
  and not B in (C+1,D+2,E+3,F+4,G+5,H+6)
...
  and not G in (H+1)


Чтобы отфильтровать и вторую диагональ — просто дублируем код первой диагонали с полной заменой знака на противоположный:

where
  not A in (B-1,C-2,D-3,E-4,F-5,G-6,H-7)
  and not B in (C-1,D-2,E-3,F-4,G-5,H-6)
...
  and not G in (H-1)


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

Чтобы всё выглядело оптимально и без затроения в where я сгруппировал все условия:

where not A in (B,C,D,E,F,G,H,B+1,C+2,D+3,E+4,F+5,G+6,H+7,B-1,C-2,D-3,E-4,F-5,G-6,H-7)
  and not B in (C,D,E,F,G,H,C+1,D+2,E+3,F+4,G+5,H+6,C-1,D-2,E-3,F-4,G-5,H-6)
  and not C in (D,E,F,G,H,D+1,E+2,F+3,G+4,H+5,D-1,E-2,F-3,G-4,H-5)
  and not D in (E,F,G,H,E+1,F+2,G+3,H+4,E-1,F-2,G-3,H-4)
  and not E in (F,G,H,F+1,G+2,H+3,F-1,G-2,H-3)
  and not F in (G,H,G+1,H+2,G-1,H-2)
  and not G in (H,H+1,H-1)


И в конце концов, форматируем вывод, согласно требований в условии и добавляем сортировку, чтобы ответ выглядел прилично:

select 'a' || A A, 'b' || B B, 'c' || C C, 'd' || D D, 'e' || E E, 'f' || F F, 'g' || G G, 'h' || H H
from
  (select level as A from Dual connect by level<=8) A
  cross join
  (select level as B from Dual connect by level<=8) B
  cross join
  (select level as C from Dual connect by level<=8) C
  cross join
  (select level as D from Dual connect by level<=8) D
  cross join
  (select level as E from Dual connect by level<=8) E
  cross join
  (select level as F from Dual connect by level<=8) F
  cross join
  (select level as G from Dual connect by level<=8) G
  cross join
  (select level as H from Dual connect by level<=8) H
where not A in (B,C,D,E,F,G,H,B+1,C+2,D+3,E+4,F+5,G+6,H+7,B-1,C-2,D-3,E-4,F-5,G-6,H-7)
  and not B in (C,D,E,F,G,H,C+1,D+2,E+3,F+4,G+5,H+6,C-1,D-2,E-3,F-4,G-5,H-6)
  and not C in (D,E,F,G,H,D+1,E+2,F+3,G+4,H+5,D-1,E-2,F-3,G-4,H-5)
  and not D in (E,F,G,H,E+1,F+2,G+3,H+4,E-1,F-2,G-3,H-4)
  and not E in (F,G,H,F+1,G+2,H+3,F-1,G-2,H-3)
  and not F in (G,H,G+1,H+2,G-1,H-2)
  and not G in (H,H+1,H-1)
order by A, B, C, D, E, F, G, H;


P.S. Жаль, что я не участвовал в этой олимпиаде.

P.P.S. Решение было сделано после прочтения условия задачи, до написания своего к автору не подглядывал.
@Apkc
карма
3,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (7)

  • 0
    Выглядит компактно и работает шустро. На моей машинке 0.12 секунды. На ней же предыдущее решение 16.87 секунд. Круто!
  • 0
    Красивое решение, спасибо. Для тех кто на 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
    


  • 0
    Вот гораздо более короткое и гибкое решение (легко подстраивается под размер доски)
    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
    
    .
    • 0
      Класс, а можете детально рассказать что и какой кусок делает? А то сложно разобраться немного…
      • 0
        Остовом запроса является конструкция
        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 '-'
        

        служит для контроля зацикленности рекурсии.
        • 0
          Спасибо огромное! По этой Вашей наводке сейчас строю решение ещё одной задачки попутно изучая рекурсию.
    • 0
      После небольшого рефакторинга запрос стал еще проще
      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
      

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