Pull to refresh

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

Reading time 3 min
Views 7.9K
В ответ на это решение, хотелось бы указать своё, несколько более простое к восприятию.

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

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. Решение было сделано после прочтения условия задачи, до написания своего к автору не подглядывал.
Tags:
Hubs:
+6
Comments 7
Comments Comments 7

Articles