суббота, 10 сентября 2011 г.

Задача о восьми Ферзях на Oracle SQL


Привет, Хабролюди!



В мае месяце в Москве прошла олимпиада IT-Планета, одной из номинаций которой было «Программирование СУБД Oracle». Задания были интересными и сложными, и хотелось бы поделиться решением некоторых из них.

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





Итак, задача озвучена, ответ необходимо представить в виде:

 A     B    C     D    E     F    G    H

---  ---  ---  ---  ---  ---  ---  --- 

 a7   b4   c2   d8   e6   f1   g3   h5



Как же такое решается:

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

Средствами иерархических запросов Oracle (а конкретно connect by level), создаем запрос, который выдает числа от 1 до 8:

select level a from dual connect by level <= 8



* This source code was highlighted with Source Code Highlighter.


Это возможные позиции Ферзя на A (A1, A2, …)

Делаем cross join восьми таких запросов, в каждом следующем меняя букву для наглядности:

select level a from dual connect by level <= 8

cross join

(select level b from dual connect by level <= 8)

cross join

(select level c from dual connect by level <= 8)

cross join

(select level d from dual connect by level <= 8)

cross join

(select level e from dual connect by level <= 8)

cross join

(select level f from dual connect by level <= 8)

cross join

(select level g from dual connect by level <= 8)

cross join

(select level h from dual connect by level <= 8)




* This source code was highlighted with Source Code Highlighter.




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

Решая задачу, вначале я убрал все с вертикалей:

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 a, b, c, d, e, f, g, h ,

 case when a = b or a = c or a = d or a = e or a = f or a = g or a = h

    then 0

    else case when b = c or b = d or b = e or b = f or b = g or b = h

        then 0

        else case when c = d or c = e or c = f or c = g or c = h

             then 0

             else case when d = e or d = f or d = g or d = h

                then 0

                else case when e = f or e = g or e = h

                     then 0

                     else case when f = g or f = h

                       then 0

                       else case when g = h

                            then 0

                            else 1

                       end

                     end

                end

             end               

           end

        end

 end chk

from

(select level a from dual connect by level <= 8)

cross join

(select level b from dual connect by level <= 8)

cross join

(select level c from dual connect by level <= 8)

cross join

(select level d from dual connect by level <= 8)

cross join

(select level e from dual connect by level <= 8)

cross join

(select level f from dual connect by level <= 8)

cross join

(select level g from dual connect by level <= 8)

cross join

(select level h from dual connect by level <= 8)

)

where chk = 1




* This source code was highlighted with Source Code Highlighter.




Теперь остался последний этап, на котором я убрал все с диагоналей:

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 a, b, c, d, e, f, g, h ,

 case when a = b or a = b - 1 or a = b + 1 or a = c or a = c - 2 or a = c + 2 or a = d or a = d - 3 or a = d + 3 or a = e or a = e - 4 or a = e + 4 or a = f or a = f - 5 or a = f + 5 or a = g or a = g - 6 or a = g + 6 or a = h or a = h - 7 or a = h + 7 

    then 0

    else case when b = c or b = c - 1 or b = c + 1 or b = d or b = d - 2 or b = d + 2 or b = e or b = e - 3 or b = e + 3 or b = f or b = f - 4 or b = f + 4 or b = g or b = g - 5 or b = g + 5 or b = h or b = h - 6 or b = h + 6

        then 0

        else case when c = d or c = d - 1 or c = d + 1 or c = e or c = e - 2 or c = e + 2 or c = f or c = f - 3 or c = f + 3 or c = g or c = g - 4 or c = g + 4 or c = h or c = h - 5 or c = h + 5

             then 0

             else case when d = e or d = e - 1 or d = e + 1 or d = f or d = f - 2 or d = f + 2 or d = g or d = g - 3 or d = g + 3 or d = h or d = h - 4 or d = h + 4

                then 0

                else case when e = f or e = f - 1 or e = f + 1 or e = g or e = g - 2 or e = g + 2 or e = h or e = h - 3 or e = h + 3

                     then 0

                     else case when f = g or f = g - 1 or f = g + 1 or f = h or f = h - 2 or f = h + 2

                       then 0

                       else case when g = h or g = h - 1 or g = h + 1

                            then 0

                            else 1

                       end

                     end

                end

             end               

           end

        end

 end chk

from

(select level a from dual connect by level <= 8)

cross join

(select level b from dual connect by level <= 8)

cross join

(select level c from dual connect by level <= 8)

cross join

(select level d from dual connect by level <= 8)

cross join

(select level e from dual connect by level <= 8)

cross join

(select level f from dual connect by level <= 8)

cross join

(select level g from dual connect by level <= 8)

cross join

(select level h from dual connect by level <= 8)

)

where chk = 1




* This source code was highlighted with Source Code Highlighter.




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

Данное решение абсолютно законно и дает все 92 решения данной задачи.



UPD: Перенесено в «Ненормальное программирование»









Источник: Хабрахабр - Ненормальное программирование
Оригинальная страница: Задача о восьми Ферзях на Oracle SQL

Комментариев нет:

Отправить комментарий