puzzleup 2021

solomon_007

太多了，40分钟 找了 23000多个解

solomon_007

32400 个解，58分钟

solomon_007

SQL> set timing on;
SQL>
SQL> set pagesize 1000;
SQL>
SQL>
SQL>   with
  2      function f_check (p_nlist in varchar2)
  3    return int
  4    is
  5      type r_rec is record( n int,
  6                            x int,
  7                            y int);
  8  
  9      type t_rec is table of r_rec index by pls_integer;
10      l_rec t_rec;
11      l_tmp t_rec;
12  
13      l_cnt   int := 0;
14      l_t_cnt int := -1;
15  
16    begin
17  
18      select n,
19             ceil(n/6),
20             mod(n-1,6)+1
21        bulk collect into l_rec
22        from (
23              select regexp_substr(p_nlist,'[^,]+',1,level) n
24                from dual
25               connect by level <= regexp_count(p_nlist,',')+1
26             );
27  
28       for rec in ( with t as (
29                              select substr(sys_connect_by_path(n,','),2) rc
30                                from (select level n from dual connect by level<=6)
31                               where level = 3
32                              connect by prior n < n
33                              )
34                              select a.rc x_rc,b.rc y_rc
35                                from t a,t b   ) loop
36  
37         l_tmp := l_rec;
38  
39         for i in l_tmp.first..l_tmp.last loop
40           if l_tmp.exists(i)=TRUE and instr(rec.x_rc,l_tmp(i).x) > 0 then
41             l_tmp.delete(i);
42           end if;
43         end loop;
44  
45         for i in l_tmp.first..l_tmp.last loop
46           if l_tmp.exists(i)=TRUE and instr(rec.y_rc,l_tmp(i).y) > 0 then
47             l_tmp.delete(i);
48           end if;
49         end loop;
50  
51         if l_tmp.count > 0 then
52           l_cnt := l_cnt + 1;
53         else
54           return 0;
55         end if;
56  
57       end loop;
58  
59       select count(*)
60         into l_t_cnt
61         from (
62           with t as (
63                      select substr(sys_connect_by_path(n,','),2) rc
64                        from (select level n from dual connect by level<=6)
65                       where level = 3
66                      connect by prior n < n
67                      )
68                      select a.rc x_rc,b.rc y_rc
69                        from t a,t b
70         );
71  
72       if l_cnt=l_t_cnt then
73         return 1;
74       else
75         return 0;
76       end if;
77  
78    end;
79     t(n,c,x,y) as (select level,chr(64+level),ceil(level/6),mod(level-1,6)+1 from dual connect by level<=6*6),
80     s(lvl,n,nlist,clist) as (select 1, n,cast(n as varchar2(100)),c
81                                   from t
82                                  where t.n between 1 and 6
83                                union all
84                               select lvl + 1,
85                                      b.n,
86                                      nlist||','||b.n,
87                                      clist||','||b.c
88                                 from s,t b
89                                where s.n < b.n
90                                  and (select greatest(sum(case when a.x = b.x then 1 end),
91                                                       sum(case when a.y = b.y then 1 end)
92                                                       )
93                                         from t a
94                                        where instr(clist||','||b.c,a.c)>0
95                                       ) <= 2
96                                  and lvl < 10
97                                  and b.n between (ceil((lvl+1)/2)-1)*6 + 1 and (ceil((lvl+1)/2)-1)*6 + 6*2
98                    )
99    select nlist from s where lvl = 10 and f_check(nlist)=1 and rownum <= 100
100  /

NLIST
--------------------------------------------------------------------------------
1,2,7,9,14,16,21,22,29,36
1,2,7,9,14,16,21,22,30,35
1,2,7,9,14,16,23,27,28,36
1,2,7,9,14,16,23,30,33,34
1,2,7,9,14,16,24,27,28,35
1,2,7,9,14,16,24,29,33,34
1,2,7,9,14,17,21,23,28,36
1,2,7,9,14,17,21,23,30,34
1,2,7,9,14,17,22,27,29,36
1,2,7,9,14,17,22,30,33,35
1,2,7,9,14,17,24,27,29,34
1,2,7,9,14,17,24,28,33,35
1,2,7,9,14,18,21,24,28,35
1,2,7,9,14,18,21,24,29,34
1,2,7,9,14,18,22,27,30,35
1,2,7,9,14,18,22,29,33,36
1,2,7,9,14,18,23,27,30,34
1,2,7,9,14,18,23,28,33,36
1,2,7,9,15,16,20,22,29,36
1,2,7,9,15,16,20,22,30,35
1,2,7,9,15,16,23,26,28,36
1,2,7,9,15,16,23,30,32,34
1,2,7,9,15,16,24,26,28,35
1,2,7,9,15,16,24,29,32,34
1,2,7,9,15,17,20,23,28,36
1,2,7,9,15,17,20,23,30,34
1,2,7,9,15,17,22,26,29,36
1,2,7,9,15,17,22,30,32,35
1,2,7,9,15,17,24,26,29,34
1,2,7,9,15,17,24,28,32,35
1,2,7,9,15,18,20,24,28,35
1,2,7,9,15,18,20,24,29,34
1,2,7,9,15,18,22,26,30,35
1,2,7,9,15,18,22,29,32,36
1,2,7,9,15,18,23,26,30,34
1,2,7,9,15,18,23,28,32,36
1,2,7,9,16,20,23,27,29,36
1,2,7,9,16,20,23,30,33,35
1,2,7,9,16,20,24,27,30,35
1,2,7,9,16,20,24,29,33,36
1,2,7,9,16,21,23,26,29,36
1,2,7,9,16,21,23,30,32,35
1,2,7,9,16,21,24,26,30,35
1,2,7,9,16,21,24,29,32,36
1,2,7,9,16,23,26,30,33,36
1,2,7,9,16,23,27,30,32,36
1,2,7,9,16,24,26,29,33,35
1,2,7,9,16,24,27,29,32,35
1,2,7,9,17,20,22,27,28,36
1,2,7,9,17,20,22,30,33,34
1,2,7,9,17,20,24,27,30,34
1,2,7,9,17,20,24,28,33,36
1,2,7,9,17,21,22,26,28,36
1,2,7,9,17,21,22,30,32,34
1,2,7,9,17,21,24,26,30,34
1,2,7,9,17,21,24,28,32,36
1,2,7,9,17,22,26,30,33,36
1,2,7,9,17,22,27,30,32,36
1,2,7,9,17,24,26,28,33,34
1,2,7,9,17,24,27,28,32,34
1,2,7,9,18,20,22,27,28,35
1,2,7,9,18,20,22,29,33,34
1,2,7,9,18,20,23,27,29,34
1,2,7,9,18,20,23,28,33,35
1,2,7,9,18,21,22,26,28,35
1,2,7,9,18,21,22,29,32,34
1,2,7,9,18,21,23,26,29,34
1,2,7,9,18,21,23,28,32,35
1,2,7,9,18,22,26,29,33,35
1,2,7,9,18,22,27,29,32,35
1,2,7,9,18,23,26,28,33,34
1,2,7,9,18,23,27,28,32,34
1,2,7,10,14,15,21,22,29,36
1,2,7,10,14,15,21,22,30,35
1,2,7,10,14,15,23,27,28,36
1,2,7,10,14,15,23,30,33,34
1,2,7,10,14,15,24,27,28,35
1,2,7,10,14,15,24,29,33,34
1,2,7,10,14,17,21,28,29,36
1,2,7,10,14,17,21,30,34,35
1,2,7,10,14,17,22,23,27,36
1,2,7,10,14,17,22,23,30,33
1,2,7,10,14,17,24,27,34,35
1,2,7,10,14,17,24,28,29,33
1,2,7,10,14,18,21,28,30,35
1,2,7,10,14,18,21,29,34,36
1,2,7,10,14,18,22,24,27,35
1,2,7,10,14,18,22,24,29,33
1,2,7,10,14,18,23,27,34,36
1,2,7,10,14,18,23,28,30,33
1,2,7,10,15,16,20,21,29,36
1,2,7,10,15,16,20,21,30,35
1,2,7,10,15,16,23,26,27,36
1,2,7,10,15,16,23,30,32,33
1,2,7,10,15,16,24,26,27,35
1,2,7,10,15,16,24,29,32,33
1,2,7,10,15,20,23,28,29,36
1,2,7,10,15,20,23,30,34,35
1,2,7,10,15,20,24,28,30,35
1,2,7,10,15,20,24,29,34,36

100 rows selected


Executed in 112.685 seconds

solomon_007

测试一下吞不吞

solomon_007

用了一个函数判断。

SQL> set timing on;
SQL>
SQL> set pagesize 1000;
SQL>
SQL>
SQL>   with
  2      function f_check (p_nlist in varchar2)
  3    return int
  4    is
  5      type r_rec is record( n int,
  6                            x int,
  7                            y int);
  8  
  9      type t_rec is table of r_rec index by pls_integer;
10      l_rec t_rec;
11      l_tmp t_rec;
12  
13      l_cnt   int := 0;
14      l_t_cnt int := -1;
15  
16    begin
17  
18      select n,
19             ceil(n/6),
20             mod(n-1,6)+1
21        bulk collect into l_rec
22        from (
23              select regexp_substr(p_nlist,'[^,]+',1,level) n
24                from dual
25               connect by level <= regexp_count(p_nlist,',')+1
26             );
27  
28       for rec in ( with t as (
29                              select substr(sys_connect_by_path(n,','),2) rc
30                                from (select level n from dual connect by level<=6)
31                               where level = 3
32                              connect by prior n < n
33                              )
34                              select a.rc x_rc,b.rc y_rc
35                                from t a,t b   ) loop
36  
37         l_tmp := l_rec;
38  
39         for i in l_tmp.first..l_tmp.last loop
40           if l_tmp.exists(i)=TRUE and instr(rec.x_rc,l_tmp(i).x) > 0 then
41             l_tmp.delete(i);
42           end if;
43         end loop;
44  
45         for i in l_tmp.first..l_tmp.last loop
46           if l_tmp.exists(i)=TRUE and instr(rec.y_rc,l_tmp(i).y) > 0 then
47             l_tmp.delete(i);
48           end if;
49         end loop;
50  
51         if l_tmp.count > 0 then
52           l_cnt := l_cnt + 1;
53         else
54           return 0;
55         end if;
56  
57       end loop;
58  
59       select count(*)
60         into l_t_cnt
61         from (
62           with t as (
63                      select substr(sys_connect_by_path(n,','),2) rc
64                        from (select level n from dual connect by level<=6)
65                       where level = 3
66                      connect by prior n < n
67                      )
68                      select a.rc x_rc,b.rc y_rc
69                        from t a,t b
70         );
71  
72       if l_cnt=l_t_cnt then
73         return 1;
74       else
75         return 0;
76       end if;
77  
78    end;
79     t(n,c,x,y) as (select level,chr(64+level),ceil(level/6),mod(level-1,6)+1 from dual connect by level<=6*6),
80     s(lvl,n,nlist,clist) as (select 1, n,cast(n as varchar2(100)),c
81                                   from t
82                                  where t.n between 1 and 6
83                                union all
84                               select lvl + 1,
85                                      b.n,
86                                      nlist||','||b.n,
87                                      clist||','||b.c
88                                 from s,t b
89                                where s.n < b.n
90                                  and (select greatest(sum(case when a.x = b.x then 1 end),
91                                                       sum(case when a.y = b.y then 1 end)
92                                                       )
93                                         from t a
94                                        where instr(clist||','||b.c,a.c)>0
95                                       ) <= 2
96                                  and lvl < 10
97                                  and b.n between (ceil((lvl+1)/2)-1)*6 + 1 and (ceil((lvl+1)/2)-1)*6 + 6*2
98                    )
99    select nlist from s where lvl = 10 and f_check(nlist)=1 and rownum <= 100
100  /

NLIST
--------------------------------------------------------------------------------
1,2,7,9,14,16,21,22,29,36
1,2,7,9,14,16,21,22,30,35
1,2,7,9,14,16,23,27,28,36
1,2,7,9,14,16,23,30,33,34
1,2,7,9,14,16,24,27,28,35
1,2,7,9,14,16,24,29,33,34
1,2,7,9,14,17,21,23,28,36
1,2,7,9,14,17,21,23,30,34
1,2,7,9,14,17,22,27,29,36
1,2,7,9,14,17,22,30,33,35
1,2,7,9,14,17,24,27,29,34
1,2,7,9,14,17,24,28,33,35
1,2,7,9,14,18,21,24,28,35
1,2,7,9,14,18,21,24,29,34
1,2,7,9,14,18,22,27,30,35
1,2,7,9,14,18,22,29,33,36
1,2,7,9,14,18,23,27,30,34
1,2,7,9,14,18,23,28,33,36
1,2,7,9,15,16,20,22,29,36
1,2,7,9,15,16,20,22,30,35
1,2,7,9,15,16,23,26,28,36
1,2,7,9,15,16,23,30,32,34
1,2,7,9,15,16,24,26,28,35
1,2,7,9,15,16,24,29,32,34
1,2,7,9,15,17,20,23,28,36
1,2,7,9,15,17,20,23,30,34
1,2,7,9,15,17,22,26,29,36
1,2,7,9,15,17,22,30,32,35
1,2,7,9,15,17,24,26,29,34
1,2,7,9,15,17,24,28,32,35
1,2,7,9,15,18,20,24,28,35
1,2,7,9,15,18,20,24,29,34
1,2,7,9,15,18,22,26,30,35
1,2,7,9,15,18,22,29,32,36
1,2,7,9,15,18,23,26,30,34
1,2,7,9,15,18,23,28,32,36
1,2,7,9,16,20,23,27,29,36
1,2,7,9,16,20,23,30,33,35
1,2,7,9,16,20,24,27,30,35
1,2,7,9,16,20,24,29,33,36
1,2,7,9,16,21,23,26,29,36
1,2,7,9,16,21,23,30,32,35
1,2,7,9,16,21,24,26,30,35
1,2,7,9,16,21,24,29,32,36
1,2,7,9,16,23,26,30,33,36
1,2,7,9,16,23,27,30,32,36
1,2,7,9,16,24,26,29,33,35
1,2,7,9,16,24,27,29,32,35
1,2,7,9,17,20,22,27,28,36
1,2,7,9,17,20,22,30,33,34
1,2,7,9,17,20,24,27,30,34
1,2,7,9,17,20,24,28,33,36
1,2,7,9,17,21,22,26,28,36
1,2,7,9,17,21,22,30,32,34
1,2,7,9,17,21,24,26,30,34
1,2,7,9,17,21,24,28,32,36
1,2,7,9,17,22,26,30,33,36
1,2,7,9,17,22,27,30,32,36
1,2,7,9,17,24,26,28,33,34
1,2,7,9,17,24,27,28,32,34
1,2,7,9,18,20,22,27,28,35
1,2,7,9,18,20,22,29,33,34
1,2,7,9,18,20,23,27,29,34
1,2,7,9,18,20,23,28,33,35
1,2,7,9,18,21,22,26,28,35
1,2,7,9,18,21,22,29,32,34
1,2,7,9,18,21,23,26,29,34
1,2,7,9,18,21,23,28,32,35
1,2,7,9,18,22,26,29,33,35
1,2,7,9,18,22,27,29,32,35
1,2,7,9,18,23,26,28,33,34
1,2,7,9,18,23,27,28,32,34
1,2,7,10,14,15,21,22,29,36
1,2,7,10,14,15,21,22,30,35
1,2,7,10,14,15,23,27,28,36
1,2,7,10,14,15,23,30,33,34
1,2,7,10,14,15,24,27,28,35
1,2,7,10,14,15,24,29,33,34
1,2,7,10,14,17,21,28,29,36
1,2,7,10,14,17,21,30,34,35
1,2,7,10,14,17,22,23,27,36
1,2,7,10,14,17,22,23,30,33
1,2,7,10,14,17,24,27,34,35
1,2,7,10,14,17,24,28,29,33
1,2,7,10,14,18,21,28,30,35
1,2,7,10,14,18,21,29,34,36
1,2,7,10,14,18,22,24,27,35
1,2,7,10,14,18,22,24,29,33
1,2,7,10,14,18,23,27,34,36
1,2,7,10,14,18,23,28,30,33
1,2,7,10,15,16,20,21,29,36
1,2,7,10,15,16,20,21,30,35
1,2,7,10,15,16,23,26,27,36
1,2,7,10,15,16,23,30,32,33
1,2,7,10,15,16,24,26,27,35
1,2,7,10,15,16,24,29,32,33
1,2,7,10,15,20,23,28,29,36
1,2,7,10,15,20,23,30,34,35
1,2,7,10,15,20,24,28,30,35
1,2,7,10,15,20,24,29,34,36

100 rows selected


Executed in 112.685 seconds

solomon_007

一个多小时，全部大约 34000个解

〇〇

加注释看看

〇〇

感觉用二进制位判断会简单一点

〇〇

点阵在x轴和y轴上的投影都多于3个点就行

newkid

给猫猫转了个章。

答案至少为十。反证法：
假设九能满足。
划走三行之后，剩下的棋子如果不超过三个，则不满足条件。因为最多分布于三个列，把这三列拿走就空了。
从行的维度来看，棋子必须尽量均分。否则，含棋子多的行被取走，剩下的棋子可能就不够。
九个棋子尽可能均分于六行，最多只有三行能够两个棋子，其他三行一个棋子。
把含有两个棋子的三行拿走之后，只剩下三个棋子。
所以，当N=9, 必定存在三行，使得这三行拿走之后剩下不多于三个棋子。所以N=9不满足题目条件。

我的写法：
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
)
,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 not regexp_like(r31.col_cnt+r32.col_cnt,'3|4')  -------- 每列不超过两个
      and r31.cnt+r32.cnt=10  ------- 总数十个棋子
)
-----------下面构造所有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 all_rows from r6
where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
and rownum=1
;

找出第一个很快：
ALL_ROWS
---------------------------------------
000011000**00**0001100010000100000

Elapsed: 00:00:00.20

找出全部：
  COUNT(*)
----------
     32400

Elapsed: 00:01:30.38