|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
тут на днях всплывала тема про домино и 8 ферзей на шахматной доске. ну вот и подумал - а не забацать ли на оракле решение классической шахматной задачи коня. думаю, всем она известна, но на всякий случай: есть пустая шахматная доска (обыкновенная, фиде-европейская, размера 8x8 ) задача 1) за 64 хода обойти конем все её клетки (что, естественно, означает не наступать ни на какое поле дважды) задача 2) то же самое, но с условием что с поля 64-го хода конь может допрыгнуть до начальной своей позиции (то есть зациклить всю траекторию) решений в природе много. имхо, достаточно получить ~одно я решал на 11g. без pl/sql обойтись не смог (ну и еще чутка с алгоритмом подшаманил, но, надеюсь, что таки в рамках спортивных приличий ) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
удачи! ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 01:46 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-( ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 11:41 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishзадача 1) за 64 хода обойти конем все её клетки (что, естественно, означает не наступать ни на какое поле дважды) задача 2) то же самое, но с условием что с поля 64-го хода конь может допрыгнуть до начальной своей позиции (то есть зациклить всю траекторию) ... я решал на 11g. без pl/sql обойтись не смог 1 или 2? ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 11:56 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимо ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 14:40 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-( про неинтересно - не согласен. мне очень было интересно. кряхтел, потел, и очень доволен, что таки сделал. а вот про множественные решения могу сказать, что побочным продуктом процесса было строгое доказательство, что решений (задачи 2, даже без учета различий в начальном поле) много больше 1e6. на самом деле, очевидно что миллион это на много-много-много порядков грубая оценка того количества снизу (но, повторю, строгая = экспериментальная). ну, можно добавить: задача 3) - представить тех решений, допустим, 1001 задача 4) - оценить количество решений которое предлагаемый способ находит за одно исполнение (или какую-либо единицу времени) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 14:58 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:11 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно. а я вот сомневаюсь, что атомов во вселенной хватит, чтобы те все решения изобразить :) шейсятчетвертая - это очень большая степень (причем, и при среднем основании совсем не 2 ;) наивно пытаться окучить всю задачу бруттофорсом (имхо) - далеко не для нашего уровня развития технологий. да еще и симметрия (не только задачи, но и решения) чудовищная. так что - надо думать .. для затравки - в тех двух решениях, что я привел - есть очевидная подсказка ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:40 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:42 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения. не верю (c) :) кстати - парой постов выше я говорил про миллион решений, влёгкую полученных алгоритмом, обыгравшем отдельный (очень) частный случай. ну так я наврал (у того частного алгоритма) решений не менее чем 1e9 ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:56 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishandreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал? :) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:24 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxorawishandreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал? :) а, ну это же очевидно из решения - начало с концом на дистанции как раз одного хода - сталбыть 2) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, + то есть ответы тут для 2) , а алгоритму пофиг - находит и те, которые 1) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:34 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Для этого алгоритма есть оптимизация для полей очень большого размера. Там где классический поиск заходит в слишком долгий спуск и проверки. Суть в том что конь идёт не по всему полю а по "коридорам". ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 19:35 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonДля этого алгоритма есть оптимизация для полей очень большого размера. Там где классический поиск заходит в слишком долгий спуск и проверки. Суть в том что конь идёт не по всему полю а по "коридорам". ну так за чем же дело стало? вперёд! ;) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 19:43 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
я намекал, что в решении из стартового поста есть подсказка. тот кто хотел её найти, наверное, уже нашел.. (на 32 ходу или около того ;) на картинке три позиции - после ходов 1, 8 и 32 черная лошадь обозначает стартовую и финишную позицию траектории коня к соответствующему ходу, белая - прочие пройденные поля. то обстоятельство, что между 8 и 32 ходом изменилась не только конечная, но и начальная точка траектории - это еще одна подсказка :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 00:53 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Мой метод Эйлера остановился на 52 ходу а дальше уже думать надо :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 09:16 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxМой метод Эйлера остановился на 52 ходу а дальше уже думать надо :) 52 ход это же тринадцатый с конца, вот, наверное, и причина :) а если серьёзно - две вещи есть, над которыми стОит подумать 1) исключение из рассмотрения вариантов, которые при разнице в траектории к эн-ному ходу содержат одну и ту же картину на доске 2) исключение позиций, продолжение которых заведомо к решению не приведёт ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 11:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Мне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы) лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах. А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут . ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 12:01 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonМне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы) лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах. А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут . теория пусть себе развивается. развивать ли её или только использовать (или даже игнорировать ) - личный выбор каждого. форум то (вроде бы) про оракл. и тема (имхо) тоже про оракл. поговорить про алгоритмы на уровне абстрагированном от оракла пришлось - и это потому, что наиболее грубые подходы обречены в силу магии данных задачи. ну и (имхо) достаточно уже поговорили. пора бы и порешать ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 12:45 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishну и (имхо) достаточно уже поговорили. пора бы и порешать Скажем дружно "НЕТ" диктату на sql.ru! ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 14:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.По-моему квантовому компьютеру будет просто получить первое решение. Точно также, когда-то я изучал генетический алгоритм для расстановки ферзей на доске 300*300. Обычный метод на таких объемах загнется, а генетический алгоритм неплохо справляется с задачей поиска первого решения. Это, конечно, мало имеет общего с квантовыми вычислениями, но идея одна: максмиально бысто найти первое решение. Как бы там ни было с квантовым даже поэкспериментировать не удастся ибо эмулятор пока сделать невозможно. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 14:45 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Sql-брутфорс. Сервер слабоват проверить :), по идее должно работать. with field as ( select 'a1' s_name from dual union all select 'a2' s_name from dual union all select 'a3' s_name from dual union all select 'a4' s_name from dual union all select 'a5' s_name from dual union all select 'a6' s_name from dual union all select 'a7' s_name from dual union all select 'a8' s_name from dual union all select 'b1' s_name from dual union all select 'b2' s_name from dual union all select 'b3' s_name from dual union all select 'b4' s_name from dual union all select 'b5' s_name from dual union all select 'b6' s_name from dual union all select 'b7' s_name from dual union all select 'b8' s_name from dual union all select 'c1' s_name from dual union all select 'c2' s_name from dual union all select 'c3' s_name from dual union all select 'c4' s_name from dual union all select 'c5' s_name from dual union all select 'c6' s_name from dual union all select 'c7' s_name from dual union all select 'c8' s_name from dual union all select 'd1' s_name from dual union all select 'd2' s_name from dual union all select 'd3' s_name from dual union all select 'd4' s_name from dual union all select 'd5' s_name from dual union all select 'd6' s_name from dual union all select 'd7' s_name from dual union all select 'd8' s_name from dual union all select 'e1' s_name from dual union all select 'e2' s_name from dual union all select 'e3' s_name from dual union all select 'e4' s_name from dual union all select 'e5' s_name from dual union all select 'e6' s_name from dual union all select 'e7' s_name from dual union all select 'e8' s_name from dual union all select 'f1' s_name from dual union all select 'f2' s_name from dual union all select 'f3' s_name from dual union all select 'f4' s_name from dual union all select 'f5' s_name from dual union all select 'f6' s_name from dual union all select 'f7' s_name from dual union all select 'f8' s_name from dual union all select 'g1' s_name from dual union all select 'g2' s_name from dual union all select 'g3' s_name from dual union all select 'g4' s_name from dual union all select 'g5' s_name from dual union all select 'g6' s_name from dual union all select 'g7' s_name from dual union all select 'g8' s_name from dual union all select 'h1' s_name from dual union all select 'h2' s_name from dual union all select 'h3' s_name from dual union all select 'h4' s_name from dual union all select 'h5' s_name from dual union all select 'h6' s_name from dual union all select 'h7' s_name from dual union all select 'h8' s_name from dual ) select /*+FIRST_ROWS */ steps from ( select t.*, level lvl, SYS_CONNECT_BY_PATH(s_name, '/') steps from ( select row_number() over(order by s_name) id, f.s_name, row_number() over(order by s_name) parent_id from field f ) t where level <= 64 connect by NOCYCLE ( ( (id = prior parent_id + 10 and mod(prior parent_id, 8) not in (0, 7)) or (id = prior parent_id - 6 and mod(prior parent_id, 8) not in (0, 7)) or (id = prior parent_id + 17 and mod(prior parent_id, 8) not in (0)) or (id = prior parent_id - 15 and mod(prior parent_id, 8) not in (0)) or (id = prior parent_id - 10 and mod(prior parent_id, 8) not in (1, 2))or (id = prior parent_id + 6 and mod(prior parent_id, 8) not in (1, 2)) or (id = prior parent_id - 17 and mod(prior parent_id, 8) not in (1)) or (id = prior parent_id + 15 and mod(prior parent_id, 8) not in (1)) ) ) start with s_name = 'c4' ) where lvl = 64 and rownum = 1; ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 15:15 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать.. о, дак это легко проверяется. запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 15:58 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать.. о, дак это легко проверяется. запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному.а где-то с четырнадцатого - по четверти :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:02 |
|
|
start [/forum/topic.php?fid=52&fpage=49&tid=1881402]: |
0ms |
get settings: |
11ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
40ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
2ms |
others: | 16ms |
total: | 163ms |
0 / 0 |