puzzleup 2021

〇〇 · 发表于 2021-10-8 17:01

本帖最后由〇〇于 2021-10-8 17:03 编辑

居然还是错的，有个斜线不对

〇〇 · 发表于 2021-10-8 18:53

错在这里，+substr(s.plist,17,8)::bigint*10^5+substr(s.plist,17,8)::bigint*10^4

newkid · 发表于 2021-10-8 21:18

〇〇发表于 2021-10-8 18:53
错在这里，+substr(s.plist,17,8)::bigint*10^5+substr(s.plist,17,8)::bigint*10^4

我也是拆成两个8X4。
你改了bug之后，跑出来什么答案？

solomon_007 · 发表于 2021-10-8 21:54

〇〇发表于 2021-10-8 08:56
http://www.itpub.net/thread-1411980-1-1.html 说这个写法在 N=7, M=3的时候还能跑出答案，其他写法都崩溃 ...

我这里 7*7 + 2 还可以，7*7+3 就跑不出来了，为什么你的才 9分多钟。。

SQL> with t(n,c,x,y) as (select level,chr(64+level),ceil(level/7),mod(level-1,7)+1 from dual connect by level<=7*7),
  2    s(lvl,n,
  3    --nlist,
  4    clist) as (select 1,
  5                      n,
  6                      --cast(n as varchar2(100)),
  7                      c
  8                   from t
  9                where t.n between 1 and 7/2
10                union all
11                select lvl + 1,
12                      b.n,
13                      --nlist||','||b.n,
14                      clist||','||b.c
15                from s,t b
16                where s.n < b.n
17                   and (select greatest(sum(case when a.x = b.x then 1 end),
18                                        sum(case when a.y = b.y then 1 end),
19                                        sum(case when a.x-b.x = a.y-b.y then 1 end),
20                                        sum(case when a.x-b.x = b.y-a.y then 1 end)
21                                        )
22                         from t a
23                         where instr(clist||','||b.c,a.c)>0
24                      ) <= 2
25                   and b.n between (ceil((lvl+1)/2)-1)*7 + 1 and (ceil((lvl+1)/2)-1)*7 + 7
26                )
27 select max(lvl) from s
28  /

  MAX(LVL)
----------
      14

Executed in 47.695 seconds

〇〇 · 发表于 2021-10-8 22:00

这种大表笛卡尔积运算开并行有用吧

〇〇 · 发表于 2021-10-8 22:02

我的是2c16核的工作站

solomon_007 · 发表于 2021-10-8 22:10

呵呵，我 rownum 放大一些，大概率能得到 24，几秒钟：

SQL>
SQL> with t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from dual connect by level<=8*8),
  2    s(lvl,n,
  3    --nlist,
  4    clist) as (select 1,
  5                      n,
  6                      --cast(n as varchar2(100)),
  7                      c
  8                   from t
  9                where t.n between 1 and 8/3
10                union all
11                select lvl + 1,
12                      b.n,
13                      --nlist||','||b.n,
14                      clist||','||b.c
15                from s,t b
16                where s.n < b.n
17                   and (select greatest(sum(case when a.x = b.x then 1 end),
18                                        sum(case when a.y = b.y then 1 end),
19                                        sum(case when a.x-b.x = a.y-b.y then 1 end),
20                                        sum(case when a.x-b.x = b.y-a.y then 1 end)
21                                        )
22                         from t a
23                         where instr(clist||','||b.c,a.c)>0
24                      ) <= 3
25                   and b.n between (ceil((lvl+1)/3)-1)*8 + 1 and (ceil((lvl+1)/3)-1)*8 + 8
26                   and rownum <= 8000
27                )
28 select max(lvl) from s
29  /

  MAX(LVL)
----------
      24

Executed in 6.845 seconds

SQL> /

  MAX(LVL)
----------
      24

Executed in 6.65 seconds

SQL> /

  MAX(LVL)
----------
      24

Executed in 6.652 seconds

solomon_007 · 发表于 2021-10-8 22:22

给个图解

2,3,4,
9,10,11,
17,18,23,
29,31,32,
37,39,40,
44,46,48,
49,52,54,
59,61,62c:\temp\666.png

solomon_007 · 发表于 2021-10-8 22:26

〇〇发表于 2021-10-8 22:02
我的是2c16核的工作站

不错，我是笔记本 i5

solomon_007 · 发表于 2021-10-8 22:30

8000,可以随机得到2到3个解，呵呵：

SQL>
SQL> with t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from dual connect by level<=8*8),
  2    s(lvl,n,
  3    nlist,
  4    clist) as (select 1,
  5                      n,
  6                      cast(n as varchar2(100)),
  7                      c
  8                   from t
  9                where t.n between 1 and 8/3
10                union all
11                select lvl + 1,
12                      b.n,
13                      nlist||','||b.n,
14                      clist||','||b.c
15                from s,t b
16                where s.n < b.n
17                   and (select greatest(sum(case when a.x = b.x then 1 end),
18                                        sum(case when a.y = b.y then 1 end),
19                                        sum(case when a.x-b.x = a.y-b.y then 1 end),
20                                        sum(case when a.x-b.x = b.y-a.y then 1 end)
21                                        )
22                         from t a
23                         where instr(clist||','||b.c,a.c)>0
24                      ) <= 3
25                   and b.n between (ceil((lvl+1)/3)-1)*8 + 1 and (ceil((lvl+1)/3)-1)*8 + 8
26                   and rownum <= 8000
27                )
28 select lvl,nlist from s where lvl=(  select max(lvl) from s ) and rownum<=100
29  /

   LVL NLIST
---------- --------------------------------------------------------------------------------
      24 2,3,4,9,10,11,17,18,23,29,31,32,37,39,40,44,46,48,49,52,54,59,61,62
      24 2,3,4,9,10,11,17,18,23,30,31,32,36,37,40,46,47,48,49,52,53,59,61,62
      24 2,3,4,9,10,11,17,18,23,30,31,32,37,38,40,41,43,48,52,53,55,60,61,62

SQL> set timing on;
SQL>
SQL>
SQL> with t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from dual connect by level<=8*8),
  2    s(lvl,n,
  3    nlist,
  4    clist) as (select 1,
  5                      n,
  6                      cast(n as varchar2(100)),
  7                      c
  8                   from t
  9                where t.n between 1 and 8/3
10                union all
11                select lvl + 1,
12                      b.n,
13                      nlist||','||b.n,
14                      clist||','||b.c
15                from s,t b
16                where s.n < b.n
17                   and (select greatest(sum(case when a.x = b.x then 1 end),
18                                        sum(case when a.y = b.y then 1 end),
19                                        sum(case when a.x-b.x = a.y-b.y then 1 end),
20                                        sum(case when a.x-b.x = b.y-a.y then 1 end)
21                                        )
22                         from t a
23                         where instr(clist||','||b.c,a.c)>0
24                      ) <= 3
25                   and b.n between (ceil((lvl+1)/3)-1)*8 + 1 and (ceil((lvl+1)/3)-1)*8 + 8
26                   and rownum <= 8000
27                )
28 select lvl,nlist from s where lvl=(  select max(lvl) from s ) and rownum<=100
29  /

   LVL NLIST
---------- --------------------------------------------------------------------------------
      24 1,2,3,9,10,11,17,22,23,29,31,32,34,39,40,44,45,48,51,52,54,60,61,62
      24 1,2,3,9,10,11,17,22,23,30,31,32,34,36,40,45,47,48,51,52,53,60,61,62

Executed in 6.844 seconds

[每日一题] puzzleup 2021