Задача о восьми Ферзях на 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: Перенесено в «Ненормальное программирование»
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 22

      +18
      Мне кажется это надо переместить в блог «Ненормальное Программирование», хотя Oracle обидится.
        0
        Перенесено
        0
        в заглавии ошибочка закралась досадная.
          +6
          image
          Она существует, да.
          0
          Отлично, снимаю шляпу!
          После прочтения кажется, что в СУБД это сделать проще, чем на классическом языке программирования.
            0
            В СУБД такие задачи решаются только «грубой силой»: генерацией всех возможных вариантов и последующей фильтрацией. Аналогично решаются задачи комивояжера и укладки рюкзака. Я как-то хотел реализовать решатель для игры «пятнашки» и даже что-то написал, но выполнить запрос не удалось — для него тупо не хватало памяти.
            +2
            Может стоит как-то отформатировать код? А то действительно «ненормальным программированием» попахивает…
              0
              Да. Как только доберусь до большого компании — поправлю.
                +3
                Большого компа конечно же, iPad развлекается автоподстановкой)
                0
                Таки оформил=)
                +1
                Заголовок поправлен
                  0
                  Это замечательно!
                    +3
                    На sql-ex тоже была пара задачек на шахматную доску.
                    Рекомендую это ресурс для тренировок SQL-мышления =)
                      +2
                      Еще есть SQL.ru с пятничными задачками
                      +4
                      Условия у вас жесть. :)

                      Преподаю в вузе базы данных.
                      Я заставляю студентов в хранимках описывать классически алгоритмы:
                      • задача о N ферзях
                      • алгоритмы теории графов (поиск пути, определение связанности, построение каркаса и т.д. и т.п.)

                      Цель — пояснить разницу между процедурными языками и SQL.
                      + тренировка по проектированию бд. пусть сами предлагают как они это хранить будут.

                      Получается красиво, когда пара вложенных циклов с условиями заменяется одним не сложным update-ом.
                      Хранимки пишем на MySQL.
                      sql-ex.ru — тоже рулит. Уже говорилось выше, я тоже его крайне рекомендую всем тем, кто хочет хорошо знать SQL.
                        +2
                        А что за ВУЗ если не секрет?
                          0
                          Тамбовский ГТУ. Провинция, короче.
                            0
                            На ИТ-Планете 2года подряд приз берет парень с Сахалина
                          0
                          Удивительно, прочел про этот пост только сегодня в твиттере — как-то незаметно прошло через rss :) Свой вариант сделал, не заглядывая в топик однако кое-что смотрю у нас похоже(правда, я старался сгольфить-решить кратко):
                          with t as (
                                    select level-1 n 
                                    from dual 
                                    connect by level<=8
                          )
                          select 
                             lpad(to_char(power(10,t1.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t2.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t3.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t4.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t5.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t6.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t7.n)),8,'0')||chr(13)
                           ||lpad(to_char(power(10,t8.n)),8,'0')||chr(13) "В графическом виде"
                           ,chr(97+t1.n)||'1' "1"
                           ,chr(97+t2.n)||'2' "2"
                           ,chr(97+t3.n)||'3' "3"
                           ,chr(97+t4.n)||'4' "4"
                           ,chr(97+t5.n)||'5' "5"
                           ,chr(97+t6.n)||'6' "6"
                           ,chr(97+t7.n)||'7' "7"
                           ,chr(97+t8.n)||'8' "8"
                          from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8
                          where 
                           power(2,t1.n)+power(2,t2.n)+power(2,t3.n)+power(2,t4.n)+power(2,t5.n)
                             +power(2,t6.n)+power(2,t7.n)+power(2,t8.n) = 255
                           and not exists(
                             select null
                             from 
                               table(sys.odcinumberlist(t1.n+11,t2.n+21,t3.n+31,t4.n+41,t5.n+51,t6.n+61,t7.n+71,t8.n+81)) x1
                              ,table(sys.odcinumberlist(t1.n+11,t2.n+21,t3.n+31,t4.n+41,t5.n+51,t6.n+61,t7.n+71,t8.n+81)) x2
                             where 
                               x1.column_value>x2.column_value
                               and abs(trunc(x1.column_value/10)-trunc(x2.column_value/10))
                                   = abs(mod(x1.column_value,10)-mod(x2.column_value,10))
                           )
                          
                            0
                            Один знакомый с работы попробовал пооптимизировать с данной задачкой.
                            Ниже код который решает задачу в 5 раз быстрее, чем тот, что в статье.
                            Решение занимает 6 секунд.

                            with a as
                            (select f.k1,
                                  (select    regexp_replace(
                                             max(sys_connect_by_path(
                                             case when
                                               (case mod(level,8) when  0 then 8 else mod(level,8) end=substr(f.k1,1,1)
                                                or  ceil(level/8)=substr(f.k1,2,1)
                                                or  abs(case mod(level,8) when  0 then 8 else mod(level,8) 
                                                 end-substr(f.k1,1,1))=abs(ceil(level/8)-substr(f.k1,2,1)))
                                             then
                                             (case mod(level,8) when  0 then 8 else mod(level,8) end||ceil(level/8) ) end
                                              ,',')),'[,]+',',')
                                   from dual
                                   connect by level<=64)k2
                            from
                            (select case mod(level,8) when  0 then 8 else mod(level,8) end||ceil(level/8) k1
                            from dual connect by level<=64)f),
                            a1 as(select * from a where a.k1 like '1_'),
                            a2 as(select * from a where a.k1 like '2_'),
                            a3 as(select * from a where a.k1 like '3_'),
                            a4 as(select * from a where a.k1 like '4_'),
                            a5 as(select * from a where a.k1 like '5_'),
                            a6 as(select * from a where a.k1 like '6_'),
                            a7 as(select * from a where a.k1 like '7_'),
                            a8 as(select * from a where a.k1 like '8_')
                            select a1.k1 f1,a2.k1 f2,a3.k1,a4.k1,a5.k1,a6.k1,a7.k1,a8.k1
                            from  a1,a2,a3,a4,a5,a6,a7,a8
                            where not regexp_like
                             (a1.k2,','||a2.k1||'|'||a3.k1||'|'||a4.k1||'|'||a5.k1||'|'||a6.k1||'|'||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a2.k2,','||a3.k1||'|'||a4.k1||'|'||a5.k1||'|'||a6.k1||'|'||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a3.k2,','||a4.k1||'|'||a5.k1||'|'||a6.k1||'|'||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a4.k2,','||a5.k1||'|'||a6.k1||'|'||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a5.k2,','||a6.k1||'|'||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a6.k2,','||a7.k1||'|'||a8.k1)
                            and   not regexp_like (a7.k2,','||a8.k1)


                            Лучше поздно, чем никогда.
                              0
                              Несколько оптимизировал, точнее написал с нуля и получилось оптимальнее тут.
                                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
                                

                                Only users with full accounts can post comments. Log in, please.