Гость
Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня / 25 сообщений из 118, страница 1 из 5
01.04.2012, 01:46
    #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
01.04.2012, 11:41
    #37733387
Bfink
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
пятничная задачка (про) коня
orawish,

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

я решал на 11g. без pl/sql обойтись не смог 1 или 2?
...
Рейтинг: 0 / 0
01.04.2012, 14:40
    #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
01.04.2012, 14:58
    #37733487
orawish
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
пятничная задачка (про) коня
Bfinkorawish,

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

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

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

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

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

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

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

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

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

я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.
не верю (c) :)
кстати - парой постов выше я говорил про миллион решений, влёгкую полученных алгоритмом, обыгравшем
отдельный (очень) частный случай. ну так я наврал (у того частного алгоритма) решений не менее чем 1e9
...
Рейтинг: 0 / 0
01.04.2012, 17:24
    #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
01.04.2012, 17:28
    #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
01.04.2012, 17:34
    #37733595
orawish
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
пятничная задачка (про) коня
andreymx,

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

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

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

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

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


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