出个SQL题：4皇后问题（新增马步问题在第7页）

yellowlee

每个表才49行，怎么整也是很块的应该，具体没有写，哪位兄弟有空可以帮忙写下

rollingpig

Tuning一下，用单句SQL也可以很快,2sec多点

1. 
   
2. with chess -- 棋盘，X/Y为横竖轴，Z1/Z2为对角线，N为方便访问的值
   
3. as (select x.l as x,y.l as y,x.l+y.l as z1,x.l-y.l as z2,x.l||'#'||y.l as n
   
4. from (select level-1 l from dual connect by level <=7) x,
   
5. (select level-1 l from dual connect by level <=7)y ),
   
6. chess_4queen as -- 4个Queen的放置位置
   
7. (select  /*+ materialize */
   
8. q1.n as q1n,q2.n as q2n, q3.n as q3n, q4.n as q4n
   
9. from chess q1, chess q2, chess q3, chess q4
   
10. where
    
11. q1.x < q2.x and q2.x < q3.x and q3.x < q4.x --避免重复  
    
12. and q1.y != q2.y and q1.y != q3.y and q1.y != q4.y  
    
13. and q2.y != q3.y and q2.y != q4.y and q3.y != q4.y
    
14. and q1.z1 != q2.z1 and q1.z1 != q3.z1 and q1.z1 != q4.z1  
    
15. and q2.z1 != q3.z1 and q2.z1 != q4.z1 and q3.z1 != q4.z1
    
16. and q1.z2 != q2.z2 and q1.z2 != q3.z2 and q1.z2 != q4.z2
    
17. and q2.z2 != q3.z2 and q2.z2 != q4.z2 and q3.z2 != q4.z2
    
18. ),
    
19. chess_attack as -- Queen 的攻击范围 ，不包括自身
    
20. (select  /*+ materialize */
    
21. a.n,b.n as kn
    
22. from chess a, chess b
    
23. where (a.x=b.x or a.y=b.y or a.z1=b.z1 or a.z2=b.z2)
    
24. and a.n!=b.n
    
25. )  
    
26. select /*+ use_hash(chess_attack chess_4queen) ordered use_concat*/ j.*,count(distinct kn) --计算不重复的攻击格数
    
27.                   from chess_attack ,  chess_4queen j
    
28.                  where
    
29.                  n in (j.q1n,j.q2n,j.q3n,j.q4n)
    
30. group by  q1n,q2n,q3n,q4n
    
31. having count(distinct kn) = 45    --全覆盖 ， 去掉自己，45=7*7 - 4
    
32. 
    

复制代码

yellowlee

原帖由 rollingpig 于 2010-8-18 16:16 发表
Tuning一下，用单句SQL也可以很快,2sec多点

with chess -- 棋盘，X/Y为横竖轴，Z1/Z2为对角线，N为方便访问的值
as (select x.l as x,y.l as y,x.l+y.l as z1,x.l-y.l as z2,x.l||'#'||y.l as n
from (select level-1 l from dual connect by level  

   学习了，说起来简单，写起来还是费时间的，用坐标好，用标号不行，关联起来会很麻烦，多谢rollingpig大哥

yellowlee

写了个，10828个排列，眼高手低了，写的比较傻，高手们帮看看，不晓得对不对，晚上再来看看

with temp as (
select level node,
       trunc((level+6)/7) -1 row_num,
       mod(level+6,7) col_num,
       case when mod(level,7) >0 then  mod(level+6,7)+trunc(level/7)
            when mod(level,7) = 0 then mod(level+6,7)+trunc(level/7 -1)
       end a_num,
       level -8*(trunc((level+6)/7) -1) + 18  b_num
                     
from dual connect by level <= 49
)
select a.node, b.node, c.node, d.node
   from temp a, temp b, temp c, temp d
  where a.node < b.node
    and b.node < c.node
    and c.node < d.node
    and not (
         a.row_num = b.row_num or b.row_num = c.row_num or c.row_num = d.row_num
         or a.row_num = c.row_num or a.row_num = d.row_num  
         or a.col_num = b.col_num or b.col_num = c.col_num or c.col_num = d.col_num
         or a.col_num = c.col_num or a.col_num = d.col_num
         or a.a_num = b.a_num or b.a_num = c.a_num or c.a_num = d.a_num
         or a.a_num = c.a_num or a.a_num = d.a_num  
         or a.b_num = b.b_num or b.b_num = c.b_num or c.b_num = d.b_num
         or a.b_num = c.b_num or a.b_num = d.b_num
         )
;

lastwinner

原帖由 6666444 于 10-8-18 15:22 发表
呵，那个我贴上来就发现错了，后面改了
不过版主不能加q1.x

事实上，最终结果应该就1个

上下对称、左右对称，可以刨除一批重复的（其实就是镜像）
正方形旋转90度、180度、270度后，本质上都是同一个正方形，但表现出来的坐标又都不一样，这又可以刨除一批重复的（这里采用的是旋转策略）

你的结果：
       NUM         P1         P2         P3         P4        CNT
---------- ---------- ---------- ---------- ---------- ----------
   1122132          1         12         21         32         49
   3073236          3          7         32         36         49
   3133040          3         13         30         40         49
   5082730          5          8         27         30         49
   8183545          8         18         35         45         49
  12164145         12         16         41         45         49
  16273647         16         27         36         47         49
  18214043         18         21         40         43         49

以第一条数据为例，在下面的图中为图1


经过水平镜像后，得图2 （对应你的第八条数据）
经过垂直镜像后，得图4 （对应你的第四条数据）
经过水平镜像后再垂直镜像，得图3 （对应你的第七条数据）



下面是旋转后的效果，图1仍然是第一条数据


顺时针旋转90度，得图2 （对应你的第三条数据）
顺时针旋转180度，得图3 （对应你的第七条数据，与上面的图3完全一样）
顺时针旋转270度，得图4 （对应你的第五条数据）


将旋转和镜像结合起来（等价于对角线对称了），图1仍然是第一条数据

水平镜像后，顺时针旋转90度，得图2（对应你的第二条数据）
水平镜像后，顺时针旋转270度，得图3（对应你的第六条数据）



滚珠版主要是再加上第二个皇后只能在右上角4×3的方格内，第三个皇后只能在左下角3×4的方格内，第四个皇后只能在右下角3×4的方格内，那最终他的sql应该就只能求出
第一张图中的图2和图3、第二张图中的图2及第三张图中的图3，总共4个结果了

〇〇

nice 野花

newkid

滚猪大师的猪肉优化器实在是犀利！

我为了判断全覆盖，用的是位操作方法。因为没有BITOR, 改用十进制的加法，幸亏没有进位问题，我只要判断该位是不是0就可以知道是否被覆盖到。

WITH c1 AS (
   SELECT ROWNUM id, MOD(ROWNUM-1,7)+1 x,CEIL(ROWNUM/7) y FROM DUAL CONNECT BY ROWNUM<=49
   )
  ,c2 AS (
   SELECT c1.id,c1.x,c1.y
         ,REPLACE(SYS_CONNECT_BY_PATH(CASE WHEN c1.x=c2.x OR c1.y = c2.y
                                                OR c1.x-c2.x IN (c1.y-c2.y,c2.y-c1.y)
                                           THEN '1'
                                           ELSE '0'
                                      END,',')
                 ,',') cover
     FROM c1, c1 c2
    WHERE level=49
    START WITH c2.id=1
   CONNECT BY c1.id = PRIOR c1.id AND c2.id = PRIOR c2.id+1
   )
  ,cells AS (
   SELECT c2.*,SUBSTR(cover,1,25) v1,SUBSTR(cover,26) v2
     FROM c2
  )
SELECT c1.x||c1.y||'-'||c2.x||c2.y||'-'||c3.x||c3.y||'-'||c4.x||c4.y AS result
  FROM cells c1,cells c2, cells c3, cells c4
WHERE c1.x BETWEEN 1 AND 4
       AND c1.y BETWEEN 1 AND 4
       AND c1.x <= c1.y
       AND c1.id < c2.id AND c2.id < c3.id AND c3.id < c4.id
       AND SUBSTR(c1.cover,c2.id,1)='0'
       AND SUBSTR(c1.cover,c3.id,1)='0'
       AND SUBSTR(c1.cover,c4.id,1)='0'
       AND SUBSTR(c2.cover,c3.id,1)='0'
       AND SUBSTR(c2.cover,c4.id,1)='0'
       AND SUBSTR(c3.cover,c4.id,1)='0'
       AND INSTR(c1.v1+c2.v1+c3.v1+c4.v1,'0')=0
       AND c1.v1+c2.v1+c3.v1+c4.v1>1000000000000000000000000
       AND INSTR(c1.v2+c2.v2+c3.v2+c4.v2,'0')=0
       AND c1.v2+c2.v2+c3.v2+c4.v2>100000000000000000000000
;



RESULT
-----------------
22-53-16-47
33-74-26-67

这两个答案相当于滚猪的第5,7个答案。我为了排除对称限定第一点在1/8的角落中。

其他答案有待赏析。

yellowlee

皇后不能随便摆的？有位置限制么？那我搞错鸟。

newkid

原帖由 yellowlee 于 2010-8-18 22:03 发表
皇后不能随便摆的？有位置限制么？那我搞错鸟。

没有限制，我是为了去除一些对称答案才限制第一点的坐标。

newkid

原帖由 yellowlee 于 2010-8-18 17:44 发表
写了个，10828个排列，眼高手低了，写的比较傻，高手们帮看看，不晓得对不对，晚上再来看看

with temp as (
select level node,
       trunc((level+6)/7) -1 row_num,
       mod(level+6,7) col_num,
       case when mod(level,7) >0 then  mod(level+6,7)+trunc(level/7)
            when mod(level,7) = 0 then mod(level+6,7)+trunc(level/7 -1)
       end a_num,
       level -8*(trunc((level+6)/7) -1) + 18  b_num
                     
from dual connect by level  

你这个摆法只是避免了相互攻击，没有覆盖整个棋盘的条件。