Comments 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
Sign up to leave a comment.
Задача о восьми Ферзях на Oracle SQL