puzzleup 2021

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

newkid 发表于 2021-10-8 23:16
不错，下一步能否得到所有解的个数？我这个写法是用旧SQL改的：WITH r AS ( ---------- 一行里放M个球， ...

居然我和你思路是接近的，7-8确实多余的，只要不含456就行了

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

〇〇发表于 2021-10-9 05:52
概率居然这么大，我试过row_number order by 结果行定少了，只能出18，就放弃了。改成8000仍然出不来。with ...

愚昧了 generate_series(1,8*6) 应该是 generate_series(1,8*8)

test-# select max(lvl),count(*) from s;
max | count
-----+--------
24 | 280150
(1 行记录)

时间：12811.482 ms (00:12.811)

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

〇〇发表于 2021-10-9 09:08
愚昧了 generate_series(1,8*6) 应该是 generate_series(1,8*8)test-# select max(lvl),count(*) from s; ...

rn<700,1秒，n<600就只能出23了
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*8)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<700
                        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
-----+-------
  24 | 31075
(1 行记录)

时间：1077.719 ms (00:01.078)

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

一个rownum解决这么大问题， 8 8 4，rownum加到800， 1.5秒
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*8)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/4*8+1 and lvl/4*8+8  and rn<800
                        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)<=4
                        )
select max(lvl),count(*) from s;

max | count
-----+-------
  32 | 43013
(1 行记录)

时间：1545.539 ms (00:01.546)

〇〇 · 发表于 2021-10-9 10:04

本帖最后由〇〇于 2021-10-9 15:01 编辑

8 8 5
with RECURSIVE
t(n,c,x,y) as (select level,chr(32+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*8)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/5*8+1 and lvl/5*8+8  and rn<1200
                        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)<=5
                        )
select max(lvl),count(case when lvl=40 then 1 end) from s;
max | count
-----+-------
  40 |    1
(1 行记录)

时间：2483.671 ms (00:02.484)

8 8 6with RECURSIVE
t(n,c,x,y) as (select level,chr(32+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*8)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/6*8+1 and lvl/6*8+8  and rn<3000
                        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)<=6
                        )
select max(lvl),count(case when lvl=48 then 1 end) from s;
max | count
-----+-------
  48 |    1
(1 行记录)

时间：6429.706 ms (00:06.430)

--8 8 7
with RECURSIVE
t(n,c,x,y) as (select level,chr(32+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*8)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/7*8+1 and lvl/7*8+8  and rn<3000
                        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)<=7
                        )
select max(lvl),count(case when lvl=56 then 1 end) from s;

max | count
-----+-------
  56 |    1
(1 行记录)

时间：5250.644 ms (00:05.251)

insert into t884
with RECURSIVE
t(n,c,x,y) as (select level,chr(32+level),ceil(level/9),mod(level-1,9)+1 from  generate_series(1,9*9)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/7*9+1 and lvl/7*9+9  and rn<10000
                        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)<=7
                        )
select * from s where lvl=63;

INSERT 0 9
时间：38117.848 ms (00:38.118)

test=# select * from t884 where lvl=63;
lvl | n  |                                                          clist                                                          | rn
-----+----+-------------------------------------------------------------------------------------------------------------------------------+----
  63 | 81 | ",#,$,%,&,',(,*,,,-,.,/,0,1,3,4,5,7,9,:,;,<,?,@,A,B,C,D,E,F,G,H,J,L,M,N,O,P,Q,S,T,V,W,X,Z,[,],^,_,`,a,b,d,e,f,h,j,k,l,m,n,p,q |  1
...
(9 行记录)

时间：0.668 ms
能否数学上证明n*n 每行最多m的解就是n*m?

newkid · 发表于 2021-10-9 21:54

这些中间加ROWNUM限制的方法，在逻辑上都不严密。

solomon_007 · 发表于 2021-10-10 21:33

newkid 发表于 2021-10-8 23:16
不错，下一步能否得到所有解的个数？我这个写法是用旧SQL改的：WITH r AS ( ---------- 一行里放M个球， ...

本打算用纯PLSQL写一个，看看 8*8+3 到底有多少个解，但发现套了很多层循环，没意思，放弃了！

solomon_007 · 发表于 2021-10-10 21:50

〇〇发表于 2021-10-9 10:04
8 8 5with RECURSIVEt(n,c,x,y) as (select level,chr(32+level),ceil(level/8),mod(level-1,8)+1 from ge ...

行 8 个
a11 + a12 + ... + a18 = 3
a21 + a22 + ... + a28 = 3
...
a81 + a82 + ... + a88 = 3

列 8 个
a11 + a21 + ... + a81 = 3
a12 + a22 + ... + a82 = 3
...
a18 + a28 + ... + a88 = 3

左上右下对角线 11 条

左下右上对角线 11 条

共计 8+8+11+11=38 个方程，64个未知数，所以满足条件的解总是存在的！

solomon_007 · 发表于 2021-10-10 21:55

并且 a(ij) 属于 {0，1}，联立起来就是线性规划的问题

〇〇 · 发表于 2021-10-10 22:56

对角线的方程不定啊，要不用mathematica解决了

[每日一题] puzzleup 2021