puzzleup 2021

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

newkid · 发表于 2021-10-8 23:16

不错，下一步能否得到所有解的个数？

我这个写法是用旧SQL改的：
WITH r AS ( ---------- 一行里放M个球，这M个球所处的列位置的所有组合
SELECT s as one_row
  FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
      FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
      WHERE LEVEL=8
      CONNECT BY LEVEL<=8
   )
WHERE LENGTH(s)-NVL(LENGTH(REPLACE(s,'1')),0)=3
)
,balls (row_cnt -- 当前行数
   ,all_rows -- 截至当前行，所有行的摆法拼接的结果
   ,col_cnt -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
   ,diag_cnt1  -- 此数字表示在右上至左下的斜线上各位的和
   ,diag_cnt2  -- 此数字表示在左上至右下的斜线上各位的和
   )
AS (
SELECT 1,one_row,TO_NUMBER(one_row),TO_NUMBER(one_row),TO_NUMBER(one_row) ---初始化第一行数据
   FROM r
UNION ALL
SELECT balls.row_cnt+1  ---- 行数递增
      ,balls.all_rows||r.one_row  ---当前行拼入总结果
      ,balls.col_cnt+r.one_row --- 在列方向各位进行累加
      ,balls.diag_cnt1*10+r.one_row  ---- 在斜线方向各位进行累加
      ,balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt)
   FROM balls,r
WHERE balls.row_cnt<4 ---- 递归出口
      AND INSTR(balls.col_cnt+r.one_row,3+1)=0 ---- 把带M+1的结果拦截掉
      AND INSTR(balls.diag_cnt1*10+r.one_row,3+1)=0
      AND INSTR(balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt),3+1)=0
)
,q4 as (
SELECT /*+ materialize */ * FROM balls WHERE row_cnt=4
)
select /*+ use_hash(a b) */ a.ALL_ROWS||b.ALL_ROWS
  from q4 a,q4 b
where 33333333-a.COL_CNT=b.COL_CNT  -------- 大胆假设答案存在，有这个条件才能做HASH JOIN
   and not regexp_like(a.DIAG_CNT1*1e4+b.DIAG_CNT1,'4|5|6')
   and not regexp_like(b.DIAG_CNT2*1e4+a.DIAG_CNT2,'4|5|6')
   and rownum=1
;

A.ALL_ROWS||B.ALL_ROWS
----------------------------------------------------------------------------
0**100000010011000**01000001111110000011100000**0100000001110

Elapsed: 00:03:10.47

〇〇 · 发表于 2021-10-9 05:52

本帖最后由〇〇于 2021-10-9 08:54 编辑

概率居然这么大，我试过row_number order by 结果行定少了，只能出18，就放弃了。
改成8000仍然出不来。
with RECURSIVE
t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*6)level),
   s(lvl,n,
   --nlist,
   clist,rn) as (select 1::int,
                           n,
                           --cast(n as varchar2(100)),
                           c,1::bigint
                        from t where t.n between 1 and 4
                     union all
                     select lvl + 1,
                           b.n,
                           --nlist||','||b.n,
                           clist||','||b.c ,row_number()over(order by b.n)
                        from s,t b
                     where s.n < b.n and b.n between lvl/3*8+1 and lvl/3*8+8  and rn<8000
                        and (select greatest(sum(case when a.x = b.x then 1 end),
                                             sum(case when a.y = b.y then 1 end),
                                             sum(case when a.x-b.x = a.y-b.y then 1 end),
                                             sum(case when a.x-b.x = b.y-a.y then 1 end)
                                             )
                              from t a
                              where position(a.c in clist||','||b.c)>0)<=3
                        )
select max(lvl),count(*) from s;

max | count
-----+--------
  18 | 390231
(1 行记录)

时间：10382.809 ms (00:10.383)

加了随机排序，还是一样不行
with RECURSIVE
t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*6)level),
   s(lvl,n,
   --nlist,
   clist,rn) as (select 1::int,
                           n,
                           --cast(n as varchar2(100)),
                           c,1::bigint
                        from t where t.n between 1 and 4
                     union all
                     select lvl + 1,
                           b.n,
                           --nlist||','||b.n,
                           clist||','||b.c ,row_number()over(order by random())
                        from s,t b
                     where s.n < b.n and b.n between lvl/3*8+1 and lvl/3*8+8  and rn<8000
                        and (select greatest(sum(case when a.x = b.x then 1 end),
                                             sum(case when a.y = b.y then 1 end),
                                             sum(case when a.x-b.x = a.y-b.y then 1 end),
                                             sum(case when a.x-b.x = b.y-a.y then 1 end)
                                             )
                              from t a
                              where position(a.c in clist||','||b.c)>0)<=3
                        )
select max(lvl),count(*) from s;

max | count
-----+--------
  18 | 255928
(1 行记录)

时间：7571.092 ms (00:07.571)

想改成你的写法，pg不支持
test(#                               where position(a.c in clist||','||b.c)>0)<=3  limit 6000
test(#                            )
test-# select max(lvl),count(*) from s;
ERROR:  LIMIT in a recursive query is not implemented
第23行...ere position(a.c in clist||','||b.c)>0)<=3  limit 6000    ...
                                                         ^

〇〇 · 发表于 2021-10-9 08:09

newkid 发表于 2021-10-8 21:18
我也是拆成两个8X4。你改了bug之后，跑出来什么答案？

ｔｅｓｔ－＃　ｓｅｌｅｃｔ　＊　ｆｒｏｍ　ｊ　ｌｉｍｉｔ　１；
　　　　ｓ
－－－－－－－－－－
　１０００１１００＋
　００１１００１０＋
　００００１０１１＋
　０００００１１１＋
　１１１０００００＋
　１１１０００００＋
　０１０１１０００＋
　０００１０１０１
（１　行记录）

时间：８４６４５３．９５８　ｍｓ　（１４：０６．４５４）

[每日一题] puzzleup 2021