powered by simpleCommunicator - 2.0.52     © 2025 Programmizd 02
Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня
25 сообщений из 118, страница 1 из 5
пятничная задачка (про) коня
    #37733264
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тут на днях всплывала тема про домино и 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.
 

-----------------------------------------------------------------
SQL> create or replace package pk as
..
 16  /

Package created.

SQL> create or replace package body pk as
..
 83  /

Package body created.

SQL> set timing on linesize 120
SQL> with tt as (select  1 dx , 2 dy from dual
  2  	   union select  1    ,-2    from dual
  3  	   union select  2    , 1    from dual
  4  	   union select  2    ,-1    from dual
  5  	   union select -1    , 2    from dual
  6  	   union select -1    ,-2    from dual
  7  	   union select -2    , 1    from dual
  8  	   union select -2    ,-1    from dual
 ..
101  	;

R                                                                                                                       
------------------------------------------------------------------------------------------------------------------------
 f4 d3 b4 a2 c1 e2 g1 h3 g5 h7 f8 e6 c5 a6 b8 d7 b6 a8 c7 d5 f6 e8 g7 h5 g3 h1 f2 d1 b2 a4 c3 e4 d2 b1 a3 b5 a7 c6 a5 b3
 a1 c2 d4 f5 h4 g2 e1 f3 e5 c4 e3 f1 h2 g4 h6 g8 e7 c8 d6 b7 d8 f7 h8 g6                                                
                                                                                                                        
 f4 d3 b4 a2 c1 e2 g1 h3 g5 h7 f8 e6 c5 a6 b8 d7 b6 a8 c7 d5 f6 e8 g7 h5 g3 h1 f2 d1 b2 a4 c3 e4 d2 b1 a3 b5 a7 c6 a5 b3
 a1 c2 d4 f5 h4 g6 h8 f7 d8 b7 d6 c8 e7 g8 h6 g4 e5 c4 e3 f1 h2 f3 e1 g2                                                
                                                                                                                        

Elapsed: 00:00:27.29


 



удачи!
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733387
Bfink
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-(
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733402
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishзадача 1) за 64 хода обойти конем все её клетки (что, естественно, означает не наступать ни на какое поле дважды)
задача 2) то же самое, но с условием что с поля 64-го хода конь может допрыгнуть до начальной своей позиции
(то есть зациклить всю траекторию)
...

я решал на 11g. без pl/sql обойтись не смог 1 или 2?
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733480
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andreymx,

Код: plsql
1.
2.
Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - 64bit Production
With the Partitioning, OLAP, Data Mining and Real Application Testing options



но, навскидку, с 11.1 совместимо
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733487
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Bfinkorawish,

Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-(

про неинтересно - не согласен. мне очень было интересно. кряхтел, потел, и очень доволен, что таки сделал.

а вот про множественные решения могу сказать, что побочным продуктом процесса было строгое
доказательство, что решений (задачи 2, даже без учета различий в начальном поле) много больше 1e6.
на самом деле, очевидно что миллион это на много-много-много порядков грубая оценка того количества снизу
(но, повторю, строгая = экспериментальная).
ну, можно добавить:

задача 3) - представить тех решений, допустим, 1001
задача 4) - оценить количество решений которое предлагаемый способ находит за одно исполнение
(или какую-либо единицу времени)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733501
Bfink
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733518
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Bfinkorawish,

я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно.
а я вот сомневаюсь, что атомов во вселенной хватит, чтобы те все решения изобразить :)
шейсятчетвертая - это очень большая степень (причем, и при среднем основании совсем не 2 ;)
наивно пытаться окучить всю задачу бруттофорсом (имхо) - далеко не для нашего уровня развития технологий.
да еще и симметрия (не только задачи, но и решения) чудовищная.

так что - надо думать ..

для затравки - в тех двух решениях, что я привел - есть очевидная подсказка
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733521
Bfink
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733534
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Bfinkorawish,

я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.
не верю (c) :)
кстати - парой постов выше я говорил про миллион решений, влёгкую полученных алгоритмом, обыгравшем
отдельный (очень) частный случай. ну так я наврал (у того частного алгоритма) решений не менее чем 1e9
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733590
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishandreymx,

Код: plsql
1.
2.
Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - 64bit Production
With the Partitioning, OLAP, Data Mining and Real Application Testing options




но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал?
:)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733593
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andreymxorawishandreymx,

Код: plsql
1.
2.
Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - 64bit Production
With the Partitioning, OLAP, Data Mining and Real Application Testing options




но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал?
:)
а, ну это же очевидно из решения - начало с концом на дистанции как раз одного хода - сталбыть 2)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733595
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andreymx,

+ то есть ответы тут для 2) , а алгоритму пофиг - находит и те, которые 1)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733686
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для этого алгоритма есть оптимизация для полей очень большого размера.
Там где классический поиск заходит в слишком долгий спуск и проверки.
Суть в том что конь идёт не по всему полю а по "коридорам".
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733692
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДля этого алгоритма есть оптимизация для полей очень большого размера.
Там где классический поиск заходит в слишком долгий спуск и проверки.
Суть в том что конь идёт не по всему полю а по "коридорам".
ну так за чем же дело стало? вперёд! ;)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733993
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
я намекал, что в решении из стартового поста есть подсказка.
тот кто хотел её найти, наверное, уже нашел.. (на 32 ходу или около того ;)

на картинке три позиции - после ходов 1, 8 и 32
черная лошадь обозначает стартовую и финишную позицию траектории коня к соответствующему ходу,
белая - прочие пройденные поля. то обстоятельство, что между 8 и 32 ходом изменилась не только конечная,
но и начальная точка траектории - это еще одна подсказка :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37733994
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734123
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мой метод Эйлера остановился на 52 ходу
а дальше уже думать надо
:)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734303
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andreymxМой метод Эйлера остановился на 52 ходу
а дальше уже думать надо
:)
52 ход это же тринадцатый с конца, вот, наверное, и причина :)
а если серьёзно - две вещи есть, над которыми стОит подумать
1) исключение из рассмотрения вариантов, которые при разнице в траектории к эн-ному ходу
содержат одну и ту же картину на доске
2) исключение позиций, продолжение которых заведомо к решению не приведёт
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы)
лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах.

А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут .
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734461
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonМне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы)
лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах.

А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут .
теория пусть себе развивается. развивать ли её или только использовать (или даже игнорировать ) - личный выбор каждого.
форум то (вроде бы) про оракл. и тема (имхо) тоже про оракл. поговорить про алгоритмы на уровне абстрагированном
от оракла пришлось - и это потому, что наиболее грубые подходы обречены в силу магии данных задачи.
ну и (имхо) достаточно уже поговорили. пора бы и порешать
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734663
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishну и (имхо) достаточно уже поговорили. пора бы и порешать Скажем дружно "НЕТ" диктату на sql.ru!
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734695
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Bfinkorawish,

я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.По-моему квантовому компьютеру будет просто получить первое решение.
Точно также, когда-то я изучал генетический алгоритм для расстановки ферзей на доске 300*300. Обычный метод на таких объемах загнется, а генетический алгоритм неплохо справляется с задачей поиска первого решения. Это, конечно, мало имеет общего с квантовыми вычислениями, но идея одна: максмиально бысто найти первое решение.
Как бы там ни было с квантовым даже поэкспериментировать не удастся ибо эмулятор пока сделать невозможно. :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734749
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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;
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734819
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать..
о, дак это легко проверяется.
запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734830
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать..
о, дак это легко проверяется.
запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному.а где-то с четырнадцатого - по четверти
:)
...
Рейтинг: 0 / 0
25 сообщений из 118, страница 1 из 5
Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]