powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня
118 сообщений из 118, показаны все 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
пятничная задачка (про) коня
    #37734840
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
orawish, по чуть-чуть нельзя( - это ж брутфорс. Первые 63 этапа могут быть логичные, а вот 64ий не сойдется.
А никто не считал, сколько в теории верных результатов? А то у мя уже час считается, чую надо будет ждать маленькую вечность с тупым перебором.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734888
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukku,

ваш алгоритм, похоже, скорее мёртв, чем жив.
не позднее 19 хода он фатально ошибается и весело продолжает скакать по первому возможному варианту до 60-го
на 60-м ходов не остается совсем и начинается вечный балет по перемалыванию заведомо неживого хвоста
(из минимум ~сорока одного уровня)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734894
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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  	;удачи!


Тут можно расширить постановку и искать обходы не только конём но и королём, ферзём
и произвольной фигурой которая ходит вовсе не по правилам шахмат.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734897
Фотография -2-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonи произвольной фигурой которая ходит вовсе не по правилам шахмат.и по площади занимает произвольные 8х8 клеток шахматной доски.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37734898
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Поэтому и назвал тупым перебором :) Кто дойдет до 64 только тот и будет верный. Ладно хватит работать сегодня, надо будет завтра подумать чтобы заведомо не верные отсекались.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735455
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishну так за чем же дело стало? вперёд! ;)Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д.
Если ~перебором - то решать задачу для половины доски как рекомендуют здесь , при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить.
Но слишком много рутины - это отталкивает от задачи.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735501
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshoporawishну так за чем же дело стало? вперёд! ;)Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д.
Если ~перебором - то решать задачу для половины доски как рекомендуют здесь , при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить.
Но слишком много рутины - это отталкивает от задачи.
насколько я понимаю, решение от ukku и есть инкарнация алгоритма Варнсдорфа, по сути - тот же перебор.
т.е. сам по себе, без дополнительных приседаний - абсолютно никаких шансов
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735506
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

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

Абсолютно нет.
Правило ВарнсдорфаПри обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них.
согласен. (посмотрел в код :) в части алгоритма выбора - принципиально разные подходы.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735760
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735773
wurdu
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)Через recursive subquery factoring можно, но там куча ограничений на запрос.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37735818
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)
вы же траекторию рисуете - в ней всё есть
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736011
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)
В классике алгоритмизации это состояние хранит стек рекурсии. Попытка развернуть это
в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736039
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПопытка развернуть это в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO.
Смысл извращения в самом извращение :) Надо было б написать по-человечески взяли бы плюсы или тому подобное.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736091
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736204
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.1-е апреля было позавчера.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736218
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshopmaytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.1-е апреля было позавчера.
Не важно. Жанр пятничных задачек мне интересен вне зависимости от праздников.
Просто не понятна была глубина извращённости решения которую хотел получить
автор.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736304
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshopmaytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу.
Если доказали то можно решить любую задачку.1-е апреля было позавчера.
offtop:

кстати, про первое апреля (тема же как раз от этого числа)
признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки.
:)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736338
ukku
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
orawishdbms_photoshopпропущено...
1-е апреля было позавчера.
offtop:
кстати, про первое апреля (тема же как раз от этого числа)
признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки.
:)
Была мысль стишок из вики распарсить )
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736446
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37736773
Фотография _bob
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд.
Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)

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

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.
недопонял я, про что вы.
если решение циклическое, то начальная позиция для него - любая.
(т.е. если замкнёте , то решать можно, начиная с какой хотите позиции)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737050
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishdbms_photoshoporawish,

Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут.
Если начальная позиция любая, то есс-но задача особого смысла не имеет.
недопонял я, про что вы.
если решение циклическое, то начальная позиция для него - любая.
(т.е. если замкнёте , то решать можно, начиная с какой хотите позиции)Начиная с произвольной - неинтересно.
В этом решении можно увидеть определенные закономерности и заставить двигаться коня согласно их:

То же самое касательно закономерностей здесь:

А вот если на входе может быть любое поле, а не a1 это уже интересней.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737063
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я и предлагал рассмотреть самый общий случай.
И поле - произвольной области. Не прямогуольное.
Или объединение множества прямогольников.
Или лабиринт.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737123
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ и предлагал рассмотреть самый общий случай.
И поле - произвольной области. Не прямогуольное.
Или объединение множества прямогольников.
Или лабиринт.
а кто против? во всяком случае - я не против.
рассматривайте
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737152
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop..
А вот если на входе может быть любое поле, а не a1 это уже интересней.
и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвост
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737494
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishdbms_photoshop..
А вот если на входе может быть любое поле, а не a1 это уже интересней.
и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность.
Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны.
В общем цель была как можно быстрее написать эту рутину.
Красным выделено ноу-хау решения.
Уже озвученный правило Варнсдорфа
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
declare
  type t is table of binary_integer index by binary_integer;
  type tt is table of t index by binary_integer;
  desk tt;
  ii   binary_integer := 1;
  jj   binary_integer := 1;
  ind  binary_integer := 1;
  v    varchar2(25);
  function cnt_unvisited(x in binary_integer, y in binary_integer)
    return binary_integer as
    result binary_integer := 0;
  begin
    for i in (select x + dx x, y + dy y
                from
                -- NoFormat Start
                      (select 2 dx, -1 dy from dual
                      union all select 2 dx, 1 dy from dual
                      union all select 1 dx, 2 dy from dual
                      union all select -1 dx, 2 dy from dual
                      union all select -2 dx, +1 dy from dual
                      union all select -2 dx, -1 dy from dual
                      union all select -1 dx, -2 dy from dual
                      union all select 1 dx, -2 dy from dual)
                      -- NoFormat End
               where x + dx >= 1
                 and x + dx <= 8
                 and y + dy >= 1
                 and y + dy <= 8) loop
      result := result + (1 - sign(desk(i.x) (i.y)));
    end loop;
    return result;
  end;
  procedure find_next(x in out binary_integer, y in out binary_integer) as
    tmp sys.odcivarchar2list := sys.odcivarchar2list();
  begin
    if ind = 64 then
      for i in 1 .. 8 loop
        for j in 1 .. 8 loop
          if desk(i) (j) = 0 then
            desk(i)(j) := 64;
          end if;
        end loop;
      end loop;
    else
      for i in (select x + dx x, y + dy y
                  from
                  -- NoFormat Start
                        (select 2 dx, -1 dy from dual
                        union all select 2 dx, 1 dy from dual
                        union all select 1 dx, 2 dy from dual
                        union all select -1 dx, 2 dy from dual
                        union all select -2 dx, +1 dy from dual
                        union all select -2 dx, -1 dy from dual
                        union all select -1 dx, -2 dy from dual
                        union all select 1 dx, -2 dy from dual)
                        -- NoFormat End
                 where x + dx >= 1
                   and x + dx <= 8
                   and y + dy >= 1
                   and y + dy <= 8) loop
        if desk(i.x) (i.y) = 0 then
          tmp.extend;
          tmp(tmp.count) := to_char(cnt_unvisited(i.x, i.y), 'fm00') ||
                            to_char(i.x, 'fm00') || to_char(i.y, 'fm00');
        end if;
      end loop;
      if tmp.count = 0 then
        raise_application_error(-20000, 'It''s a dead end!');
      end if;
      select t.x, t.y
        into find_next.x, find_next.y
        from (select substr(column_value, 3, 2) x,
                     substr(column_value, 5, 2) y
                from table(tmp)
               order by substr(column_value, 1, 2), dbms_random.value) t
       where rownum = 1;
    end if;
  end;
begin
  -- initializing
  for i in 1 .. 8 loop
    for j in 1 .. 8 loop
      desk(i)(j) := 0;
    end loop;
  end loop;
  -- finding solution
  begin
    for i in 1 .. 8 loop
      for j in 1 .. 8 loop
        desk(ii)(jj) := ind;
        find_next(ii, jj);
        ind := ind + 1;
      end loop;
    end loop;
  exception
    when others then
      if sqlcode = -20000 then
        null;
      else
        raise;
      end if;
  end;
  -- printing result
  dbms_output.put_line(lpad('-', 25, '-'));
  for i in 1 .. 8 loop
    v := '|';
    for j in 1 .. 8 loop
      v := v || to_char(desk(i) (j), 'fm00') || '|';
    end loop;
    dbms_output.put_line(v);
  end loop;
  dbms_output.put_line(lpad('-', 25, '-'));
end;

Если немного поклацать, то рано или поздно выпадет что-то в духе:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
-------------------------
|01|04|59|20|23|06|57|52|
|42|19|02|05|58|51|22|07|
|03|64|43|60|21|24|53|56|
|18|41|30|63|50|55|08|25|
|31|14|61|44|37|26|49|54|
|40|17|38|29|62|45|36|09|
|13|32|15|46|11|34|27|48|
|16|39|12|33|28|47|10|35|
-------------------------

Процесс поиска замкнутого я уже не автоматизировал, легче было поклацать.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37737578
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
попробовал 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.
41.
42.
43.
CREATE TABLE TABLES AS
WITH
T AS
(SELECT ROWNUM i FROM dual connect BY ROWNUM < 9)
SELECT t1.i r, t2.i c,
       (t1.i-1)*8+t2.i ID
  FROM T t1, T t2
;

CREATE TABLE s
AS
WITH
steps AS(
SELECT  1 r,  2 c FROM dual UNION ALL
SELECT  1 r, -2 c FROM dual UNION ALL
SELECT  2 r, -1 c FROM dual UNION ALL
SELECT  2 r,  1 c FROM dual UNION ALL
SELECT -1 r,  2 c FROM dual UNION ALL
SELECT -1 r, -2 c FROM dual UNION ALL
SELECT -2 r, -1 c FROM dual UNION ALL
SELECT -2 r,  1 c FROM dual
)
SELECT t_from.ID id_from,
       t_from.r r_from,
       t_from.c c_from,
       t_to.ID id_to,
       t_to.r  r_to,
       t_to.c  c_to
  FROM TABLES t_from,
       steps,
       TABLES t_to
 WHERE t_from.r + steps.r = t_to.r
   AND t_from.c + steps.c = t_to.c
 ORDER BY id_from, id_to;

CREATE TABLE ss
PCTFREE 0
CACHE
AS
SELECT s1.id_from, s1.id_to id_to1, s2.id_to id_to2
  FROM s s1,
       s s2
 WHERE s2.id_from = s1.id_to;




запрос

Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
WITH
T0  AS (SELECT 0 r, 11 ID, 1 LAST FROM dual),
t1 AS
(SELECT /*+ materialize */1 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T0,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T0)
   AND ss.id_to2 NOT IN (SELECT ID FROM T0)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T0
),

t2 AS
(SELECT /*+ materialize */2 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T1,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T1)
   AND ss.id_to2 NOT IN (SELECT ID FROM T1)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T1
),

t3 AS
(SELECT /*+ materialize */3 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T2,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T2)
   AND ss.id_to2 NOT IN (SELECT ID FROM T2)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T2
),

t4 AS
(SELECT /*+ materialize */4 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T3,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T3)
   AND ss.id_to2 NOT IN (SELECT ID FROM T3)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T3
),

t5 AS
(SELECT /*+ materialize */5 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T4,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T4)
   AND ss.id_to2 NOT IN (SELECT ID FROM T4)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T4
),

t6 AS
(SELECT /*+ materialize */6 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T5,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T5)
   AND ss.id_to2 NOT IN (SELECT ID FROM T5)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T5
),

t7 AS
(SELECT /*+ materialize */7 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T6,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T6)
   AND ss.id_to2 NOT IN (SELECT ID FROM T6)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T6
),

t8 AS
(SELECT /*+ materialize */8 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T7,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T7)
   AND ss.id_to2 NOT IN (SELECT ID FROM T7)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T7
),

t9 AS
(SELECT /*+ materialize */9 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T8,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T8)
   AND ss.id_to2 NOT IN (SELECT ID FROM T8)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T8
),

t10 AS
(SELECT /*+ materialize */10 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T9,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T9)
   AND ss.id_to2 NOT IN (SELECT ID FROM T9)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T9
),

t11 AS
(SELECT /*+ materialize */11 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T10,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T10)
   AND ss.id_to2 NOT IN (SELECT ID FROM T10)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T10
),

t12 AS
(SELECT /*+ materialize */12 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T11,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T11)
   AND ss.id_to2 NOT IN (SELECT ID FROM T11)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T11
),

t13 AS
(SELECT /*+ materialize */13 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T12,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T12)
   AND ss.id_to2 NOT IN (SELECT ID FROM T12)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T12
),

t14 AS
(SELECT /*+ materialize */14 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T13,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T13)
   AND ss.id_to2 NOT IN (SELECT ID FROM T13)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T13
),

t15 AS
(SELECT /*+ materialize */15 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T14,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T14)
   AND ss.id_to2 NOT IN (SELECT ID FROM T14)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T14
),

t16 AS
(SELECT /*+ materialize */16 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T15,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T15)
   AND ss.id_to2 NOT IN (SELECT ID FROM T15)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T15
),

t17 AS
(SELECT /*+ materialize */17 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T16,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T16)
   AND ss.id_to2 NOT IN (SELECT ID FROM T16)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T16
),

t18 AS
(SELECT /*+ materialize */18 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T17,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T17)
   AND ss.id_to2 NOT IN (SELECT ID FROM T17)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T17
),

t19 AS
(SELECT /*+ materialize */19 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T18,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T18)
   AND ss.id_to2 NOT IN (SELECT ID FROM T18)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T18
),

t20 AS
(SELECT /*+ materialize */20 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T19,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T19)
   AND ss.id_to2 NOT IN (SELECT ID FROM T19)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T19
),

t21 AS
(SELECT /*+ materialize */21 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T20,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T20)
   AND ss.id_to2 NOT IN (SELECT ID FROM T20)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T20
),

t22 AS
(SELECT /*+ materialize */22 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T21,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T21)
   AND ss.id_to2 NOT IN (SELECT ID FROM T21)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T21
),

t23 AS
(SELECT /*+ materialize */23 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T22,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T22)
   AND ss.id_to2 NOT IN (SELECT ID FROM T22)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T22
),

t24 AS
(SELECT /*+ materialize */24 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T23,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T23)
   AND ss.id_to2 NOT IN (SELECT ID FROM T23)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T23
),

t25 AS
(SELECT /*+ materialize */25 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T24,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T24)
   AND ss.id_to2 NOT IN (SELECT ID FROM T24)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T24
),

t26 AS
(SELECT /*+ materialize */26 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T25,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T25)
   AND ss.id_to2 NOT IN (SELECT ID FROM T25)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T25
),

t27 AS
(SELECT /*+ materialize */27 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T26,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T26)
   AND ss.id_to2 NOT IN (SELECT ID FROM T26)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T26
),

t28 AS
(SELECT /*+ materialize */28 r, MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID, 1 LAST
  FROM T27,
       ss
 WHERE ss.id_from = ID
   AND LAST = 1
   AND ss.id_to1 NOT IN (SELECT ID FROM T27)
   AND ss.id_to2 NOT IN (SELECT ID FROM T27)
 GROUP BY ss.id_to1
UNION-- ALL
SELECT r, ID, 0 LAST FROM T27
)


SELECT *
  FROM T28 



на 28 ходу план запроса строится 5 минут :))


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

и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность.
Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны.
В общем цель была как можно быстрее написать эту рутину.
Красным выделено ноу-хау решения.
..
Процесс поиска замкнутого я уже не автоматизировал, легче было поклацать.
а я считаю, что зря вы скромничаете - в том смысле, что очень хорошее решение нарисовали.
для задачи 1) оно просто вне конкуренции
процесс поклацать до циклического (т.е. решение задачи 2 ) тут
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
 
SQL> set timing on serveroutput on
SQL> declare
  2    type t is table of binary_integer index by binary_integer;
  3    type tt is table of t index by binary_integer;
  4    desk tt;
  5    ii   binary_integer := 1;
  6    jj   binary_integer := 1;
  7    ind  binary_integer := 1;
  8    rpt  binary_integer := 1;
  9    v    varchar2(25);
 10    function cnt_unvisited(x in binary_integer, y in binary_integer)
 11  	 return binary_integer as
 12  	 result binary_integer := 0;
 13    begin
 14  	 for i in (select x + dx x, y + dy y
 15  		     from
 16  		     -- NoFormat Start
 17  			   (select 2 dx, -1 dy from dual
 18  			   union all select 2 dx, 1 dy from dual
 19  			   union all select 1 dx, 2 dy from dual
 20  			   union all select -1 dx, 2 dy from dual
 21  			   union all select -2 dx, +1 dy from dual
 22  			   union all select -2 dx, -1 dy from dual
 23  			   union all select -1 dx, -2 dy from dual
 24  			   union all select 1 dx, -2 dy from dual)
 25  			   -- NoFormat End
 26  		    where x + dx >= 1
 27  		      and x + dx <= 8
 28  		      and y + dy >= 1
 29  		      and y + dy <= 8) loop
 30  	   result := result + (1 - sign(desk(i.x) (i.y)));
 31  	 end loop;
 32  	 return result;
 33    end;
 34    procedure find_next(x in out binary_integer, y in out binary_integer) as
 35  	 tmp sys.odcivarchar2list := sys.odcivarchar2list();
 36    begin
 37  	 if ind = 64 then
 38  	   for i in 1 .. 8 loop
 39  	     for j in 1 .. 8 loop
 40  	       if desk(i) (j) = 0 then
 41  		 desk(i)(j) := 64;
 42  	       end if;
 43  	     end loop;
 44  	   end loop;
 45  	 else
 46  	   for i in (select x + dx x, y + dy y
 47  		       from
 48  		       -- NoFormat Start
 49  			     (select 2 dx, -1 dy from dual
 50  			     union all select 2 dx, 1 dy from dual
 51  			     union all select 1 dx, 2 dy from dual
 52  			     union all select -1 dx, 2 dy from dual
 53  			     union all select -2 dx, +1 dy from dual
 54  			     union all select -2 dx, -1 dy from dual
 55  			     union all select -1 dx, -2 dy from dual
 56  			     union all select 1 dx, -2 dy from dual)
 57  			     -- NoFormat End
 58  		      where x + dx >= 1
 59  			and x + dx <= 8
 60  			and y + dy >= 1
 61  			and y + dy <= 8) loop
 62  	     if desk(i.x) (i.y) = 0 then
 63  	       tmp.extend;
 64  	       tmp(tmp.count) := to_char(cnt_unvisited(i.x, i.y), 'fm00') ||
 65  				 to_char(i.x, 'fm00') || to_char(i.y, 'fm00');
 66  	     end if;
 67  	   end loop;
 68  	   if tmp.count = 0 then
 69  	     raise_application_error(-20000, 'It''s a dead end!');
 70  	   end if;
 71  	   select t.x, t.y
 72  	     into find_next.x, find_next.y
 73  	     from (select substr(column_value, 3, 2) x,
 74  			  substr(column_value, 5, 2) y
 75  		     from table(tmp)
 76  		    order by substr(column_value, 1, 2), dbms_random.value) t
 77  	    where rownum = 1;
 78  	 end if;
 79    end;
 80  begin
 81    loop
 82  	 ii    := 1;
 83  	 jj    := 1;
 84  	 ind   := 1;
 85    -- initializing
 86  	 for i in 1 .. 8 loop
 87  	   for j in 1 .. 8 loop
 88  	     desk(i)(j) := 0;
 89  	   end loop;
 90  	 end loop;
 91  	 -- finding solution
 92  	 begin
 93  	   for i in 1 .. 8 loop
 94  	     for j in 1 .. 8 loop
 95  	       desk(ii)(jj) := ind;
 96  	       find_next(ii, jj);
 97  	       ind := ind + 1;
 98  	     end loop;
 99  	   end loop;
100  	 exception
101  	   when others then
102  	     if sqlcode = -20000 then
103  	       null;
104  	     else
105  	       raise;
106  	     end if;
107  	 end;
108  	 exit when 64 in (desk(2)(3),desk(3)(2)) or rpt>10000;
109  	 rpt := rpt+1;
110    end loop;
111    -- printing result
112    dbms_output.put_line('rpt='||rpt);
113    dbms_output.put_line(lpad('-', 25, '-'));
114    for i in 1 .. 8 loop
115  	 v := '|';
116  	 for j in 1 .. 8 loop
117  	   v := v || to_char(desk(i) (j), 'fm00') || '|';
118  	 end loop;
119  	 dbms_output.put_line(v);
120    end loop;
121    dbms_output.put_line(lpad('-', 25, '-'));
122  end;
123  /
rpt=119                                                                         
-------------------------                                                       
|01|34|03|18|63|32|13|16|                                                       
|04|19|64|33|14|17|58|31|                                                       
|41|02|35|50|57|62|15|12|                                                       
|20|05|40|61|36|51|30|59|                                                       
|39|42|37|56|49|60|11|26|                                                       
|06|21|54|45|52|27|48|29|                                                       
|43|38|23|08|55|46|25|10|                                                       
|22|07|44|53|24|09|28|47|                                                       
-------------------------                                                       

Процедура PL/SQL успешно завершена.

Затрач.время: 00:00:02.17
 


из чего видно, что и задача 2 таким способом решается (по крайней мере) на порядок быстрее,
чем моим алгоритмом (сейчас опубликую).
но остаются еще: задача 3) - 1001 решение найти
и задача 4) таки попробовать оценить их (решений) количество
:)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738396
Vint
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop,
класс)
orawish
задача 4 решается у dbms_photoshop примерно, если посчитать произведение всех order by substr(column_value, 1, 2) на каждом шаге. конечно не все из них ведут к правильному решению но ошибку будет на 1-2 порядка)
а вот третья задачка интересная, но думаю тоже можно оттолкнутся от той же строки сортировки что и в предыдушем случае только не сортировать по , dbms_random.value а ввести еще какой нибудь дополнительный массив где отмечать пройденные \ не пройденные маршруты. то есть достигнув решения. возвращаемся на n шагов назад. где substr(column_value, 1, 2)>1 и идем в другую сторону.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738416
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vintdbms_photoshop,
класс)
orawish
задача 4 решается у dbms_photoshop примерно, если посчитать произведение всех order by substr(column_value, 1, 2) на каждом шаге. конечно не все из них ведут к правильному решению но ошибку будет на 1-2 порядка)
а вот третья задачка интересная, но думаю тоже можно оттолкнутся от той же строки сортировки что и в предыдушем случае только не сортировать по , dbms_random.value а ввести еще какой нибудь дополнительный массив где отмечать пройденные \ не пройденные маршруты. то есть достигнув решения. возвращаемся на n шагов назад. где substr(column_value, 1, 2)>1 и идем в другую сторону.
рассуждения хорошо бы подкреплять вычислениями
(многократно ужЕ проверено, что умозрительные оценки в данной задаче совершенно не оправдываются :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738553
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
мой способ - тут
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
spool o1
create or replace package pk as
  g_level binary_integer;
  type tp1 is table of boolean index by varchar2(66);
  t1 tp1;

  function f (
     p_level number
    ,p_x     number
    ,p_y     number
    ,p_x2    number
    ,p_y2    number
    ,p_s     varchar2
  ) return number;

end;
/
create or replace package body pk as

  function f (
     p_level number
    ,p_x     number
    ,p_y     number
    ,p_x2    number
    ,p_y2    number
    ,p_s     varchar2
  ) return number is
    a_s varchar2(66) := p_x||p_y||p_s;
    r   number;
  begin
    if p_level <> nvl(g_level,0) or p_level=33 then
      t1.delete;
      g_level := p_level;
    end if;

    if t1.exists(a_s) then
      return 0;
    end if;
    t1(a_s) := null;

    if p_level = 64
      and not (p_x2||p_y2) in ((p_x +1) || (p_y +2)
                              ,(p_x +1) || (p_y -2)
                              ,(p_x +2) || (p_y +1)
                              ,(p_x +2) || (p_y -1)
                              ,(p_x -1) || (p_y +2)
                              ,(p_x -1) || (p_y -2)
                              ,(p_x -2) || (p_y +1)
                              ,(p_x -2) || (p_y -1))
    then
      return 0;
    end if;

    for x in 1..8 loop
      for y in 1..8 loop
        if substr(p_s,(x-1)*8+y,1) = '0' then
          r := case when x+1 between 1 and 8 and  y+2  between 1 and 8 then
             substr(p_s,(x+1 -1)*8+               y+2 ,1) else 1 end
              +case when x+1 between 1 and 8 and  y-2  between 1 and 8 then
             substr(p_s,(x+1 -1)*8+               y-2 ,1) else 1 end
              +case when x+2 between 1 and 8 and  y+1  between 1 and 8 then
             substr(p_s,(x+2 -1)*8+               y+1 ,1) else 1 end
              +case when x+2 between 1 and 8 and  y-1  between 1 and 8 then
             substr(p_s,(x+2 -1)*8+               y-1 ,1) else 1 end
              +case when x-1 between 1 and 8 and  y+2  between 1 and 8 then
             substr(p_s,(x-1 -1)*8+               y+2 ,1) else 1 end
              +case when x-1 between 1 and 8 and  y-2  between 1 and 8 then
             substr(p_s,(x-1 -1)*8+               y-2 ,1) else 1 end
              +case when x-2 between 1 and 8 and  y+1  between 1 and 8 then
             substr(p_s,(x-2 -1)*8+               y+1 ,1) else 1 end
              +case when x-2 between 1 and 8 and  y-1  between 1 and 8 then
             substr(p_s,(x-2 -1)*8+               y-1 ,1) else 1 end
              +case when (x||y) in ((p_x2+1) || (p_y2+2)
                                   ,(p_x2+1) || (p_y2-2)
                                   ,(p_x2+2) || (p_y2+1)
                                   ,(p_x2+2) || (p_y2-1)
                                   ,(p_x2-1) || (p_y2+2)
                                   ,(p_x2-1) || (p_y2-2)
                                   ,(p_x2-2) || (p_y2+1)
                                   ,(p_x2-2) || (p_y2-1)) then -1 else 0 end
              +case when (x||y) in ((p_x +1) || (p_y +2)
                                   ,(p_x +1) || (p_y -2)
                                   ,(p_x +2) || (p_y +1)
                                   ,(p_x +2) || (p_y -1)
                                   ,(p_x -1) || (p_y +2)
                                   ,(p_x -1) || (p_y -2)
                                   ,(p_x -2) || (p_y +1)
                                   ,(p_x -2) || (p_y -1)) then -1 else 0 end
          ;
          if r >= 7 then
            return 0;
          end if;
        end if;
      end loop;
    end loop;

    return 1;
  end;
end;
/
set timing on linesize 120
with tt as (select  1 dx , 2 dy from dual
      union select  1    ,-2    from dual
      union select  2    , 1    from dual
      union select  2    ,-1    from dual
      union select -1    , 2    from dual
      union select -1    ,-2    from dual
      union select -2    , 1    from dual
      union select -2    ,-1    from dual
) ,t(i,x1,y1,x2,y2,s,r) as (
            select 1 as i
                  ,3 as x1
                  ,5 as y1
                  ,3 as x2
                  ,5 as y2
                 -- 12345678
                  ,'00000000' -- a
                 ||'00000000' -- b
                 ||'00001000' -- c
                 ||'00000000' -- d
                 ||'00000000' -- e
                 ||'00000000' -- f
                 ||'00000000' -- g
                 ||'00000000' -- h
                 as s
                  ,cast(' c5' as varchar2(192)) as r
              from dual
  union all select i+1
                  ,x1+dx
                  ,y1+dy
                  ,x2
                  ,y2
                  ,substr(s,1,(x1+dx-1)*8+y1+dy-1)||1||substr(s,(x1+dx-1)*8+y1+dy+1)
                  ,r||' '||chr(ascii('a')-1+x1+dx)||(y1+dy)
              from tt ,t
             where substr(s,  (x1+dx-1)*8+y1+dy,1) = '0'
               and substr(s,1,(x1+dx-1)*8+y1+dy-1)||1||substr(s,(x1+dx-1)*8+y1+dy+1) not like '%11%'
               and x1+dx between 1 and 4
               and y1+dy between 5 and 8
               and ( i < 7 or (x1+dx = x2+1 and y1+dy = y2) )
), t2(i,x1,y1,x2,y2,s,r) as (
            select min(i)  i
                  ,min(x1) x1
                  ,min(y1) y1
                  ,min(x2) x2
                  ,min(y2) y2
                  ,min(s)  s
                  ,min(r)  r
              from t
             where i = 8
  union all select i+2  as i
                  ,case when abs(dx)=2 or x1+dx = x2              then x1+dx end  as x1
                  ,y1+dy                                                          as y1
                  ,case when abs(dx)=2 then x2+dx when x1+dx = x2 then x2-dx end  as x2
                  ,y2+dy                                                          as y2
                  ,regexp_replace(
                   regexp_replace( s
                      ,'.',1,1,(case when abs(dx)=2 then x2+dx when x1+dx = x2 then x2-dx end-1)*8+y2+dy)
                      ,'.',1,1,(case when abs(dx)=2 or x1+dx = x2              then x1+dx end-1)*8+y1+dy)
                  ,' '||chr(ascii('a')-1
                               +case when abs(dx)=2 then x2+dx when x1+dx = x2 then x2-dx end)||(y2+dy)||r||
                   ' '||chr(ascii('a')-1
                               +case when abs(dx)=2 or x1+dx = x2              then x1+dx end)||(y1+dy)
              from tt ,t2
             where substr(s,(case when abs(dx)=2 then x2+dx when x1+dx = x2 then x2-dx end -1)*8+y2+dy,1) = '0'
               and substr(s,(case when abs(dx)=2 or x1+dx = x2              then x1+dx end -1)*8+y1+dy,1) = '0'
               and case when abs(dx)=2 then x2+dx when x1+dx = x2 then x2-dx end  between 1 and 8
               and case when abs(dx)=2 or x1+dx = x2              then x1+dx end  between 1 and 8
               and y1+dy  between 1 and 8
               and y2+dy  between 1 and 8
               and ( i < 32 )
), t3(i,x1,y1,x2,y2,s,r) as (
            select min(i)  i
                  ,min(x1) x1
                  ,min(y1) y1
                  ,min(x2) x2
                  ,min(y2) y2
                  ,min(s) s
                  ,min(r) r
              from t2
             where i = 32 and r like ' f4 %e4'
  union all select i+1
                  ,x1+dx
                  ,y1+dy
                  ,x2
                  ,y2
                  ,substr(s,1,(x1+dx-1)*8+y1+dy-1)||1||substr(s,(x1+dx-1)*8+y1+dy+1)
                  ,r||' '||chr(ascii('a')-1+x1+dx)||(y1+dy)
              from tt ,t3
             where substr(s,(x1+dx-1)*8+y1+dy,1) = '0'
               and x1+dx  between 1 and 8
               and y1+dy  between 1 and 8
               and 1=pk.f(i+1
                         ,x1+dx
                         ,y1+dy
                         ,x2
                         ,y2
                         ,substr(s,1,(x1+dx-1)*8+y1+dy-1)||1||substr(s,(x1+dx-1)*8+y1+dy+1))
               and i<64
          ) select r
              from t3
             where i=64;


т.е. таки брутфорс, но не задачи целиком, а задачи, разделённой на три фазы (по брутфорсу на фазу)
на самом деле - на картинках, что я рисовал выше, сказано буквально всё
1) фаза - 8 ходов, на протяжении которых конь не должен выходить из своего квадранта доски (4x4), и не должен допускать,
чтобы вся траектория имела два соседних поля по вертикали. а также требуется, чтобы на 8 ходу конь пришел к полю, соседнему
(по горизонтали) с полем старта.
2) фаза - ходы с 9 по 32. здесь в движение приходит и голова и хвост траектории одновременно. то есть скачут как бы два,
коня, но одной дивизией - т.е. как бы строй держат ) на каждом ходу. вариантов не много - перебор их проходит быстро.
3) свободной остается половина доски. вторая половина доски здОрово ограничивает количество вариантов.
можно, вроде бы и попробовать перебрать их все. однако - увы и ах.. вариантов всё равно слишком, слишком много.
тут приходится подключать pl/sql - первым делом , для того, чтобы отсекать ходы после которых гарантированно решение не
может быть получено. и вторым делом - для исключения дубликатов позиции (разумеется, это = пройденные поля+позиция коня ).
Все.
теперь про результаты. если на каждом ходу исключать (из дальнейшего рассмотрения ) дубликаты позиций, то,
глядя на позицию после 32 хода, очевидно что решений уникальных не может быть больше двух - ведь подходов к финальной точке лишь два. что, собственно и имеем в результате нашего запроса.
Если дубликаты позиций не исключать (комментируем в пакете)
Код: plsql
1.
2.
3.
--     if t1.exists(a_s) then
--       return 0;
--     end if;


, то решение всё равно будет получено (за в 5-7 раз бОльшее время = 135 секунд у меня получилось ) и решений
этих будет числом 21390.
пора сделать первый вывод. поскольку на 32 ходу позиция на доске симметричная, то для первых 32 ходов
(если мы не будем заставлять коня держать строй ) имеем столько же (ровно 21390) вариантов траектории.
умножаем.. :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738560
Vint
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,
надеюсь за плагиат не побьют))
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
DECLARE
  TYPE t IS TABLE OF BINARY_INTEGER INDEX BY BINARY_INTEGER;
  TYPE tt IS TABLE OF t INDEX BY BINARY_INTEGER;
  desk       tt;
  ii         BINARY_INTEGER := 1;
  jj         BINARY_INTEGER := 1;
  ind        BINARY_INTEGER := 1;
  v          VARCHAR2(25);
  all_cnt    NUMBER := 1;
  all_vektor BINARY_INTEGER := 0;
  FUNCTION cnt_unvisited(x IN BINARY_INTEGER, y IN BINARY_INTEGER) RETURN BINARY_INTEGER AS
    RESULT BINARY_INTEGER := 0;
  BEGIN
    FOR i IN (SELECT x + dx x, y + dy y
                FROM
                -- NoFormat Start
                      (select 2 dx, -1 dy from dual
                      union all select 2 dx, 1 dy from dual
                      union all select 1 dx, 2 dy from dual
                      union all select -1 dx, 2 dy from dual
                      union all select -2 dx, +1 dy from dual
                      union all select -2 dx, -1 dy from dual
                      union all select -1 dx, -2 dy from dual
                      union all select 1 dx, -2 dy from dual)
                      -- NoFormat End
               WHERE x + dx >= 1
                 AND x + dx <= 8
                 AND y + dy >= 1
                 AND y + dy <= 8) LOOP
      RESULT := RESULT + (1 - sign(desk(i.x) (i.y)));
    END LOOP;
    RETURN RESULT;
  END;
  PROCEDURE find_next(x IN OUT BINARY_INTEGER, y IN OUT BINARY_INTEGER) AS
    tmp     sys.odcivarchar2list := sys.odcivarchar2list();
    tmp_cnt BINARY_INTEGER;
  BEGIN
    IF ind = 64 THEN
      FOR i IN 1 .. 8 LOOP
        FOR j IN 1 .. 8 LOOP
          IF desk(i) (j) = 0 THEN
            desk(i)(j) := 64;
          END IF;
        END LOOP;
      END LOOP;
    ELSE
      FOR i IN (SELECT x + dx x, y + dy y
                  FROM
                  -- NoFormat Start
                        (select 2 dx, -1 dy from dual
                        union all select 2 dx, 1 dy from dual
                        union all select 1 dx, 2 dy from dual
                        union all select -1 dx, 2 dy from dual
                        union all select -2 dx, +1 dy from dual
                        union all select -2 dx, -1 dy from dual
                        union all select -1 dx, -2 dy from dual
                        union all select 1 dx, -2 dy from dual)
                        -- NoFormat End
                 WHERE x + dx >= 1
                   AND x + dx <= 8
                   AND y + dy >= 1
                   AND y + dy <= 8) LOOP
        IF desk(i.x) (i.y) = 0 THEN
          tmp.extend;
          tmp(tmp.count) := to_char(cnt_unvisited(i.x, i.y), 'fm00') || to_char(i.x, 'fm00') || to_char(i.y, 'fm00');
        END IF;
      END LOOP;
      IF tmp.count = 0 THEN
        raise_application_error(-20000, 'It''s a dead end!');
      END IF;
      SELECT t.x, t.y, t.cnt
        INTO find_next.x, find_next.y, tmp_cnt
        FROM (SELECT substr(column_value, 3, 2) x, substr(column_value, 5, 2) y, COUNT(1) over(PARTITION BY substr(column_value, 1, 2)) cnt
                FROM TABLE(tmp)
               ORDER BY substr(column_value, 1, 2), dbms_random.value) t
       WHERE rownum = 1;
      all_vektor := tmp_cnt + all_vektor;
      all_cnt    := tmp_cnt * all_cnt;
    END IF;
  END;
BEGIN
  -- initializing
  FOR i IN 1 .. 8 LOOP
    FOR j IN 1 .. 8 LOOP
      desk(i)(j) := 0;
    END LOOP;
  END LOOP;
  -- finding solution
  BEGIN
    FOR i IN 1 .. 8 LOOP
      FOR j IN 1 .. 8 LOOP
        desk(ii)(jj) := ind;
        find_next(ii, jj);
        ind := ind + 1;
      END LOOP;
    END LOOP;
  EXCEPTION
    WHEN OTHERS THEN
      IF SQLCODE = -20000 THEN
        NULL;
      ELSE
        RAISE;
      END IF;
  END;
  -- printing result
  dbms_output.put_line(lpad('-', 25, '-'));
  FOR i IN 1 .. 8 LOOP
    v := '|';
    FOR j IN 1 .. 8 LOOP
      v := v || to_char(desk(i) (j), 'fm00') || '|';
    END LOOP;
    dbms_output.put_line(v);
  END LOOP;
  dbms_output.put_line(lpad('-', 25, '-'));
  dbms_output.put_line('Ветвлений:' || all_vektor);
  dbms_output.put_line('Если бы все ветвления были похожи:' || all_cnt);
END;


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

это попытка таки понакликать (тупым упорством) 1001 различное решение задачи 2)
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
SQL> set timing on serveroutput on
SQL> declare
  2    type t is table of binary_integer index by binary_integer;
  3    type tt is table of t index by binary_integer;
  4    desk tt;
  5    ii   binary_integer := 1;
  6    jj   binary_integer := 1;
  7    ind  binary_integer := 1;
  8    rpt  binary_integer := 1;
  9    type t_solv is table of binary_integer index by varchar2(128);
 10    solv t_solv;
 11    v_solv  varchar2(128);
 12    dup_solv  binary_integer := 0;
 13    v    varchar2(25);
 14    function cnt_unvisited(x in binary_integer, y in binary_integer)
 15  	 return binary_integer as
 16  	 result binary_integer := 0;
 17    begin
 18  	 for i in (select x + dx x, y + dy y
 19  		     from
 20  		     -- NoFormat Start
 21  			   (select 2 dx, -1 dy from dual
 22  			   union all select 2 dx, 1 dy from dual
 23  			   union all select 1 dx, 2 dy from dual
 24  			   union all select -1 dx, 2 dy from dual
 25  			   union all select -2 dx, +1 dy from dual
 26  			   union all select -2 dx, -1 dy from dual
 27  			   union all select -1 dx, -2 dy from dual
 28  			   union all select 1 dx, -2 dy from dual)
 29  			   -- NoFormat End
 30  		    where x + dx >= 1
 31  		      and x + dx <= 8
 32  		      and y + dy >= 1
 33  		      and y + dy <= 8) loop
 34  	   result := result + (1 - sign(desk(i.x) (i.y)));
 35  	 end loop;
 36  	 return result;
 37    end;
 38    procedure find_next(x in out binary_integer, y in out binary_integer) as
 39  	 tmp sys.odcivarchar2list := sys.odcivarchar2list();
 40    begin
 41  	 if ind = 64 then
 42  	   for i in 1 .. 8 loop
 43  	     for j in 1 .. 8 loop
 44  	       if desk(i) (j) = 0 then
 45  		 desk(i)(j) := 64;
 46  	       end if;
 47  	     end loop;
 48  	   end loop;
 49  	 else
 50  	   for i in (select x + dx x, y + dy y
 51  		       from
 52  		       -- NoFormat Start
 53  			     (select 2 dx, -1 dy from dual
 54  			     union all select 2 dx, 1 dy from dual
 55  			     union all select 1 dx, 2 dy from dual
 56  			     union all select -1 dx, 2 dy from dual
 57  			     union all select -2 dx, +1 dy from dual
 58  			     union all select -2 dx, -1 dy from dual
 59  			     union all select -1 dx, -2 dy from dual
 60  			     union all select 1 dx, -2 dy from dual)
 61  			     -- NoFormat End
 62  		      where x + dx >= 1
 63  			and x + dx <= 8
 64  			and y + dy >= 1
 65  			and y + dy <= 8) loop
 66  	     if desk(i.x) (i.y) = 0 then
 67  	       tmp.extend;
 68  	       tmp(tmp.count) := to_char(cnt_unvisited(i.x, i.y), 'fm00') ||
 69  				 to_char(i.x, 'fm00') || to_char(i.y, 'fm00');
 70  	     end if;
 71  	   end loop;
 72  	   if tmp.count = 0 then
 73  	     raise_application_error(-20000, 'It''s a dead end!');
 74  	   end if;
 75  	   select t.x, t.y
 76  	     into find_next.x, find_next.y
 77  	     from (select substr(column_value, 3, 2) x,
 78  			  substr(column_value, 5, 2) y
 79  		     from table(tmp)
 80  		    order by substr(column_value, 1, 2), dbms_random.value) t
 81  	    where rownum = 1;
 82  	 end if;
 83    end;
 84  begin
 85    loop
 86  	 ii    := 1;
 87  	 jj    := 1;
 88  	 ind   := 1;
 89    -- initializing
 90  	 for i in 1 .. 8 loop
 91  	   for j in 1 .. 8 loop
 92  	     desk(i)(j) := 0;
 93  	   end loop;
 94  	 end loop;
 95  	 -- finding solution
 96  	 begin
 97  	   for i in 1 .. 8 loop
 98  	     for j in 1 .. 8 loop
 99  	       desk(ii)(jj) := ind;
100  	       find_next(ii, jj);
101  	       ind := ind + 1;
102  	     end loop;
103  	   end loop;
104  	 exception
105  	   when others then
106  	     if sqlcode = -20000 then
107  	       null;
108  	     else
109  	       raise;
110  	     end if;
111  	 end;
112  	 if 64 in (desk(2)(3),desk(3)(2)) then
113  	   v_solv := null;
114  	   for i in 1 .. 8 loop
115  	     for j in 1 .. 8 loop
116  	       v_solv := v_solv || to_char(desk(i) (j), 'fm00');
117  	     end loop;
118  	   end loop;
119  	   if solv.exists(v_solv) then
120  	     dup_solv := dup_solv+1;
121  	   end if;
122  	   solv(v_solv):=null;
123  	   exit when solv.count>1000;
124  	 end if;
125  	 rpt := rpt+1;
126    end loop;
127    -- printing result
128    dbms_output.put_line('rpt='||rpt||' dup_solv='||dup_solv);
129  end; -- rpt=5377 dup_solv=10
130  /


результат
Код: plsql
1.
2.
3.
4.
5.
rpt=146611 dup_solv=1870                                                        

Процедура PL/SQL успешно завершена.

Затрач.время: 00:48:49.15


то есть удалось это за 48 минут, в результате 146611 повторений вашей процедуры
(т.е. столько решений задачи 1 было достигнуто), чтобы получить 1001+1870 решений задачи 2, из которых 1001 уникальны
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738700
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vint,

однако, не верю. :)
по той простой причине, что мои прикидки дают совсем-совсем другой по порядку величины диапазон значений, где может быть результат.

вот смотрИте (вспомним комбинаторику)
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
select 16*
       power(
        (32*31*30*29*28*27*26*25*24*23*22*21*20*19*18*17)
       /(16*15*14*13*12*11*10* 9* 8* 7* 6* 5* 4* 3* 2* 1)
       ,2)
from dual;

5780762163880833600


это количество вариантов позиции, которая могла бы возникнуть на 32 ходу, в случае если бы конь умел летать , но
на каждом ходу таки менял цвет поля приземления. реальных позиций, разумеется меньше. но намного ли?
на порядок? на два? на три? да хотя бы и так - тут этих порядков 18. ну а количество вариантов траектории для достижения
каждой позиции - см. выше результат брутфорса. так что, навскидку, я сказал бы - 1е20..1e25

дополнительные вычисления, разумеется, помогут это уточнить ( / или опровергнуть :)
на досуге покручу
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738735
Vint
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,
в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться)
итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше))
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738779
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vintorawish,
в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться)
итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше))
как быть с тем, что
Код: plsql
1.
2.
select 21390*21390 from dual; 
> 450 000 000


? и это только варианты, которые обязаны на 32 ходу соответствовать одной позиции, а их, (позиций) 10 в степени до-фи-га
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738842
Vint
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738897
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vintorawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.
ну, поскольку я (в основном) долбил задачу от середины, то уверенно могу сказать - и после 32 хода количество вариантов
на каждом последующем ходу продолжает будь-здоров как расти (настолько, что перебор без дополнительных мер не имеет шансов).
и еще - можете посмотреть на каком (начиная от первого) ходу накрываются тазом брутфорсы и сколько (+ какой прирост на уровень) вариантов уникальных позиций имеют они тогда.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738910
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vintorawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.
кстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738918
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishпроцесс поклацать до циклического (т.е. решение задачи 2 ) тутПросто у меня при тестировании с третьей попытки получился замкнутый маршрут и я решил не париться. :)
orawish задача 3) - 1001 решение найтиЕсли начинать не из угла доски, то, думаю, время нахождения 1001 решения сократится в разы.
orawish задача 4) таки попробовать оценить их (решений) количествоВот это самое интересное.
Как написано по ссылке, которую я уже приводил: http://golovolomka.hobby.ru/books/gik/02.shtml Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня по доске, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C63168 (число сочетаний из 168 элементов по 63, оно состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом провести, практически неосуществимы.Интересно что за метод, вычисления для которого практически не осуществимы, при этом для половины доски уже найдено точное число решений.
Как бы там ни было, делать свои брутфорсы без изучения работ по тематике из сабжа бессмысленно.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738933
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 .
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738936
Vint
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop,
хм.. а мне казалось что всё проще))).....
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738945
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Созрел быстрый и универсальный алгоритм для обхода произвольных областей клеток.

1) Прозвольная область заполняется заполняющей кривой Гильберта или кривой Пеано
с шириной в 4 клетки. Границы кривой обозначаются как стенки которые конь не пересекает.

2) Конь обходит область придерживаясь этого коридора.

Поскольку движение коня в коридоре - быстро и детерминировано то в целом
конь очень быстро обходит произвольные и сложные области.

Кривую Гилберта я взял просто без оснований. Интуитивно. Хотя по ней можно
спорить. Возможно есть варианты обхода "змейкой", "спиралью", Z-порядком e.t.c.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37738988
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshoporawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 .
отлично! ответ известен. осталось получить его от оракла :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739015
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Уже потихоньку начинает напрягать желание местных обитателей пытаться изобретать велосипед.
По ссылке, что я приводил есть абзац: "При каких значениях m и n существует маршрут коня по всем полям доски m*n (с посещением каждого из них по одному разу)?"
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739019
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishdbms_photoshopпропущено...
Три минуты гугления привели к: 33,439,123,484,294 .
отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739021
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop, чел, я говорю не о прямоугольных досках.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739027
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshoporawishпропущено...

отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы.
ну а я попробую усовершенствовать силовой вариант. ~2e9 решений полузадачи это не так уж и много.
опять же - одно дело посчитать сколько их, а другое - отрисовать их всех
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739029
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Ок, надеюсь не надо доказывать, что, к примеру, для доски с шириной 2 и любой длиной задача неразрешима?
Если подумать далее, то можно прийти к заключению, что область можно разбить на некоторые разрешимые подобласти.
Обход делается опять же по правилу Варнсдорфа.
К чему здесь блистать своими анти познаниями по кривым?
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739038
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739053
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop, я же и говорю о ширине коридора.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37739271
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshoporawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда.
это бред (). очередное доказательство, что нефиг трендеть на основе домыслов, а надо запросы писать.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741148
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
обычным SQL за 0.2 сек на Оракл 9.2? это реально :-)

таблицы
Код: 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.
41.
42.
43.
44.
45.
46.
47.
DROP TABLE TABLES;

CREATE TABLE TABLES AS
WITH
T AS
(SELECT ROWNUM i FROM dual connect BY ROWNUM < 9)
SELECT t1.i r, t2.i c,
       (t1.i-1)*8+t2.i ID
  FROM T t1, T t2
;

DROP TABLE s;

CREATE TABLE s
AS
WITH
s AS(
SELECT  1 r,  2 c FROM dual UNION ALL
SELECT  1 r, -2 c FROM dual UNION ALL
SELECT  2 r, -1 c FROM dual UNION ALL
SELECT  2 r,  1 c FROM dual UNION ALL
SELECT -1 r,  2 c FROM dual UNION ALL
SELECT -1 r, -2 c FROM dual UNION ALL
SELECT -2 r, -1 c FROM dual UNION ALL
SELECT -2 r,  1 c FROM dual
)
SELECT t_from.ID id_from,
       t_from.r r_from,
       t_from.c c_from,
       t_to.ID id_to,
       t_to.r  r_to,
       t_to.c  c_to
  FROM TABLES t_from,
       s,
       TABLES t_to
 WHERE t_from.r + s.r = t_to.r
   AND t_from.c + s.c = t_to.c
 ORDER BY id_from, id_to;


DROP TABLE ss;

CREATE TABLE ss AS
SELECT s1.id_from, s1.id_to id_to1, s2.id_to id_to2
  FROM s s1,
       s s2
 WHERE s2.id_from = s1.id_to;



запрос
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
392.
393.
394.
395.
396.
397.
398.
399.
400.
401.
402.
403.
404.
405.
406.
407.
408.
409.
410.
411.
412.
413.
414.
415.
416.
417.
418.
419.
420.
421.
422.
423.
424.
425.
426.
427.
428.
429.
430.
431.
432.
433.
434.
435.
436.
437.
438.
439.
440.
441.
442.
443.
444.
445.
446.
447.
448.
449.
450.
451.
452.
453.
454.
455.
456.
457.
458.
459.
460.
461.
462.
463.
464.
465.
466.
467.
468.
469.
470.
471.
472.
473.
474.
475.
476.
477.
478.
479.
480.
481.
482.
483.
484.
485.
486.
487.
488.
489.
490.
491.
492.
493.
494.
495.
496.
497.
498.
499.
500.
501.
502.
503.
504.
505.
506.
507.
508.
509.
510.
511.
512.
513.
514.
515.
516.
517.
518.
519.
520.
521.
522.
523.
524.
525.
526.
527.
528.
529.
530.
531.
532.
533.
534.
535.
536.
537.
538.
539.
540.
541.
542.
543.
544.
545.
546.
547.
548.
549.
550.
551.
552.
553.
554.
555.
556.
557.
558.
559.
560.
561.
562.
563.
564.
565.
566.
567.
568.
569.
570.
571.
572.
573.
574.
575.
576.
577.
578.
579.
580.
581.
582.
583.
584.
585.
586.
587.
588.
589.
590.
591.
592.
593.
594.
595.
596.
597.
598.
599.
600.
601.
602.
603.
604.
605.
606.
607.
608.
609.
610.
611.
612.
613.
614.
615.
616.
617.
618.
619.
620.
621.
622.
623.
624.
625.
626.
627.
628.
629.
630.
631.
632.
633.
634.
635.
636.
637.
638.
639.
640.
641.
642.
643.
644.
645.
646.
647.
648.
649.
650.
651.
652.
653.
654.
655.
656.
657.
658.
659.
660.
661.
662.
663.
664.
665.
666.
667.
668.
669.
670.
671.
672.
673.
674.
675.
676.
677.
678.
679.
680.
681.
682.
683.
684.
685.
686.
687.
688.
689.
690.
691.
692.
693.
694.
695.
WITH
t0 AS
(SELECT ',1,' ID, 1 id_new FROM dual),
t1 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T0 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t2 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T1 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t3 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T2 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t4 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T3 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t5 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T4 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t6 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T5 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t7 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T6 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t8 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T7 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t9 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T8 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t10 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T9 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t11 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T10 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t12 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T11 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t13 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T12 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t14 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T13 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t15 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T14 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t16 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T15 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t17 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T16 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t18 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T17 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t19 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T18 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t20 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T19 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t21 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T20 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t22 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T21 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t23 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T22 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t24 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T23 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t25 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T24 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t26 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T25 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t27 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T26 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t28 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T27 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t29 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T28 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t30 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T29 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t31 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T30 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t32 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T31 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t33 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T32 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t34 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T33 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t35 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T34 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t36 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T35 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t37 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T36 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t38 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T37 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t39 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T38 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t40 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T39 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t41 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T40 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t42 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T41 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t43 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T42 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t44 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T43 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t45 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T44 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t46 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T45 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t47 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T46 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t48 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T47 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t49 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T48 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t50 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T49 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t51 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T50 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t52 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T51 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t53 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T52 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t54 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T53 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t55 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T54 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t56 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T55 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t57 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T56 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t58 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T57 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t59 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T58 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t60 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T59 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t61 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T60 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t62 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T61 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
   AND T.ID NOT LIKE '%,'||ss.id_to2||',%' 
 GROUP BY ss.id_to1
)),

t63 AS
(SELECT ID||id_new||',' ID, id_new FROM(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, MAX(MAX(ID)) ID
  FROM T62 T,
       ss
 WHERE ss.id_from = T.id_new
   AND T.ID NOT LIKE '%,'||ss.id_to1||',%' 
 GROUP BY ss.id_to1
))
SELECT * FROM t63



результат:
,1,18,33,50,60,54,64,47,62,56,39,24,7,13,3,9,26,41,58,52,35,25,10,4,19,2,17,11,5,20,14,8,23,40,55,61,51,57,42,59,49,34,44,29,46,63,48,31,16,6,12,27,37,43,53,36,30,45,28,22,32,38,21,15,



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

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
WITH
T0 AS (SELECT ROWNUM-1 I0, ROWNUM I FROM dual connect BY ROWNUM < 64)
SELECT
't' || i || ' AS
(select id||id_new||'','' id, id_new from(
SELECT MAX(ss.id_to1) KEEP(DENSE_RANK FIRST ORDER BY COUNT(*)) ID_new, max(max(id)) id
  FROM T' || i0 || ' t,
       ss
 WHERE ss.id_from = t.id_new
   AND T.id not like ''%,''||ss.id_to1||'',%'' 
   AND T.id not like ''%,''||ss.id_to2||'',%'' 
 GROUP BY ss.id_to1
)),
' FROM t0 

...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741231
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
оказывается, 11g не любит GROUP BY и аналитику в RECURSIVE WITH с UNION ALL
вываливается ORA-32486

а так бы всё красиво :)

Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
/* Formatted on 05.04.2012 23:21:38 (QP5 v5.163.1008.3004) */
WITH Z
     AS (SELECT     ROWNUM I
               FROM DUAL
         CONNECT BY ROWNUM < 9),
     TABLES
     AS (SELECT T1.I R, T2.I C, (T1.I - 1) * 8 + T2.I ID
           FROM Z T1, Z T2),
     Sint
     AS (SELECT 1 R, 2 C FROM DUAL
         UNION ALL
         SELECT 1 R, -2 C FROM DUAL
         UNION ALL
         SELECT 2 R, -1 C FROM DUAL
         UNION ALL
         SELECT 2 R, 1 C FROM DUAL
         UNION ALL
         SELECT -1 R, 2 C FROM DUAL
         UNION ALL
         SELECT -1 R, -2 C FROM DUAL
         UNION ALL
         SELECT -2 R, -1 C FROM DUAL
         UNION ALL
         SELECT -2 R, 1 C FROM DUAL),
     S
     AS (SELECT T_from.ID Id_from,
                T_from.R R_from,
                T_from.C C_from,
                T_to.ID Id_to,
                T_to.R R_to,
                T_to.C C_to
           FROM TABLES T_from, Sint S, TABLES T_to
          WHERE T_from.R + S.R = T_to.R AND T_from.C + S.C = T_to.C),
     Ss
     AS (SELECT S1.Id_from, S1.Id_to Id_to1, S2.Id_to Id_to2
           FROM S S1, S S2
          WHERE S2.Id_from = S1.Id_to),
     T0 AS (SELECT ',1,' ID, 1 Id_new, 1 L FROM DUAL),
     T(ID, Id_new, L)
     AS (
         SELECT ID, Id_new, L FROM T0
         UNION ALL
         --SELECT ID||id_new||',' ID, id_new, l+1 l FROM(
         SELECT      MAX(MAX(ID))
                  || MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*))
                  || ','
                     ID,
                  MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*))
                     Id_new,
                  MAX(MAX(L))+1 L
             FROM T, Ss
            WHERE Ss.Id_from = T.Id_new
              AND T.ID NOT LIKE '%,' || Ss.Id_to1 || ',%'
              AND T.ID NOT LIKE '%,' || Ss.Id_to2 || ',%'
              AND L < 63
         GROUP BY Ss.Id_to1--)
        )
SELECT *
  FROM T
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741243
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Добил-таки
одним запросом
:)
Код: 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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
WITH Z AS
        (SELECT ROWNUM I
            FROM DUAL
         CONNECT BY ROWNUM < 9
        ),
     TABLES AS
        (SELECT T1.I R, T2.I C, (T1.I - 1) * 8 + T2.I ID
           FROM Z T1, Z T2
         ),
     Sint
     AS (SELECT  1 R,  2 C FROM DUAL UNION ALL
         SELECT  1 R, -2 C FROM DUAL UNION ALL
         SELECT  2 R, -1 C FROM DUAL UNION ALL
         SELECT  2 R,  1 C FROM DUAL UNION ALL
         SELECT -1 R,  2 C FROM DUAL UNION ALL
         SELECT -1 R, -2 C FROM DUAL UNION ALL
         SELECT -2 R, -1 C FROM DUAL UNION ALL
         SELECT -2 R,  1 C FROM DUAL
        ),
     S AS
        (SELECT T_from.ID Id_from,
                T_from.R R_from,
                T_from.C C_from,
                T_to.ID Id_to,
                T_to.R R_to,
                T_to.C C_to
           FROM TABLES T_from, Sint S, TABLES T_to
          WHERE T_from.R + S.R = T_to.R AND T_from.C + S.C = T_to.C
        ),
     Ss
     AS (SELECT S1.Id_from, S1.Id_to Id_to1, S2.Id_to Id_to2
           FROM S S1, S S2
          WHERE S2.Id_from = S1.Id_to
        ),
     T0 AS (SELECT cast(',' AS VARCHAR2(4000)) ID FROM DUAL),
     T (ID, Id_new, L)
     AS (
         SELECT ID, 1 Id_new, 1 L FROM T0
         UNION ALL
         SELECT   ID || Id_new || ',' ID,
                  (
                     SELECT      MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*))
                         FROM Ss
                        WHERE Ss.Id_from = T.Id_new
                          AND T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to1 || ',%'
                          AND (T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to2 || ',%' OR l = 63)
                     GROUP BY Ss.Id_to1
                  )   Id_new,
                  L+1 L
             FROM T
            WHERE L < 64
        )
SELECT ID || id_new
  FROM T
 WHERE l = 64
 




для ОРакл 11XE
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741253
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну ты и демон. Ладно завтра проверю.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741737
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andreymxДобил-таки
одним запросом
:)

..

для ОРакл 11XE

а на результат с какой стороны смотреть?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
,1 ,18,33,50,60,54,64,47
,62,56,39,24, 7,13, 3, 9
,26,41,58,52,35,25,10, 4
,19, 2,17,11, 5,20,14, 8
,23,40,55,61,51,57,42,59
,49,34,44,29,46,63,48,31
,16, 6,12,27,37,43,53,36
,30,45,28,22,32,38,21,15
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741748
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish,

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

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

чесслово - я не нарочно. это цитирование обалдело
:)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37741772
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishandreymx,

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

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

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

Аудитория замерла в ожидании.

после 25-го хода количество вариантов позиции начинает уверенно падать.
пока - это всё, что могу сказать.
а полный расклад обязательно будет, но чуть позже. :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37749221
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Эээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37749229
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче.
не силён я в фольклоре. о чем вы?
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #37749455
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawishmaytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче.
не силён я в фольклоре. о чем вы?
А забудь, проехали.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38004537
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
быстро сказка сказывается, но как всегда дело делается
дотолкал я таки в гору этот паровоз. и .. получил, таки от оракла значение, которое и так знал -
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532
(спасибочки предыдущим сетевым и прочим исследователям, а также википедии)

четыре картинки (маслом) чего это стоило на (сугубо одной ноде от x2:2 1/4)
1) спейса - чтобы хранить все результаты (причем с учетом, что использовалась compress for query high) надо ~4.9 Tb.
но, поскольку всё хранить не надо, а достаточно хранить лишь два шага (из энного считается еэплюспервый), то
,в пике (35 ход) это "всего" 825 Gb
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38004542
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2) времени (тут мы понимаем, что один шаг состоит из 64/2 = 32 полей)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38004548
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
3)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38004549
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
4) ну и, собственно, результат
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38005155
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
orawish http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532dbms_photoshopТри минуты гугления привели к: 33,439,123,484,294 .Как же все-таки банально описание того, что процитированная мной цифра неправильная. http://en.wikipedia.org/wiki/Talk%3AKnight%27s_tour Yes, that's the entry, and I agree it's not completely clear. It claims "Loebbing and Wegener give 33,439,123,484,294 for the 8 X 8 board. The value given here is due to B. McKay and agrees with that given by Wegener in his book.". Reading Loebbing and Wegener gives the figure 33,439,123,484,294 (closed, undirected), but it also claims that it's wrong, because 33,439,123,484,294 is not divisible by 4 . It seems to me that the Sloane page is saying that 13,267,364,410,532 is the corrected figure for 33,439,123,484,294, and is therefore the correct number of closed, undirected 8x8 knight's tours. Wolfram's Mathworld agrees with the 13,267,364,410,532 figure, and they cite [Wegener, I. Branching Programs and Binary Decision Diagrams. Philadelphia, PA: SIAM, 2000] which is a book [ISBN 0-898-71458-3]. I don't have the book, but at this point I think we've got enough verifiability, so I'm going ahead. Until a wiki-author reads that book, I think we don't know the number of non-closed tours. Mathworld simply quotes the figure from the paper which gives the wrong figure for the number of closed tours, which must be highly suspect. Adam1729 07:23, 12 April 2007 (UTC) 13,267,364,410,532
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38005166
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dbms_photoshop,

да, симметрия - существенна для этой задачи.
так, очевидно, что решение для количества всех нециклических траекторий может быть получено как сумма 10 расчетов -
(например) с начальных полей a1,b1,b2,c1-c3,d1-d4, разумеется, с учетом соответствующего симметрии каждого поля веса.
также, для полей большой диагонали (a1,b2,c3,d4) симметрия позволяет вдвое (т.е. диагонально) ограничить и позиции второго хода.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38006184
collow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: 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.
with
  d as ( select level n from dual connect by level <= 8 )
, c as ( select x.n x, y.n y from d x, d y )
, s as (
    select  1 x,  2 y from dual union all
    select  2 x,  1 y from dual union all
    select -1 x,  2 y from dual union all
    select -2 x,  1 y from dual union all
    select  1 x, -2 y from dual union all
    select  2 x, -1 y from dual union all
    select -1 x, -2 y from dual union all
    select -2 x, -1 y from dual
  )
, p as (
    select c.x        x0
         , c.y        y0
         , c.x + s.x  x1
         , c.y + s.y  y1
      from c, s
     where c.x + s.x between 1 and 8
       and c.y + s.y between 1 and 8
  )
select level lev
     , sys_connect_by_path( p.x1 || p.y1, ',' ) route
  from p
 where level = 63
 start with p.x0 = 1 and p.y0 = 1
 connect by nocycle p.x0 = prior p.x1 and p.y0 = prior p.y1 and not ( p.x1 = 1 and p.y1 = 1 )


Написал тупо в лоб минут за 15. ОКончания работы пока не дождался. Тему не читал :)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38006223
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
collow..
Написал тупо в лоб минут за 15. ОКончания работы пока не дождался. Тему не читал :)
(имхо) ну и напрасно .
совершенно не обязательно прыгать на грабли, которые уже известны всем.
(и особенно больно, если прыгать с 64-го этажа)
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38006261
collow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну я как бы ни на что и не претендую.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38006272
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
collow,

Просто решил продемонстрировать свою туполобость?
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38006286
collow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да не, просто зацепил начальный пост о невозможности сделать это на чистом скл и тем более полный перебор. В этом плане да, решил немного выпендриться. Бывает. На самом деле если бы я сразу обратил внимание на дату начального поста, не стал бы вообще заморачиваться.
Ну а теперь можно и развитие сюжета почитать.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38161560
init.ora
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня )

сейчас для закрепления материала начал решать ее под оракл тем же методом.

каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида
:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
with x (a)  as(
select 1 a from dual
union all
select a
from(
	select  a+1 a
	from x where a<64
)z
)
select * from x



если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38161620
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
init.oraкаково же было мое удивлениеRSFC (recursive subquery factoring clause) вообще сильно отстает от CTE: 11020487 .
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38161971
init.ora
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
dbms_photoshopinit.oraкаково же было мое удивлениеRSFC (recursive subquery factoring clause) вообще сильно отстает от CTE: 11020487 .

Зато в RSFC можно писать в рекурсивной части
Код: plsql
1.
2.
3.
4.
5.
6.
with x as(
..
union all
select (select min\max from ....)
from x
)



что довольно неплохо.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38162075
Фотография orawish
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
init.oraРешал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня )

сейчас для закрепления материала начал решать ее под оракл тем же методом.

каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида
:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
with x (a)  as(
select 1 a from dual
union all
select a
from(
	select  a+1 a
	from x where a<64
)z
)
select * from x



если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql.
пример (как мне видится) сути вашей проблемы не отображает, ибо, чтобы заработал, достаточно выполнить то, что говорит вам
ORA-32042: рекурсивная фраза WITH должна напрямую ссылаться на себя в одной из ветвей UNION ALL
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
with x (a)  as(
select 1 a from dual
union all
-- select a
-- from(
	select  a+1 a
	from x where a<64
-- )z
)
select * from x;
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38162145
init.ora
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
orawishinit.oraРешал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня )

сейчас для закрепления материала начал решать ее под оракл тем же методом.

каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида
:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
with x (a)  as(
select 1 a from dual
union all
select a
from(
	select  a+1 a
	from x where a<64
)z
)
select * from x



если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql.
пример (как мне видится) сути вашей проблемы не отображает, ибо, чтобы заработал, достаточно выполнить то, что говорит вам
ORA-32042: рекурсивная фраза WITH должна напрямую ссылаться на себя в одной из ветвей UNION ALL
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
with x (a)  as(
select 1 a from dual
union all
-- select a
-- from(
	select  a+1 a
	from x where a<64
-- )z
)
select * from x;



Понятное дело!
пример, который я привел сильно упрощен, чтобы показать суть проблемы с которой я столкнулся.
В подзапросе хотел использовать Row_number(), вот так:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
...
Union all
select ....
from(
select row_number()over(order by ..) r
from ttt
)z where r=1
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38162163
Фотография -2-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
init.oraВ подзапросе хотел использовать Row_number(), вот таккак ты себе представляешь рекрсию по условию над результатами рекурсии. Если предполагаешь сначала сформировать набор, потом фильтровать, так и делай.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38162301
init.ora
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
-2-init.oraВ подзапросе хотел использовать Row_number(), вот таккак ты себе представляешь рекрсию по условию над результатами рекурсии. Если предполагаешь сначала сформировать набор, потом фильтровать, так и делай.

нет, нет.. никакой рекурсии над рекурсией.

хотелось бы сначала отфильтровать записи в зависимости от рекурсивного члена,
затем применить ROW_NUMBER, затем отфильтровать по нему.

в частности решение andreymx (точнее, последнюю его часть)
Код: plsql
1.
2.
3.
4.
5.
6.
SELECT      MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*))
     FROM Ss
    WHERE Ss.Id_from = T.Id_new
      AND T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to1 || ',%'
      AND (T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to2 || ',%' OR l = 63)
 GROUP BY Ss.Id_to1



я хотел (точнее не хотел, а не знал что можно так использовать MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) ) бы переписать таким образом( в MSSQL это возможно)
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
select cnt ...
from(
 select cnt,row_number()over(order by cnt) r
 from(
	 select count(Ss.Id_to1)over(partititon by S1.Id_from) cnt 
	 from ss
	 WHERE Ss.Id_from = T.Id_new
	 AND T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to1 || ',%'
	 AND (T.ID || Id_new || ',' NOT LIKE '%,' || Ss.Id_to2 || ',%' OR l = 63)
 )z
)z where r=1
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38174033
andreymxобычным SQL за 0.2 сек на Оракл 9.2? это реально :-)А можно два слова о подходе?
И что означают колонки и цифры в таблице ss?
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38174177
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Благодарный читательandreymxобычным SQL за 0.2 сек на Оракл 9.2? это реально :-)А можно два слова о подходе?
И что означают колонки и цифры в таблице ss?да там вроде всё понятно - что за подход
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #38174338
andreymxБлагодарный читательпропущено...
А можно два слова о подходе?
И что означают колонки и цифры в таблице ss?да там вроде всё понятно - что за подход

Он оказался слишком гениален для меня.
Так же как и число строк - 2008 в ss.
В чем идея?
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
пятничная задачка (про) коня
    #39942102
Jack963
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #39942133
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Jack963
dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке.
В мире есть 10 типов людей: которые понимают двоичную арифметику и которые нет.
Смирись. Если ты не в состоянии понять что-либо работающее, ты, тем более, не сможешь создать что-нибудь близкое по сложности сам. Ищи другую нишу для трудоустройства.
...
Рейтинг: 0 / 0
пятничная задачка (про) коня
    #39942227
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Jack963
dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке.
Юное дарование, в том сообщении откуда решение было взято также указан используемый метод.
Вместо того, чтоб почитать про метод ты решило избавиться от процедур и функций и сделать решение более сложным для понимания.
Это персональный выбор каждого - включить мозг или заниматься вредительством.
...
Рейтинг: 0 / 0
118 сообщений из 118, показаны все 5 страниц
Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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