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

seraphin

算法题用sql！？？！

6666444

失误失误...居然漏了个abs
with t as
(select level-1 l from dual connect by level <=49),
t1 as
(select *
  from (select a.l l, b.l cl from t a, t b)
where trunc(l / 7) = trunc(cl / 7)
    or mod(l, 7) = mod(cl, 7)
    or abs((trunc(l / 7) - trunc(cl / 7))) = abs((mod(l, 7) - mod(cl, 7)))),
t2 as
(select a.l*1e6+b.l*1e4+c.l*1e2+d.l num from t a,t b,t c,t d
  where a.l<b.l and b.l<c.l and c.l<d.l
  and trunc(a.l/7)<>trunc(b.l/7)
  and trunc(a.l/7)<>trunc(c.l/7)
  and trunc(a.l/7)<>trunc(d.l/7)
  and trunc(b.l/7)<>trunc(c.l/7)
  and trunc(b.l/7)<>trunc(d.l/7)
  and trunc(c.l/7)<>trunc(d.l/7)
  and mod(a.l,7)<>mod(b.l,7)
  and mod(a.l,7)<>mod(c.l,7)
  and mod(a.l,7)<>mod(d.l,7)
  and mod(b.l,7)<>mod(c.l,7)
  and mod(b.l,7)<>mod(d.l,7)
  and mod(c.l,7)<>mod(d.l,7))
select *
  from (select num,
               trunc(mod(num, 1e8) / 1e6) p1,
               trunc(mod(num, 1e6) / 1e4) p2,
               trunc(mod(num, 1e4) / 1e2) p3,
               trunc(mod(num, 1e2)) p4,
               (select count(distinct cl)
                  from t1
                 where l in
                       (trunc(mod(num, 1e8) / 1e6), trunc(mod(num, 1e6) / 1e4),
                        trunc(mod(num, 1e4) / 1e2), trunc(mod(num, 1e2)))) cnt
          from t2)
where cnt = 49

6666444

晕死，结果是错的....

[ 本帖最后由 6666444 于 2010-8-18 13:31 编辑 ]

6666444

SQL> with t as
  2  (select level-1 l from dual connect by level <=49),
  3  t1 as
  4  (select *
  5    from (select a.l l, b.l cl from t a, t b)
  6  where trunc(l / 7) = trunc(cl / 7)
  7      or mod(l, 7) = mod(cl, 7)
  8      or abs((trunc(l / 7) - trunc(cl / 7))) = abs((mod(l, 7) - mod(cl, 7)))),
  9  t2 as
10  (select a.l*1e6+b.l*1e4+c.l*1e2+d.l num from t a,t b,t c,t d
11    where a.l<b.l and b.l<c.l and c.l<d.l
12    and trunc(a.l/7)<>trunc(b.l/7)
13    and trunc(a.l/7)<>trunc(c.l/7)
14    and trunc(a.l/7)<>trunc(d.l/7)
15    and trunc(b.l/7)<>trunc(c.l/7)
16    and trunc(b.l/7)<>trunc(d.l/7)
17    and trunc(c.l/7)<>trunc(d.l/7)
18    and mod(a.l,7)<>mod(b.l,7)
19    and mod(a.l,7)<>mod(c.l,7)
20    and mod(a.l,7)<>mod(d.l,7)
21    and mod(b.l,7)<>mod(c.l,7)
22    and mod(b.l,7)<>mod(d.l,7)
23    and mod(c.l,7)<>mod(d.l,7)
24    and abs((trunc(a.l / 7) - trunc(b.l / 7))) <> abs((mod(a.l, 7) - mod(b.l, 7)))
25    and abs((trunc(a.l / 7) - trunc(c.l / 7))) <> abs((mod(a.l, 7) - mod(c.l, 7)))
26    and abs((trunc(a.l / 7) - trunc(d.l / 7))) <> abs((mod(a.l, 7) - mod(d.l, 7)))
27    and abs((trunc(b.l / 7) - trunc(c.l / 7))) <> abs((mod(b.l, 7) - mod(c.l, 7)))
28    and abs((trunc(b.l / 7) - trunc(d.l / 7))) <> abs((mod(b.l, 7) - mod(d.l, 7)))
29    and abs((trunc(c.l / 7) - trunc(d.l / 7))) <> abs((mod(c.l, 7) - mod(d.l, 7))))
30  select *
31    from (select num,
32                 trunc(mod(num, 1e8) / 1e6) p1,
33                 trunc(mod(num, 1e6) / 1e4) p2,
34                 trunc(mod(num, 1e4) / 1e2) p3,
35                 trunc(mod(num, 1e2)) p4,
36                 (select count(distinct cl)
37                    from t1
38                   where l in
39                         (trunc(mod(num, 1e8) / 1e6), trunc(mod(num, 1e6) / 1e4),
40                          trunc(mod(num, 1e4) / 1e2), trunc(mod(num, 1e2)))) cnt
41            from t2)
42  where cnt = 49
43  /

       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

8 rows selected.

Elapsed: 00:00:17.88

Statistics
----------------------------------------------------------
       3062  recursive calls
         11  db block gets
     119114  consistent gets
          1  physical reads
       1452  redo size
       1031  bytes sent via SQL*Net to client
        498  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
       7066  sorts (memory)
          0  sorts (disk)
          8  rows processed
总算出来了

风铃中の鬼

楼上的答案不对。。。用第一行的结果验证就差了2个格子没填满。。以防万一确定一下，第一行是4个皇后分别占在第1,12,21,32号格子里是吧

rollingpig

你的对角线的算法不对。

原帖由 6666444 于 2010-8-18 11:56 发表
你牛，剩下的就简单了
with t as
(select level-1 l from dual connect by level  

6666444

结果是对的，注意脚本，用的号数是0-48不是1-49是下面这种排列
0        1        2        3        4        5        6
7        8        9        10        11        12        13
14        15        16        17        18        19        20
21        22        23        24        25        26        27
28        29        30        31        32        33        34
35        36        37        38        39        40        41
42        43        44        45        46        47        48

6666444

错在什么地方？
我验证了下结果，是正确的啊

rollingpig

我写了一个比较直观的。没有mod/trunc/除法，更好理解。

with chess -- 棋盘，x横轴，y竖轴，Z1对角1，Z2对角2，n是为了更简便访问的
as ( select /*+ materialize  */
x.l as x,y.l as y,x.l+y.l as z1,x.l-y.l as z2,x.l+10*y.l as n
from (select level-1 l from dual connect by level <=7) x,
(select level-1 l from dual connect by level <=7)y ),
chess_attack as -- x,y,z Queen所在位置, kx,ky,kn Queen可以攻击到的位置，type 是攻击类型，x横轴，y竖轴，Z1对角1，Z2对角2
(select /*+ materialize  */
a.x,a.y,a.n, b.x kx,b.y ky,b.n as kn,'X' as type from chess a, chess b
where a.x=b.x
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as kn,'Y' as type from chess a, chess b
where a.y=b.y
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as kn,'Z1' as type from chess a, chess b
where     a.z1=b.z1
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as kn,'Z2' as type from chess a, chess b
where     a.z2=b.z2),
chess_4queen as -- 4个Queen的放置位置，分别是 Q#x,Q#y,Q#n
(select /*+ materialize  */
q1.x as q1x,q1.y as q1y,q1.n as q1n,
q2.x as q2x,q2.y as q2y,q2.n as q2n,
q3.x as q3x,q3.y as q3y,q3.n as q3n,
q4.x as q4x,q4.y as q4y,q4.n as q4n
from
chess q1,
chess q2,
chess q3,
chess q4
where
q1.x<=4 and q1.y<=4 -- 对称原则，把第一个Queen放在前1/4棋盘。
and q1.x < q2.x and q2.x < q3.x and q3.x < q4.x -- 其他3个Queen依次排开，不同X
and q1.y != q2.y and q1.y != q3.y and q1.y != q4.y  -- 不同Y
and q2.y != q3.y and q2.y != q4.y and q3.y != q4.y
and q1.z1 != q2.z1 and q1.z1 != q3.z1 and q1.z1 != q4.z1  -- 不同Z
and q2.z1 != q3.z1 and q2.z1 != q4.z1 and q3.z1 != q4.z1
and q1.z2 != q2.z2 and q1.z2 != q3.z2 and q1.z2 != q4.z2
and q2.z2 != q3.z2 and q2.z2 != q4.z2 and q3.z2 != q4.z2
)
select * from
(
select j.*,
(select count(distinct kn ) -- 4个Queen能攻击到的位置，去除重复攻击点。
                  from chess_attack
                 where n in
                       (j.q1n,j.q2n,j.q3n,j.q4n)) as cnt
                         from   chess_4queen  j
) where cnt = 49

10秒出结果
Q1X,Q1Y,Q1N,Q2X,Q2Y,Q2N,Q3X,Q3Y,Q3N,Q4X,Q4Y,Q4N,CNT
0,1,10,1,5,51,3,0,3,4,4,44,49
0,3,30,1,0,1,4,4,44,5,1,15,49
0,3,30,1,6,61,4,2,24,5,5,55,49
1,1,11,2,4,42,5,0,5,6,3,36,49
2,2,22,3,6,63,5,1,15,6,5,56,49
2,4,42,3,0,3,5,5,55,6,1,16,49

rollingpig

其实用inline table只是简化了写法，性能不行。
如果把with as 里的table拿出来，create出来，在chess_attack的N上创建index. 总共1秒多就出来了。

drop table chess;
create table chess
as select x.l as x,y.l as y,x.l+y.l as z1,x.l-y.l as z2,x.l+10*y.l as n
from (select level-1 l from dual connect by level <=7) x,
(select level-1 l from dual connect by level <=7)y
;
drop table chess_attack;
create table chess_attack as
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as bn,'X' as type from chess a, chess b
where a.x=b.x
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as bn,'Y' as type from chess a, chess b
where a.y=b.y
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as bn,'Z1' as type from chess a, chess b
where     a.z1=b.z1
union all
select a.x,a.y,a.n, b.x kx,b.y ky,b.n as bn,'Z2' as type from chess a, chess b
where     a.z2=b.z2  ;
drop table chess_4queen;
create table chess_4queen
as
select
q1.x as q1x,q1.y as q1y,q1.n as q1n,
q2.x as q2x,q2.y as q2y,q2.n as q2n,
q3.x as q3x,q3.y as q3y,q3.n as q3n,
q4.x as q4x,q4.y as q4y,q4.n as q4n
from
chess q1,
chess q2,
chess q3,
chess q4
where
q1.x<=4 and q1.y<=4
and q1.x < q2.x and q2.x < q3.x and q3.x < q4.x
and q1.y != q2.y and q1.y != q3.y and q1.y != q4.y
and q2.y != q3.y and q2.y != q4.y and q3.y != q4.y
and q1.z1 != q2.z1 and q1.z1 != q3.z1 and q1.z1 != q4.z1
and q2.z1 != q3.z1 and q2.z1 != q4.z1 and q3.z1 != q4.z1
and q1.z2 != q2.z2 and q1.z2 != q3.z2 and q1.z2 != q4.z2
and q2.z2 != q3.z2 and q2.z2 != q4.z2 and q3.z2 != q4.z2 ;
create index  chess_attack_inx on chess_attack(n) ;
select  * from
(
select j.*,
(select count(distinct kx||' '||ky)
                  from chess_attack
                 where n in
                       (j.q1n,j.q2n,j.q3n,j.q4n)) as cnt
                         from   chess_4queen  j
) where cnt = 49