Комментарии 22
Мне кажется это надо переместить в блог «Ненормальное Программирование», хотя Oracle обидится.
в заглавии ошибочка закралась досадная.
Отлично, снимаю шляпу!
После прочтения кажется, что в СУБД это сделать проще, чем на классическом языке программирования.
После прочтения кажется, что в СУБД это сделать проще, чем на классическом языке программирования.
В СУБД такие задачи решаются только «грубой силой»: генерацией всех возможных вариантов и последующей фильтрацией. Аналогично решаются задачи комивояжера и укладки рюкзака. Я как-то хотел реализовать решатель для игры «пятнашки» и даже что-то написал, но выполнить запрос не удалось — для него тупо не хватало памяти.
Может стоит как-то отформатировать код? А то действительно «ненормальным программированием» попахивает…
Заголовок поправлен
Это замечательно!
На sql-ex тоже была пара задачек на шахматную доску.
Рекомендую это ресурс для тренировок SQL-мышления =)
Рекомендую это ресурс для тренировок SQL-мышления =)
Условия у вас жесть. :)
Преподаю в вузе базы данных.
Я заставляю студентов в хранимках описывать классически алгоритмы:
Цель — пояснить разницу между процедурными языками и SQL.
+ тренировка по проектированию бд. пусть сами предлагают как они это хранить будут.
Получается красиво, когда пара вложенных циклов с условиями заменяется одним не сложным update-ом.
Хранимки пишем на MySQL.
sql-ex.ru — тоже рулит. Уже говорилось выше, я тоже его крайне рекомендую всем тем, кто хочет хорошо знать SQL.
Преподаю в вузе базы данных.
Я заставляю студентов в хранимках описывать классически алгоритмы:
- задача о N ферзях
- алгоритмы теории графов (поиск пути, определение связанности, построение каркаса и т.д. и т.п.)
Цель — пояснить разницу между процедурными языками и SQL.
+ тренировка по проектированию бд. пусть сами предлагают как они это хранить будут.
Получается красиво, когда пара вложенных циклов с условиями заменяется одним не сложным update-ом.
Хранимки пишем на MySQL.
sql-ex.ru — тоже рулит. Уже говорилось выше, я тоже его крайне рекомендую всем тем, кто хочет хорошо знать SQL.
А что за ВУЗ если не секрет?
Удивительно, прочел про этот пост только сегодня в твиттере — как-то незаметно прошло через 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)) )
Один знакомый с работы попробовал пооптимизировать с данной задачкой.
Ниже код который решает задачу в 5 раз быстрее, чем тот, что в статье.
Решение занимает 6 секунд.
Лучше поздно, чем никогда.
Ниже код который решает задачу в 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)
Лучше поздно, чем никогда.
Вот еще один вариант. Короткий и для любого размера доски (две константы поменять)
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
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о восьми Ферзях на Oracle SQL