пятничная задачка (про) коня / Oracle

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня

25 сообщений из 118, страница 3 из 5

все

пятничная задачка (про) коня

#37737152

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

dbms_photoshop..
А вот если на входе может быть любое поле, а не a1 это уже интересней.
и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвост

...

Рейтинг:

0 / 0

03.04.2012, 19:24

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37737494

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

orawishdbms_photoshop..
А вот если на входе может быть любое поле, а не a1 это уже интересней.
и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность.
Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны.
В общем цель была как можно быстрее написать эту рутину.
Красным выделено ноу-хау решения.

Уже озвученный правило Варнсдорфа

Код: plsql

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

04.04.2012, 01:25

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37737578

andreymx

Участник

Откуда: Запорожье

Сообщения: 56 486

Рейтинг: 0 / 0

попробовал 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

04.04.2012, 07:19

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738323

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

dbms_photoshoporawishпропущено...

и всё же - вашу мысль я не догоняю..
пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля
(a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо
перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность.
Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны.
В общем цель была как можно быстрее написать эту рутину.
Красным выделено ноу-хау решения.
..
Процесс поиска замкнутого я уже не автоматизировал, легче было поклацать.
а я считаю, что зря вы скромничаете - в том смысле, что очень хорошее решение нарисовали.
для задачи 1) оно просто вне конкуренции
процесс поклацать до циклического (т.е. решение задачи 2 ) тут

Код: plsql

 
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

04.04.2012, 13:37

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738396

Vint

Участник

Откуда: Москва

Сообщения: 4 120

Рейтинг: 0 / 0

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

04.04.2012, 14:13

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738416

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

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

04.04.2012, 14:21

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738553

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

мой способ - тут

Код: plsql

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

04.04.2012, 15:07

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738560

Vint

Участник

Откуда: Москва

Сообщения: 4 120

Рейтинг: 0 / 0

orawish,
надеюсь за плагиат не побьют))

Код: plsql

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

04.04.2012, 15:12

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738577

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

dbms_photoshop,

это попытка таки понакликать (тупым упорством) 1001 различное решение задачи 2)

Код: plsql

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

04.04.2012, 15:22

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738700

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

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

04.04.2012, 16:18

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738735

Vint

Участник

Откуда: Москва

Сообщения: 4 120

Рейтинг: 0 / 0

orawish,
в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться)
итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше))

...

Рейтинг:

0 / 0

04.04.2012, 16:31

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738779

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

Vintorawish,
в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться)
итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше))
как быть с тем, что

Код: plsql

1.
2.

select 21390*21390 from dual; 
> 450 000 000

? и это только варианты, которые обязаны на 32 ходу соответствовать одной позиции, а их, (позиций) 10 в степени до-фи-га

...

Рейтинг:

0 / 0

04.04.2012, 16:44

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738842

Vint

Участник

Откуда: Москва

Сообщения: 4 120

Рейтинг: 0 / 0

orawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.

...

Рейтинг:

0 / 0

04.04.2012, 17:07

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738897

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

Vintorawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.
ну, поскольку я (в основном) долбил задачу от середины, то уверенно могу сказать - и после 32 хода количество вариантов
на каждом последующем ходу продолжает будь-здоров как расти (настолько, что перебор без дополнительных мер не имеет шансов).
и еще - можете посмотреть на каком (начиная от первого) ходу накрываются тазом брутфорсы и сколько (+ какой прирост на уровень) вариантов уникальных позиций имеют они тогда.

...

Рейтинг:

0 / 0

04.04.2012, 17:26

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738910

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

Vintorawish,
если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу.
кстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)

...

Рейтинг:

0 / 0

04.04.2012, 17:30

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738918

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

orawishпроцесс поклацать до циклического (т.е. решение задачи 2 ) тутПросто у меня при тестировании с третьей попытки получился замкнутый маршрут и я решил не париться. :)
orawish задача 3) - 1001 решение найтиЕсли начинать не из угла доски, то, думаю, время нахождения 1001 решения сократится в разы.
orawish задача 4) таки попробовать оценить их (решений) количествоВот это самое интересное.
Как написано по ссылке, которую я уже приводил: http://golovolomka.hobby.ru/books/gik/02.shtml Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня по доске, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C63168 (число сочетаний из 168 элементов по 63, оно состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом провести, практически неосуществимы.Интересно что за метод, вычисления для которого практически не осуществимы, при этом для половины доски уже найдено точное число решений.
Как бы там ни было, делать свои брутфорсы без изучения работ по тематике из сабжа бессмысленно.

...

Рейтинг:

0 / 0

04.04.2012, 17:32

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738933

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

orawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 .

...

Рейтинг:

0 / 0

04.04.2012, 17:36

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738936

Vint

Участник

Откуда: Москва

Сообщения: 4 120

Рейтинг: 0 / 0

dbms_photoshop,
хм.. а мне казалось что всё проще))).....

...

Рейтинг:

0 / 0

04.04.2012, 17:37

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738945

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Созрел быстрый и универсальный алгоритм для обхода произвольных областей клеток.

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

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

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

Кривую Гилберта я взял просто без оснований. Интуитивно. Хотя по ней можно
спорить. Возможно есть варианты обхода "змейкой", "спиралью", Z-порядком e.t.c.

...

Рейтинг:

0 / 0

04.04.2012, 17:40

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37738988

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

dbms_photoshoporawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы).
попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 .
отлично! ответ известен. осталось получить его от оракла :)

...

Рейтинг:

0 / 0

04.04.2012, 18:01

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37739015

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

mayton,

Уже потихоньку начинает напрягать желание местных обитателей пытаться изобретать велосипед.
По ссылке, что я приводил есть абзац: "При каких значениях m и n существует маршрут коня по всем полям доски m*n (с посещением каждого из них по одному разу)?"

...

Рейтинг:

0 / 0

04.04.2012, 18:15

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37739019

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

orawishdbms_photoshopпропущено...
Три минуты гугления привели к: 33,439,123,484,294 .
отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы.

...

Рейтинг:

0 / 0

04.04.2012, 18:16

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37739021

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

dbms_photoshop, чел, я говорю не о прямоугольных досках.

...

Рейтинг:

0 / 0

04.04.2012, 18:17

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37739027

orawish

Участник

Откуда: Гадюкино-2 (City)

Сообщения: 15 402

Рейтинг: 0 / 0

dbms_photoshoporawishпропущено...

отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы.
ну а я попробую усовершенствовать силовой вариант. ~2e9 решений полузадачи это не так уж и много.
опять же - одно дело посчитать сколько их, а другое - отрисовать их всех

...

Рейтинг:

0 / 0

04.04.2012, 18:21

| Ответить | Цитировать | Написать

пятничная задачка (про) коня

#37739029

dbms_photoshop

Участник

Откуда: sqlmdx.net

Сообщения: 5 140

Рейтинг: 0 / 0

mayton,

Ок, надеюсь не надо доказывать, что, к примеру, для доски с шириной 2 и любой длиной задача неразрешима?
Если подумать далее, то можно прийти к заключению, что область можно разбить на некоторые разрешимые подобласти.
Обход делается опять же по правилу Варнсдорфа.
К чему здесь блистать своими анти познаниями по кривым?

...

Рейтинг:

0 / 0

04.04.2012, 18:22

| Ответить | Цитировать | Написать

25 сообщений из 118, страница 3 из 5

все

Форумы / Oracle [игнор отключен] [закрыт для гостей] / пятничная задачка (про) коня

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=52&msg=37739015&tid=1881402]:	0ms
get settings:	9ms
get forum list:	13ms
check forum access:	4ms
check topic access:	4ms
track hit:	77ms
get topic data:	12ms
get forum data:	3ms
get page messages:	67ms
get tp. blocked users:	2ms
others:	14ms

total:	205ms