puzzleup 2021

〇〇

solomon_007 发表于 2021-10-18 22:32
OO，ORACLE 版本的，你发个完整版吧，sqlite/postgres 都没有环境

oracle语法检查比sqlite/posgresql严格，第一行就报错，
with t6(n) as (select 1 from dual union all select n+1 from t where n<6)
                                                            *
第 2 行出现错误:
ORA-32031: WITH 子句中查询名的引用非法


已用时间:  00: 00: 00.06
把移位改成power，取整改为floor,改完又不知错在哪了。
SQL> --oracle
SQL> create table chess6f as
  2  with t6(n) as (select 1 from dual union all select n+1 from t6 where n<6)
  3  ,
  4  b3(a,b,c,bit)as(select a.n,b.n,c.n,(power(2,a.n-1))+(power(2,b.n-1))+(power(2,c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
  5  ,
  6  b9(b)as(select c.bit*((power(2,r.a-1)*6)+(power(2,r.b-1)*6)+(power(2,r.c-1)*6)) from b3 c,b3 r)
  7  ,
  8  t(n,c,x,y)
  9  as(select 1,cast('1'as varchar(100)),1,1 from dual union all select n+1,cast(n+1 as varchar(100)),floor(n/6)+1,mod(n,6)+1 from t where n<6*6)
10  ,
11  s(lv,n,nlist,blist,px,py)
12  as(select 1,t.n,t.c,power(2,t.n-1),power(10,t.x),power(10,t.y) from t where t.n<=6
13  union all
14  select lv+1,b.n,nlist||','||c,blist+(power(2,b.n-1)),px+power(10,b.x),py+power(10,b.y)
15  from s,t b
16  where lv<10 and s.n<b.n and b.x < floor(s.n/6) +3
17  --and(blist%19<14)
18  and (instr(px+power(10,b.x),3)=0 and instr(py+power(10,b.y),3)=0)
19  --and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
20  --  where ((blist+(power(2,b.n-1))&(power(2,a.n-1)))>0))<=2
21  and b.n  between floor(lv/2)*6+1 and floor(lv/2)*6+6*2
22  )
23  select * from s where lv=10 and not exists(select 1 from b9 where  bitand(blist , b9.b) =0)
24  ;

表已创建。

已用时间:  00: 06: 15.61
SQL> select count(*) from chess6f;

  COUNT(*)
----------
       151

找出来的也不知对错
SQL> col nlist format a50
SQL> /

        LV          N NLIST                                                   BLIST         PX         PY
---------- ---------- -------------------------------------------------- ---------- ---------- ----------
        10         28 5,6,7,12,13,14,20,21,27,28                          202913904     222220    2112220
        10         29 5,6,7,12,13,14,20,21,27,29                          337131632     222220    2202220
        10         34 5,6,7,12,13,14,20,21,27,34                         8658630768    1122220    2112220
        10         35 5,6,7,12,13,14,20,21,27,35                         1.7249E+10    1122220    2202220
        10         29 5,6,7,12,13,14,20,21,28,29                          404240496     222220    2211220
        10         33 5,6,7,12,13,14,20,21,28,33                         4430772336    1122220    2112220
        10         34 5,6,7,12,13,14,20,21,28,34                         8725739632    1122220    2121220
        10         35 5,6,7,12,13,14,20,21,28,35                         1.7316E+10    1122220    2211220
        10         33 5,6,7,12,13,14,20,21,29,33                         4564990064    1122220    2202220

已选择 9 行。

〇〇

〇〇 发表于 2021-10-19 08:25
oracle语法检查比sqlite/posgresql严格，第一行就报错，with t6(n) as (select 1 from dual union all sele ...

找到原因了，计算位图的power括号写错了


--oracle sql
create table chess6f as
with t6(n) as (select 1 from dual union all select n+1 from t6 where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(power(2,a.n-1))+(power(2,b.n-1))+(power(2,c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*(power(2,(r.a-1)*6)+power(2,(r.b-1)*6)+power(2,(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast('1'as varchar(100)),1,1 from dual union all select n+1,cast(n+1 as varchar(100)),floor(n/6)+1,mod(n,6)+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,power(2,t.n-1),power(10,t.x),power(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(power(2,b.n-1)),px+power(10,b.x),py+power(10,b.y)
from s,t b
where lv<10 and s.n<b.n and b.x < floor(s.n/6) +3
--and(blist%19<14)
and (instr(px+power(10,b.x),3)=0 and instr(py+power(10,b.y),3)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(power(2,b.n-1))&(power(2,a.n-1)))>0))<=2
and b.n  between floor(lv/2)*6+1 and floor(lv/2)*6+6*2
)
select * from s where lv=10 and not exists(select 1 from b9 where  bitand(blist , b9.b) =0)
;

表已创建。

已用时间:  00: 11: 12.11
SQL>
SQL>
SQL>
SQL> select count(*) from chess6f;

  COUNT(*)
----------
     32400

已用时间:  00: 00: 00.04
学newkid加上实体化提示
SQL> --oracle sql
SQL> create table chess6f as
  2  with t6(n) as (select 1 from dual union all select n+1 from t6 where n<6)
  3  ,
  4  b3(a,b,c,bit)as(select a.n,b.n,c.n,(power(2,a.n-1))+(power(2,b.n-1))+(power(2,c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
  5  ,
  6  b9(b)as(select /*+ materialize */ c.bit*(power(2,(r.a-1)*6)+power(2,(r.b-1)*6)+power(2,(r.c-1)*6)) from b3 c,b3 r)
  7  ,
  8  t(n,c,x,y)
  9  as(select 1,cast('1'as varchar(100)),1,1 from dual union all select n+1,cast(n+1 as varchar(100)),floor(n/6)+1,mod(n,6)+1 from t where n<6*6)
10  ,
11  s(lv,n,nlist,blist,px,py)
12  as(select 1,t.n,t.c,power(2,t.n-1),power(10,t.x),power(10,t.y) from t where t.n<=6
13  union all
14  select lv+1,b.n,nlist||','||c,blist+(power(2,b.n-1)),px+power(10,b.x),py+power(10,b.y)
15  from s,t b
16  where lv<10 and s.n<b.n and b.x < floor(s.n/6) +3
17  --and(blist%19<14)
18  and (instr(px+power(10,b.x),3)=0 and instr(py+power(10,b.y),3)=0)
19  --and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
20  --  where ((blist+(power(2,b.n-1))&(power(2,a.n-1)))>0))<=2
21  and b.n  between floor(lv/2)*6+1 and floor(lv/2)*6+6*2
22  )
23  select * from s where lv=10 and not exists(select 1 from b9 where  bitand(blist , b9.b) =0)
24  ;

表已创建。

已用时间:  00: 05: 24.28

〇〇

newkid 发表于 2021-10-17 07:36
给猫猫转了个章。答案至少为十。反证法：假设九能满足。划走三行之后，剩下的棋子如果不超过三个，则不满足 ...

利用结果中不可能有重复行的思路，把newkid的改进了三下，一半时间


WITH
-------- 先把10个棋子放置在6X6，使得每行每列不超过两个（满足尽量均分的思路）
c as (select power(2,level-1) b,power(10,level-1) d from dual connect by level<=6) --- 1~6 位比特
,r as (select c1.b+c2.b b -------- 所有每行两个棋子的位置组合
      ,c1.d+c2.d d
      ,2 as cnt
  from c c1,c c2
where c1.b<c2.b
union all
select b,d,1 from c  -------- 加上每行一个棋子的位置
)
----- 递归三行的结果
,r2 (row_cnt    -- 当前行数
       ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
       ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
       ,b
       ,cnt
       )
AS (
   SELECT 1,lpad(d,6,'0'),d,b,cnt
     FROM r
   UNION ALL
   SELECT r2.row_cnt+1  ---- 行数递增
         ,r2.all_rows||lpad(r.d,6,'0')  ---当前行拼入总结果
         ,r2.col_cnt+r.d    --- 在列方向各位进行累加
         ,r2.b*power(2,6)+r.b
         ,r2.cnt+r.cnt
     FROM r2,r
    WHERE r2.row_cnt<3 ---- 递归出口
          AND INSTR(r2.col_cnt+r.d,3)=0 ---- 把带M+1的结果拦截掉
          and r2.cnt+r.cnt<=10 and mod(instr(r2.all_rows,lpad(r.d,6,'0')),6)<>1 --消除一块之内的重复行
)
,r3 as (select * from r2 where row_cnt=3)  -------- 6X3的结果
,r6 as (  -------- 两个6X3的结果拼成6X6
select /* materialize */ r31.all_rows||r32.all_rows as all_rows
      ,r31.col_cnt+r32.col_cnt as col_cnt
      ,r31.b*power(2,18)+r32.b as b
from r3 r31,r3 r32
where r31.all_rows<r32.all_rows --上半块小于下半块，因为不可能有重复行，所以相等不需考虑，然后把最后的结果上下半块对调就能得到所有解
      and not regexp_like(r31.col_cnt+r32.col_cnt,'3|4')  -------- 每列不超过两个
      and r31.cnt+r32.cnt=10  ------- 总数十个棋子
and mod(instr(r32.all_rows,substr(r31.all_rows,1,6)),6)<>1 --消除两块之间的重复行
and mod(instr(r32.all_rows,substr(r31.all_rows,7,6)),6)<>1
and mod(instr(r32.all_rows,substr(r31.all_rows,13,6)),6)<>1
)
-----------下面构造所有3X3 的BITAND掩码。一个满足条件的答案在BITAND之后都不为零，即每个3X3里面至少有一个棋子
,n as (
select p,substr(p,level,1) n   ------- 再把三个坐标拆成三行
from (
      select replace(sys_connect_by_path(n,','),',') p  ------ 所有三个坐标的组合，共C(6,3)=20
        from (select level n from dual connect by level<=6)
      where level=3
      connect by n>prior n
             and level<=3
)
connect by level<=3 and p=prior p and prior sys_guid() is not null
)
,bitmap as (  ---------- 所有3X3 的坐标，及其9个点的比特位之和构成的掩码，共400个掩码
select /*+ materialize */ x.p||y.p id
      ,sum(power(2,(x.n-1)*6+y.n-1)) as bit
  from n x,n y
group by x.p,y.p
)      
select count(all_rows) from r6
where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
;

COUNT(ALL_ROWS)
---------------
          16200

已用时间:  00: 01: 03.87

〇〇

如果有重复行，
如果重复的是每行2球，就能划两列去掉两行4个球，剩下6个球必定是一行2，2,1,1个球，再划两行去掉4个，还剩两球，一横一竖全划掉了。
如果重复的是每行1球，就能划1列去掉两行2个球，剩下8个球必定是一行2，2,2,2个球，再划3行去掉6个，还剩两球，2竖全划掉了。

〇〇

〇〇 发表于 2021-10-19 13:40
如果有重复行，如果重复的是每行2球，就能划两列去掉两行4个球，剩下6个球必定是一行2，2,1,1个球，再划两 ...

实际上，行与行是可以互换的，是否找出6个不同行的组合，然后再全排列都是解？

〇〇

2球c(6,2)=15
1球c(6,1)=6
从15中取4，第1个任意取，后续数字比前一个大，还要保证每列最多2个
从6取2，第1个任意取，后续数字比前一个大，还要保证每列最多2个
然后检查一下

〇〇

〇〇 发表于 2021-10-19 13:57
实际上，行与行是可以互换的，是否找出6个不同行的组合，然后再全排列都是解？

继续用newkid的改
--先求组合，再全排列
WITH
-------- 先把10个棋子放置在6X6，使得每行每列不超过两个（满足尽量均分的思路）
c as (select power(2,level-1) b,power(10,level-1) d from dual connect by level<=6) --- 1~6 位比特
,r as (select c1.b+c2.b b -------- 所有每行两个棋子的位置组合
      ,c1.d+c2.d d
      ,2 as cnt
  from c c1,c c2
where c1.b<c2.b
union all
select b,d,1 from c  -------- 加上每行一个棋子的位置
)
----- 递归三行的结果
,r2 (row_cnt    -- 当前行数
       ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
       ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
       ,b
       ,cnt
       )
AS (
   SELECT 1,lpad(d,6,'0'),d,b,cnt
     FROM r
   UNION ALL
   SELECT r2.row_cnt+1  ---- 行数递增
         ,r2.all_rows||lpad(r.d,6,'0')  ---当前行拼入总结果
         ,r2.col_cnt+r.d    --- 在列方向各位进行累加
         ,r2.b*power(2,6)+r.b
         ,r2.cnt+r.cnt
     FROM r2,r
    WHERE r2.row_cnt<6 ---- 递归出口
          AND INSTR(r2.col_cnt+r.d,3)=0 ---- 把带M+1的结果拦截掉
          and r2.cnt+r.cnt<=10
          and lpad(r.d,6,'0')>substr(r2.all_rows,-6) --后拼的都更大
)
,r6 as (select * from r2 where row_cnt=6 and cnt=10 and not regexp_like(col_cnt,'3|4|5|6'))  -------- 6X6的结果
-----------下面构造所有3X3 的BITAND掩码。一个满足条件的答案在BITAND之后都不为零，即每个3X3里面至少有一个棋子
,n as (
select p,substr(p,level,1) n   ------- 再把三个坐标拆成三行
from (
      select replace(sys_connect_by_path(n,','),',') p  ------ 所有三个坐标的组合，共C(6,3)=20
        from (select level n from dual connect by level<=6)
      where level=3
      connect by n>prior n
             and level<=3
)
connect by level<=3 and p=prior p and prior sys_guid() is not null
)
,bitmap as (  ---------- 所有3X3 的坐标，及其9个点的比特位之和构成的掩码，共400个掩码
select /*+ materialize */ x.p||y.p id
      ,sum(power(2,(x.n-1)*6+y.n-1)) as bit
  from n x,n y
group by x.p,y.p
)      
select count(*) from r6
where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
;

  COUNT(*)
----------
        45

已用时间:  00: 00: 00.53

45 *6！=32400

〇〇

还原结果
create table chess2 as
WITH
-------- 先把10个棋子放置在6X6，使得每行每列不超过两个（满足尽量均分的思路）
c as (select power(2,level-1) b,power(10,level-1) d from dual connect by level<=6) --- 1~6 位比特
,r as (select c1.b+c2.b b -------- 所有每行两个棋子的位置组合
      ,c1.d+c2.d d
      ,2 as cnt
  from c c1,c c2
where c1.b<c2.b
union all
select b,d,1 from c  -------- 加上每行一个棋子的位置
)
----- 递归三行的结果
,r2 (row_cnt    -- 当前行数
       ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
       ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
       ,b
       ,cnt
       )
AS (
   SELECT 1,lpad(d,6,'0'),d,b,cnt
     FROM r
   UNION ALL
   SELECT r2.row_cnt+1  ---- 行数递增
         ,r2.all_rows||lpad(r.d,6,'0')  ---当前行拼入总结果
         ,r2.col_cnt+r.d    --- 在列方向各位进行累加
         ,r2.b*power(2,6)+r.b
         ,r2.cnt+r.cnt
     FROM r2,r
    WHERE r2.row_cnt<6 ---- 递归出口
          AND INSTR(r2.col_cnt+r.d,3)=0 ---- 把带M+1的结果拦截掉
          and r2.cnt+r.cnt<=10
          and lpad(r.d,6,'0')>substr(r2.all_rows,-6) --后拼的都更大
)
,r6 as (select * from r2 where row_cnt=6 and cnt=10 and not regexp_like(col_cnt,'3|4|5|6'))  -------- 6X6的结果
-----------下面构造所有3X3 的BITAND掩码。一个满足条件的答案在BITAND之后都不为零，即每个3X3里面至少有一个棋子
,n as (
select p,substr(p,level,1) n   ------- 再把三个坐标拆成三行
from (
      select replace(sys_connect_by_path(n,','),',') p  ------ 所有三个坐标的组合，共C(6,3)=20
        from (select level n from dual connect by level<=6)
      where level=3
      connect by n>prior n
             and level<=3
)
connect by level<=3 and p=prior p and prior sys_guid() is not null
)
,bitmap as (  ---------- 所有3X3 的坐标，及其9个点的比特位之和构成的掩码，共400个掩码
select /*+ materialize */ x.p||y.p id
      ,sum(power(2,(x.n-1)*6+y.n-1)) as bit
  from n x,n y
group by x.p,y.p
)      
,
j as(
select rownum rn, all_rows from r6
where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
)
,
n1(n) as (select level n from dual connect by level<=6)
,
k(lv,s) as(
select 1,cast(n as varchar(10)) from n1
union all
select lv+1,s||n from k,n1 where lv<6 and instr(s,n)=0
)
,k1 as (select rownum rn,s from k where lv=6)
select substr(all_rows,substr(s,6,1)*6-5,6) --还原出全部排列
||substr(all_rows,substr(s,1,1)*6-5,6)
||substr(all_rows,substr(s,2,1)*6-5,6)
||substr(all_rows,substr(s,3,1)*6-5,6)
||substr(all_rows,substr(s,4,1)*6-5,6)
||substr(all_rows,substr(s,5,1)*6-5,6) as all_rows
from j,k1;

表已创建。

已用时间:  00: 00: 00.84

SQL> select count(*) from chess2;

  COUNT(*)
----------
     32400

和newkid的正确结果chess比较
SQL> select count(*) from(select * from chess minus select * from chess2);

  COUNT(*)
----------
         0

SQL> select count(*) from(select * from chess intersect select * from chess2);

  COUNT(*)
----------
     32400

solomon_007

OO优化无止境

〇〇

最后复原的代码难看，你用connect by 写一个？