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

szusunny

-- 5X5的棋盘上摆放5个皇后，使得它们攻击不到的安全点最多（各皇后之间可以互相攻击）。
-- 答案是最多有3个安全点

with tmp1 as(select rownum as p from dual connect by rownum <= 5),
tmp2 as(select a.p as x,b.p as y, (a.p-1)*5+b.p as t from tmp1 a, tmp1 b),
tmp3 as(
select
  a.x as a_x, a.y as a_y,
  b.x as b_x, b.y as b_y,
  c.x as c_x, c.y as c_y,
  d.x as d_x, d.y as d_y,
  e.x as e_x, e.y as e_y
from tmp2 a, tmp2 b, tmp2 c, tmp2 d, tmp2 e
where  
  a.t < b.t and b.t < c.t and c.t < d.t and d.t < e.t)
--
select
  '('||a_x||','||a_y||')' as P1,
  '('||b_x||','||b_y||')' as P2,
  '('||c_x||','||c_y||')' as P3,
  '('||d_x||','||d_y||')' as P4,
  '('||e_x||','||e_y||')' as P5,
  ct
from
  (select
     b.a_x,b.b_x,b.c_x,b.d_x,b.e_x,b.a_y,b.b_y,b.c_y,b.d_y,b.e_y,
     count(*) as ct,max(count(*))over() as max_ct
  from tmp2 a, tmp3 b
  where abs(a.x-b.a_x)<>abs(a.y-b.a_y) and abs(a.x-b.b_x)<>abs(a.y-b.b_y)
    and abs(a.x-b.c_x)<>abs(a.y-b.c_y) and abs(a.x-b.d_x)<>abs(a.y-b.d_y)
    and abs(a.x-b.e_x)<>abs(a.y-b.e_y)
    and a.x not in (b.a_x,b.b_x,b.c_x,b.d_x,b.e_x)
    and a.y not in (b.a_y,b.b_y,b.c_y,b.d_y,b.e_y)
  group by b.a_x,b.b_x,b.c_x,b.d_x,b.e_x,b.a_y,b.b_y,b.c_y,b.d_y,b.e_y)
where ct = max_ct

-- Result
           P1        P2        P3        P4        P5        CT
1        (1,2)        (1,3)        (2,2)        (2,5)        (3,5)        3
2        (1,3)        (1,4)        (2,1)        (2,4)        (3,1)        3
3        (1,2)        (1,3)        (3,1)        (4,1)        (4,2)        3
4        (1,3)        (1,4)        (3,5)        (4,4)        (4,5)        3
5        (2,1)        (2,2)        (3,1)        (5,2)        (5,3)        3
6        (2,4)        (2,5)        (3,5)        (5,3)        (5,4)        3
7        (3,1)        (4,1)        (4,4)        (5,3)        (5,4)        3
8        (3,5)        (4,2)        (4,5)        (5,2)        (5,3)        3

-- 8 rows selected in 0.266 seconds

yellowlee

这个题不继续玩了，不知道规则。。

lastwinner

论正确性，还是电脑算起来和验证起来快

jiqing1004

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 <=5) x,
(select level-1 l from dual connect by level <=5)y ),
chess_5queen as -- 4个Queen的放置位置
(select  /*+ materialize */
q1.x as q1x, q1.y as q1y, q1.z1 as q1z1, q1.z2 as q1z2, q1.n as q1n,
q2.x as q2x, q2.y as q2y, q2.z1 as q2z1, q2.z2 as q2z2, q2.n as q2n,
q3.x as q3x, q3.y as q3y, q3.z1 as q3z1, q3.z2 as q3z2, q3.n as q3n,
q4.x as q4x, q4.y as q4y, q4.z1 as q4z1, q4.z2 as q4z2, q4.n as q4n,
q5.x as q5x, q5.y as q5y, q5.z1 as q5z1, q5.z2 as q5z2, q5.n as q5n
from chess q1, chess q2, chess q3, chess q4, chess q5
where q1.x <= 2 AND q1.y <= 2 /*q1.n = '0#0'*/
AND q1.x <= q2.x and q2.x <= q3.x and q3.x <= q4.x and q4.x <= q5.x --避免重复  
AND q1.n != q2.n and q1.n != q3.n and q1.n != q4.n AND q1.n != q5.n
and q2.n != q3.n and q2.n != q4.n AND q2.n != q5.n AND q3.n != q4.n
and q3.n != q5.n and q4.n != q5.n
)
select  /*+ materialize */
q1n, q2n, q3n, q4n, q5n ,count(b.n) cnt
from chess_5queen a, chess b
where (a.q1x=b.x or a.q1y=b.y or a.q1z1=b.z1 or a.q1z2=b.z2
    OR a.q2x=b.x or a.q2y=b.y or a.q2z1=b.z1 or a.q2z2=b.z2
    OR a.q3x=b.x or a.q3y=b.y or a.q3z1=b.z1 or a.q3z2=b.z2
    OR a.q4x=b.x or a.q4y=b.y or a.q4z1=b.z1 or a.q4z2=b.z2
    OR a.q5x=b.x or a.q5y=b.y or a.q5z1=b.z1 or a.q5z2=b.z2
    )
GROUP BY q1n, q2n, q3n, q4n, q5n
ORDER BY cnt

在滚猪大师的基础的上改了一下,
还可以剩3呢

〇〇

最后一个查询实体化没有意义

已选择226行。

已用时间:  00: 00: 21.96

[ 本帖最后由 〇〇 于 2010-8-19 11:11 编辑 ]

jiqing1004

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 <=5) x,
(select LEVEL-1 l from dual connect by level <=5)y ),
chess_5queen as -- 5个Queen的放置位置
(select  /*+ materialize */
q1.x as q1x, q1.y as q1y, q1.z1 as q1z1, q1.z2 as q1z2, q1.n as q1n,
q2.x as q2x, q2.y as q2y, q2.z1 as q2z1, q2.z2 as q2z2, q2.n as q2n,
q3.x as q3x, q3.y as q3y, q3.z1 as q3z1, q3.z2 as q3z2, q3.n as q3n,
q4.x as q4x, q4.y as q4y, q4.z1 as q4z1, q4.z2 as q4z2, q4.n as q4n,
q5.x as q5x, q5.y as q5y, q5.z1 as q5z1, q5.z2 as q5z2, q5.n as q5n
from chess q1, chess q2, chess q3, chess q4, chess q5
where q1.x <= 2 AND q1.y <= 2 --避免对称
AND q1.n < q2.n and q2.n < q3.n and q3.n < q4.n and q4.n < q5.n --避免重复  
)
SELECT q1n, q2n, q3n, q4n, q5n
  FROM (SELECT q1n, q2n, q3n, q4n, q5n
              ,COUNT(b.n) cnt
              ,MIN(COUNT(b.n)) over() min_cnt
          FROM chess_5queen a, chess b
         WHERE  (a.q1x = b.x OR a.q1y = b.y OR a.q1z1 = b.z1 OR a.q1z2 = b.z2 OR  --攻击范围
               a.q2x = b.x OR a.q2y = b.y OR a.q2z1 = b.z1 OR a.q2z2 = b.z2 OR
               a.q3x = b.x OR a.q3y = b.y OR a.q3z1 = b.z1 OR a.q3z2 = b.z2 OR
               a.q4x = b.x OR a.q4y = b.y OR a.q4z1 = b.z1 OR a.q4z2 = b.z2 OR
               a.q5x = b.x OR a.q5y = b.y OR a.q5z1 = b.z1 OR a.q5z2 = b.z2)
         GROUP BY q1n, q2n, q3n, q4n, q5n)
WHERE cnt = min_cnt
ORDER BY q1n, q2n, q3n, q4n, q5n

修改了一下

〇〇

给51楼画了一个图

with t as(select level-1 l,trunc((level-1)/5) r,mod(level-1,5)c from dual connect by level<=25),
p as(
select 1 x,2 y from dual union all
select 1 x,3 y from dual union all
select 2 x,2 y from dual union all
select 2 x,5 y from dual union all
select 3 x,5 y from dual)
select replace(sys_connect_by_path(s,','),',')
from (select l,r,c, 'Ｑ' s from t where l in (select (x-1)*5+(y-1) from p) union all
select l,r,c, decode(mod(l,2),0,'█',1,'  ') s from t where l not in (select (x-1)*5+(y-1) from p))
where level=5
connect by prior c=c-1 and prior r=r
;

REPLACE(SYS_CONNECT_BY_PATH(S,','),',')
----------------------------------
█ＱＱ  █
  Ｑ  █Ｑ
█  █  Ｑ
  █  █
█  █  █

[ 本帖最后由 〇〇 于 2010-8-19 14:04 编辑 ]

〇〇

找出不被攻击的格子
  1  with t as(select level-1 l,trunc((level-1)/5) r,mod(level-1,5)c from dual connect by level<=25),
  2  p as(
  3  select 1 x,2 y from dual union all
  4  select 1 x,3 y from dual union all
  5  select 2 x,2 y from dual union all
  6  select 2 x,5 y from dual union all
  7  select 3 x,5 y from dual)
  8  select * from t
  9  minus select * from t where r+1 in (select x from p)
10  minus select * from t where c+1 in (select y from p)
11  minus select * from t where r+1+c+1 in (select x+y from p)
12* minus select * from t where c-r in (select y-x from p)
SQL> /

         L          R          C
---------- ---------- ----------
        15          3          0
        20          4          0
        23          4          3

〇〇

画出被攻击的格子

with t as(select level-1 l,trunc((level-1)/5) r,mod(level-1,5)c from dual connect by level<=25),
p as(
select 1 x,2 y from dual union all
select 1 x,3 y from dual union all
select 2 x,2 y from dual union all
select 2 x,5 y from dual union all
select 3 x,5 y from dual)
q as(select * from t
minus select * from t where r+1 in (select x from p)
minus select * from t where c+1 in (select y from p)
minus select * from t where r+1+c+1 in (select x+y from p)
minus select * from t where c-r in (select y-x from p)
)
select replace(sys_connect_by_path(s,','),',')
from (select l,r,c, 'Ｑ' s from t where l in (select (x-1)*5+(y-1) from p) union all
select l,r,c,'Ж's from t where l not in (select (x-1)*5+(y-1) from p) and l not in (select l from q) union all
select l,r,c, decode(mod(l,2),0,'█',1,'  ') s from t where l not in (select (x-1)*5+(y-1) from p) and l in (select l from q))
where level=5
connect by prior c=c-1 and prior r=r
;

REPLACE(SYS_CONNECT_BY_PATH(S,','),',')
------------------------------------------
ЖＱＱЖЖ
ЖＱЖЖＱ
ЖЖЖЖＱ
  ЖЖЖЖ
█ЖЖ  Ж

newkid

OO的画图手艺不错呀！


用我的位操作法：

WITH c1 AS (
   SELECT ROWNUM id, MOD(ROWNUM-1,5)+1 x,CEIL(ROWNUM/5) y FROM DUAL CONNECT BY ROWNUM<=25
   )
  ,cells 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=25
    START WITH c2.id=1
   CONNECT BY c1.id = PRIOR c1.id AND c2.id = PRIOR c2.id+1
   )
,t1 AS (
SELECT c1.x||c1.y||'-'||c2.x||c2.y||'-'||c3.x||c3.y||'-'||c4.x||c4.y||'-'||c5.x||c5.y AS result
      ,LPAD(c1.cover+c2.cover+c3.cover+c4.cover+c5.cover,25,'0') cover
  FROM cells c1,cells c2, cells c3, cells c4, cells c5
WHERE c1.x BETWEEN 1 AND 3
       AND c1.y BETWEEN 1 AND 3
       AND c1.x <= c1.y
       AND c1.id < c2.id AND c2.id < c3.id AND c3.id < c4.id AND c4.id < c5.id
)
SELECT result,25-LENGTH(REPLACE(cover,'0')) FROM (
SELECT result,cover,RANK() OVER(ORDER BY LENGTH(REPLACE(cover,'0'))) rnk
  FROM t1
  )
WHERE rnk=1;

12-22-13-25-35      3
13-14-44-35-45      3

这两个答案也是对称的。