puzzleup 2021

solomon_007

--6*6+2    278s
with 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),
     s(lvl,n,
     --nlist,
     clist) as (select 1,
                               n,
                               --cast(n as varchar2(100)),
                               c
                          from t
                         union all
                        select lvl + 1,
                               b.n,
                               --nlist||','||b.n,
                               clist||','||b.c
                          from s,t b
                         where s.n < b.n                          
                           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 instr(clist||','||b.c,a.c)>0)<=2            
                            )
select max(lvl) from s
--
12

〇〇

6 6 2就是第一次sql大赛第二题中的例子

http://www.itpub.net/thread-1403356-1-1.html

〇〇

每行最多2个时，最好结果就是每行都2个，因此前几行可以加b. n的限制条件为lv1和2在1-6之间，3和4在6-12之间

〇〇

由于图形的对称性，lv1在1-3之间

〇〇

加了以上约束条件6 6 2用时5秒

〇〇

663 用时2分30，应该还能剪枝

〇〇

772用时2分钟
882转出不来

newkid

8,8,3 答案是24。把SQL大赛的写法改一下，大胆假设24的摆法存在，再去小心求证，就可以跑出来了。

solomon_007

--6*6 + 2
SQL> set timing on
SQL>
SQL> with 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),
  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 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 ) <=2
24                                     and case when lvl+1=2 and b.n between 1 and 6 then 1
25                                              when lvl+1 in (3,4)   and b.n between 7  and 12 then 1
26                                              when lvl+1 in (5,6)   and b.n between 13 and 18 then 1
27                                              when lvl+1 in (7,8)   and b.n between 19 and 24 then 1
28                                              when lvl+1 in (9,10)  and b.n between 25 and 30 then 1
29                                              when lvl+1 in (11,12) and b.n between 31 and 36 then 1
30                                              else 0
31                                         end = 1
32                              )
33  select max(lvl) from s
34  /

  MAX(LVL)
----------
        12

Executed in 1.829 seconds




--7*7 + 2
SQL> set timing on;
SQL>
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 4
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 ) <=2
24                                     and case when lvl+1=2          and b.n between 1  and 7  then 1
25                                              when lvl+1 in (3,4)   and b.n between 8  and 14 then 1
26                                              when lvl+1 in (5,6)   and b.n between 15 and 21 then 1
27                                              when lvl+1 in (7,8)   and b.n between 22 and 28 then 1
28                                              when lvl+1 in (9,10)  and b.n between 29 and 35 then 1
29                                              when lvl+1 in (11,12) and b.n between 36 and 42 then 1
30                                              when lvl+1 in (13,14) and b.n between 43 and 49 then 1
31                                              else 0
32                                         end = 1
33                              )
34  select max(lvl) from s
35  /

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

Executed in 59.74 seconds

solomon_007

--8*8 + 2

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 4
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 ) <=2
24                                     and case when lvl+1=2          and b.n between 1  and 8  then 1
25                                              when lvl+1 in (3,4)   and b.n between 9  and 16 then 1
26                                              when lvl+1 in (5,6)   and b.n between 17 and 24 then 1
27                                              when lvl+1 in (7,8)   and b.n between 25 and 32 then 1
28                                              when lvl+1 in (9,10)  and b.n between 33 and 40 then 1
29                                              when lvl+1 in (11,12) and b.n between 41 and 48 then 1
30                                              when lvl+1 in (13,14) and b.n between 49 and 56 then 1
31                                              when lvl+1 in (15,16) and b.n between 57 and 64 then 1
32                                              else 0
33                                         end = 1
34                              )
35  select max(lvl) from s
36  /

  MAX(LVL)
----------
        16

Executed in 2172.525 seconds