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

newkid · 发表于 2010-8-21 03:55

61楼的经典八皇后问题，我以为递归最好，没想到传统的SQL写法是最快的：

WITH c AS (
  SELECT id,x,y,x+y m,x-y n FROM (
SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
)
  )
SELECT '('||c1.x||','||c1.y||')'
   ||'('||c2.x||','||c2.y||')'
   ||'('||c3.x||','||c3.y||')'
   ||'('||c4.x||','||c4.y||')'
   ||'('||c5.x||','||c5.y||')'
   ||'('||c6.x||','||c6.y||')'
   ||'('||c7.x||','||c7.y||')'
   ||'('||c8.x||','||c8.y||')'
  FROM c c1,c c2,c c3,c c4,c c5,c c6,c c7,c c8
WHERE c1.id<c2.id AND c2.id<c3.id AND c3.id<c4.id AND c4.id<c5.id AND c5.id<c6.id AND c6.id<c7.id AND c7.id<c8.id AND
   NOT (c1.x IN (c2.x,c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c1.y IN (c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c1.m IN (c2.m,c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c1.n IN (c2.n,c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c2.x IN (c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c2.y IN (c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c2.m IN (c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c2.n IN (c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c3.x IN (c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c3.y IN (c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c3.m IN (c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c3.n IN (c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c4.x IN (c5.x,c6.x,c7.x,c8.x)
         OR c4.y IN (c5.y,c6.y,c7.y,c8.y)
         OR c4.m IN (c5.m,c6.m,c7.m,c8.m)
         OR c4.n IN (c5.n,c6.n,c7.n,c8.n)
         OR c5.x IN (c6.x,c7.x,c8.x)
         OR c5.y IN (c6.y,c7.y,c8.y)
         OR c5.m IN (c6.m,c7.m,c8.m)
         OR c5.n IN (c6.n,c7.n,c8.n)
         OR c6.x IN (c7.x,c8.x)
         OR c6.y IN (c7.y,c8.y)
         OR c6.m IN (c7.m,c8.m)
         OR c6.n IN (c7.n,c8.n)
         OR c7.x IN (c8.x)
         OR c7.y IN (c8.y)
         OR c7.m IN (c8.m)
         OR c7.n IN (c8.n)
         )
;

〇〇 · 发表于 2010-8-21 05:33

华丽到赏心悦目,没想到能这么快

SQL> WITH c AS (
  2 SELECT id,x,y,x+y m,x-y n FROM (
  3    SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
  4    )
  5 )
  6  SELECT '('||c1.x||','||c1.y||')'
  7    ||'('||c2.x||','||c2.y||')'
  8    ||'('||c3.x||','||c3.y||')'
  9    ||'('||c4.x||','||c4.y||')'
10    ||'('||c5.x||','||c5.y||')'
11    ||'('||c6.x||','||c6.y||')'
12    ||'('||c7.x||','||c7.y||')'
13    ||'('||c8.x||','||c8.y||')'
14 FROM c c1,c c2,c c3,c c4,c c5,c c6,c c7,c c8
15  WHERE c1.id<c2.id AND c2.id<c3.id AND c3.id<c4.id AND c4.id<c5.id AND c5.id<c6.id AND c6.id<c7.id AND c7.id<c8.id AND
16       NOT (c1.x IN (c2.x,c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
17             OR c1.y IN (c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
18             OR c1.m IN (c2.m,c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
19             OR c1.n IN (c2.n,c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
20             OR c2.x IN (c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
21             OR c2.y IN (c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
22             OR c2.m IN (c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
23             OR c2.n IN (c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
24             OR c3.x IN (c4.x,c5.x,c6.x,c7.x,c8.x)
25             OR c3.y IN (c4.y,c5.y,c6.y,c7.y,c8.y)
26             OR c3.m IN (c4.m,c5.m,c6.m,c7.m,c8.m)
27             OR c3.n IN (c4.n,c5.n,c6.n,c7.n,c8.n)
28             OR c4.x IN (c5.x,c6.x,c7.x,c8.x)
29             OR c4.y IN (c5.y,c6.y,c7.y,c8.y)
30             OR c4.m IN (c5.m,c6.m,c7.m,c8.m)
31             OR c4.n IN (c5.n,c6.n,c7.n,c8.n)
32             OR c5.x IN (c6.x,c7.x,c8.x)
33             OR c5.y IN (c6.y,c7.y,c8.y)
34             OR c5.m IN (c6.m,c7.m,c8.m)
35             OR c5.n IN (c6.n,c7.n,c8.n)
36             OR c6.x IN (c7.x,c8.x)
37             OR c6.y IN (c7.y,c8.y)
38             OR c6.m IN (c7.m,c8.m)
39             OR c6.n IN (c7.n,c8.n)
40             OR c7.x IN (c8.x)
41             OR c7.y IN (c8.y)
42             OR c7.m IN (c8.m)
43             OR c7.n IN (c8.n)
44          )
45  ;

'('||C1.X||','||C1.Y||')'||'('||C2.X||','||C2.Y||')'||'('||C3.X||','||C3.Y||')'||'('||C4.X||','||C4.Y||')'||'('||C5.X||','||C5.Y||')'|
|'('||C6.X||','|
--------------------------------------------------------------------------------------------------------------------------------------
----------------
(4,1)(2,2)(7,3)(3,4)(6,5)(8,6)(5,7)(1,8)
(5,1)(2,2)(4,3)(7,4)(3,5)(8,6)(6,7)(1,8)
(3,1)(5,2)(2,3)(8,4)(6,5)(4,6)(7,7)(1,8)
(3,1)(6,2)(4,3)(2,4)(8,5)(5,6)(7,7)(1,8)
(5,1)(7,2)(1,3)(3,4)(8,5)(6,6)(4,7)(2,8)
(4,1)(6,2)(8,3)(3,4)(1,5)(7,6)(5,7)(2,8)
(3,1)(6,2)(8,3)(1,4)(4,5)(7,6)(5,7)(2,8)
(5,1)(3,2)(8,3)(4,4)(7,5)(1,6)(6,7)(2,8)
(5,1)(7,2)(4,3)(1,4)(3,5)(8,6)(6,7)(2,8)
(4,1)(1,2)(5,3)(8,4)(6,5)(3,6)(7,7)(2,8)
(3,1)(6,2)(4,3)(1,4)(8,5)(5,6)(7,7)(2,8)
(4,1)(7,2)(5,3)(3,4)(1,5)(6,6)(8,7)(2,8)
(6,1)(4,2)(2,3)(8,4)(5,5)(7,6)(1,7)(3,8)
(6,1)(4,2)(7,3)(1,4)(8,5)(2,6)(5,7)(3,8)
(1,1)(7,2)(4,3)(6,4)(8,5)(2,6)(5,7)(3,8)
(6,1)(8,2)(2,3)(4,4)(1,5)(7,6)(5,7)(3,8)
(6,1)(2,2)(7,3)(1,4)(4,5)(8,6)(5,7)(3,8)
(4,1)(7,2)(1,3)(8,4)(5,5)(2,6)(6,7)(3,8)
(5,1)(8,2)(4,3)(1,4)(7,5)(2,6)(6,7)(3,8)
(4,1)(8,2)(1,3)(5,4)(7,5)(2,6)(6,7)(3,8)
(2,1)(7,2)(5,3)(8,4)(1,5)(4,6)(6,7)(3,8)
(1,1)(7,2)(5,3)(8,4)(2,5)(4,6)(6,7)(3,8)
(2,1)(5,2)(7,3)(4,4)(1,5)(8,6)(6,7)(3,8)
(4,1)(2,2)(7,3)(5,4)(1,5)(8,6)(6,7)(3,8)
(5,1)(7,2)(1,3)(4,4)(2,5)(8,6)(6,7)(3,8)
(6,1)(4,2)(1,3)(5,4)(8,5)(2,6)(7,7)(3,8)
(5,1)(1,2)(4,3)(6,4)(8,5)(2,6)(7,7)(3,8)
(5,1)(2,2)(6,3)(1,4)(7,5)(4,6)(8,7)(3,8)
(6,1)(3,2)(7,3)(2,4)(8,5)(5,6)(1,7)(4,8)
(2,1)(7,2)(3,3)(6,4)(8,5)(5,6)(1,7)(4,8)
(7,1)(3,2)(1,3)(6,4)(8,5)(5,6)(2,7)(4,8)
(5,1)(1,2)(8,3)(6,4)(3,5)(7,6)(2,7)(4,8)
(1,1)(5,2)(8,3)(6,4)(3,5)(7,6)(2,7)(4,8)
(3,1)(6,2)(8,3)(1,4)(5,5)(7,6)(2,7)(4,8)
(6,1)(3,2)(1,3)(7,4)(5,5)(8,6)(2,7)(4,8)
(7,1)(5,2)(3,3)(1,4)(6,5)(8,6)(2,7)(4,8)
(7,1)(3,2)(8,3)(2,4)(5,5)(1,6)(6,7)(4,8)
(5,1)(3,2)(1,3)(7,4)(2,5)(8,6)(6,7)(4,8)
(2,1)(5,2)(7,3)(1,4)(3,5)(8,6)(6,7)(4,8)
(3,1)(6,2)(2,3)(5,4)(8,5)(1,6)(7,7)(4,8)
(6,1)(1,2)(5,3)(2,4)(8,5)(3,6)(7,7)(4,8)
(8,1)(3,2)(1,3)(6,4)(2,5)(5,6)(7,7)(4,8)
(2,1)(8,2)(6,3)(1,4)(3,5)(5,6)(7,7)(4,8)
(5,1)(7,2)(2,3)(6,4)(3,5)(1,6)(8,7)(4,8)
(3,1)(6,2)(2,3)(7,4)(5,5)(1,6)(8,7)(4,8)
(6,1)(2,2)(7,3)(1,4)(3,5)(5,6)(8,7)(4,8)
(3,1)(7,2)(2,3)(8,4)(6,5)(4,6)(1,7)(5,8)
(6,1)(3,2)(7,3)(2,4)(4,5)(8,6)(1,7)(5,8)
(4,1)(2,2)(7,3)(3,4)(6,5)(8,6)(1,7)(5,8)
(7,1)(1,2)(3,3)(8,4)(6,5)(4,6)(2,7)(5,8)
(1,1)(6,2)(8,3)(3,4)(7,5)(4,6)(2,7)(5,8)
(3,1)(8,2)(4,3)(7,4)(1,5)(6,6)(2,7)(5,8)
(6,1)(3,2)(7,3)(4,4)(1,5)(8,6)(2,7)(5,8)
(7,1)(4,2)(2,3)(8,4)(6,5)(1,6)(3,7)(5,8)
(4,1)(6,2)(8,3)(2,4)(7,5)(1,6)(3,7)(5,8)
(2,1)(6,2)(1,3)(7,4)(4,5)(8,6)(3,7)(5,8)
(2,1)(4,2)(6,3)(8,4)(3,5)(1,6)(7,7)(5,8)
(3,1)(6,2)(8,3)(2,4)(4,5)(1,6)(7,7)(5,8)
(6,1)(3,2)(1,3)(8,4)(4,5)(2,6)(7,7)(5,8)
(8,1)(4,2)(1,3)(3,4)(6,5)(2,6)(7,7)(5,8)
(4,1)(8,2)(1,3)(3,4)(6,5)(2,6)(7,7)(5,8)
(2,1)(6,2)(8,3)(3,4)(1,5)(4,6)(7,7)(5,8)
(7,1)(2,2)(6,3)(3,4)(1,5)(4,6)(8,7)(5,8)
(3,1)(6,2)(2,3)(7,4)(1,5)(4,6)(8,7)(5,8)
(4,1)(7,2)(3,3)(8,4)(2,5)(5,6)(1,7)(6,8)
(4,1)(8,2)(5,3)(3,4)(1,5)(7,6)(2,7)(6,8)
(3,1)(5,2)(8,3)(4,4)(1,5)(7,6)(2,7)(6,8)
(4,1)(2,2)(8,3)(5,4)(7,5)(1,6)(3,7)(6,8)
(5,1)(7,2)(2,3)(4,4)(8,5)(1,6)(3,7)(6,8)
(7,1)(4,2)(2,3)(5,4)(8,5)(1,6)(3,7)(6,8)
(8,1)(2,2)(4,3)(1,4)(7,5)(5,6)(3,7)(6,8)
(7,1)(2,2)(4,3)(1,4)(8,5)(5,6)(3,7)(6,8)
(5,1)(1,2)(8,3)(4,4)(2,5)(7,6)(3,7)(6,8)
(4,1)(1,2)(5,3)(8,4)(2,5)(7,6)(3,7)(6,8)
(5,1)(2,2)(8,3)(1,4)(4,5)(7,6)(3,7)(6,8)
(3,1)(7,2)(2,3)(8,4)(5,5)(1,6)(4,7)(6,8)
(3,1)(1,2)(7,3)(5,4)(8,5)(2,6)(4,7)(6,8)
(8,1)(2,2)(5,3)(3,4)(1,5)(7,6)(4,7)(6,8)
(3,1)(5,2)(2,3)(8,4)(1,5)(7,6)(4,7)(6,8)
(3,1)(5,2)(7,3)(1,4)(4,5)(2,6)(8,7)(6,8)
(5,1)(2,2)(4,3)(6,4)(8,5)(3,6)(1,7)(7,8)
(6,1)(3,2)(5,3)(8,4)(1,5)(4,6)(2,7)(7,8)
(5,1)(8,2)(4,3)(1,4)(3,5)(6,6)(2,7)(7,8)
(4,1)(2,2)(5,3)(8,4)(6,5)(1,6)(3,7)(7,8)
(4,1)(6,2)(1,3)(5,4)(2,5)(8,6)(3,7)(7,8)
(6,1)(3,2)(1,3)(8,4)(5,5)(2,6)(4,7)(7,8)
(5,1)(3,2)(1,3)(6,4)(8,5)(2,6)(4,7)(7,8)
(4,1)(2,2)(8,3)(6,4)(1,5)(3,6)(5,7)(7,8)
(6,1)(3,2)(5,3)(7,4)(1,5)(4,6)(2,7)(8,8)
(6,1)(4,2)(7,3)(1,4)(3,5)(5,6)(2,7)(8,8)
(4,1)(7,2)(5,3)(2,4)(6,5)(1,6)(3,7)(8,8)
(5,1)(7,2)(2,3)(6,4)(3,5)(1,6)(4,7)(8,8)

已选择92行。

已用时间:  00: 00: 04.12

〇〇 · 发表于 2010-8-21 05:42

小型机不如PC服务器
ibm 595
71：已用时间:  00: 00: 04.12
61：已用时间:  00: 00: 04.91
62：已用时间:  00: 00: 08.15
xeon 5420
71：已用时间:  00: 00: 01.73
61：已用时间:  00: 00: 03.05
62：已用时间:  00: 00: 04.58

〇〇 · 发表于 2010-8-21 06:06

观察答案后发现皇后分别在1-8行

WITH c AS (
  SELECT id,x,y,x+y m,x-y n FROM (
SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
)
  )
SELECT '('||c1.x||','||c1.y||')'
   ||'('||c2.x||','||c2.y||')'
   ||'('||c3.x||','||c3.y||')'
   ||'('||c4.x||','||c4.y||')'
   ||'('||c5.x||','||c5.y||')'
   ||'('||c6.x||','||c6.y||')'
   ||'('||c7.x||','||c7.y||')'
   ||'('||c8.x||','||c8.y||')'
  FROM (select * from c where y=1) c1,(select * from c where y=2) c2,(select * from c where y=3) c3,
  (select * from c where y=4) c4,(select * from c where y=5) c5,(select * from c where y=6) c6,
  (select * from c where y=7) c7,(select * from c where y=8) c8
WHERE --c1.id<c2.id AND c2.id<c3.id AND c3.id<c4.id AND c4.id<c5.id AND c5.id<c6.id AND c6.id<c7.id AND c7.id<c8.id AND
   NOT (c1.x IN (c2.x,c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         --OR c1.y IN (c2.y,c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c1.m IN (c2.m,c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c1.n IN (c2.n,c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c2.x IN (c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         --OR c2.y IN (c3.y,c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c2.m IN (c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c2.n IN (c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c3.x IN (c4.x,c5.x,c6.x,c7.x,c8.x)
         --OR c3.y IN (c4.y,c5.y,c6.y,c7.y,c8.y)
         OR c3.m IN (c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c3.n IN (c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c4.x IN (c5.x,c6.x,c7.x,c8.x)
         --OR c4.y IN (c5.y,c6.y,c7.y,c8.y)
         OR c4.m IN (c5.m,c6.m,c7.m,c8.m)
         OR c4.n IN (c5.n,c6.n,c7.n,c8.n)
         OR c5.x IN (c6.x,c7.x,c8.x)
         --OR c5.y IN (c6.y,c7.y,c8.y)
         OR c5.m IN (c6.m,c7.m,c8.m)
         OR c5.n IN (c6.n,c7.n,c8.n)
         OR c6.x IN (c7.x,c8.x)
         --OR c6.y IN (c7.y,c8.y)
         OR c6.m IN (c7.m,c8.m)
         OR c6.n IN (c7.n,c8.n)
         OR c7.x IN (c8.x)
         --OR c7.y IN (c8.y)
         OR c7.m IN (c8.m)
         OR c7.n IN (c8.n)
         )
;

ibm 已用时间:  00: 00: 00.29
xeon 已用时间:  00: 00: 00.16

newkid · 发表于 2010-8-21 07:45

OO的强悍FBO(FLESH BASED OPTIMIZER)又启动了！我装修如下：

WITH c AS (
  SELECT id,x,y,x+y m,x-y n FROM (
SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
)
  )
SELECT '('||c1.x||','||c1.y||')'
   ||'('||c2.x||','||c2.y||')'
   ||'('||c3.x||','||c3.y||')'
   ||'('||c4.x||','||c4.y||')'
   ||'('||c5.x||','||c5.y||')'
   ||'('||c6.x||','||c6.y||')'
   ||'('||c7.x||','||c7.y||')'
   ||'('||c8.x||','||c8.y||')'
FROM c c1,c c2,c c3,c c4,c c5,c c6,c c7,c c8
WHERE  c1.y=1 AND c2.y=2 AND c3.y=3 AND c4.y=4 AND c5.y=5 AND c6.y=6 AND c7.y=7 AND c8.y=8 AND
   NOT (c1.x IN (c2.x,c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c1.m IN (c2.m,c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c1.n IN (c2.n,c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c2.x IN (c3.x,c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c2.m IN (c3.m,c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c2.n IN (c3.n,c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c3.x IN (c4.x,c5.x,c6.x,c7.x,c8.x)
         OR c3.m IN (c4.m,c5.m,c6.m,c7.m,c8.m)
         OR c3.n IN (c4.n,c5.n,c6.n,c7.n,c8.n)
         OR c4.x IN (c5.x,c6.x,c7.x,c8.x)
         OR c4.m IN (c5.m,c6.m,c7.m,c8.m)
         OR c4.n IN (c5.n,c6.n,c7.n,c8.n)
         OR c5.x IN (c6.x,c7.x,c8.x)
         OR c5.m IN (c6.m,c7.m,c8.m)
         OR c5.n IN (c6.n,c7.n,c8.n)
         OR c6.x IN (c7.x,c8.x)
         OR c6.m IN (c7.m,c8.m)
         OR c6.n IN (c7.n,c8.n)
         OR c7.x IN (c8.x)
         OR c7.m IN (c8.m)
         OR c7.n IN (c8.n)
         )
;

newkid · 发表于 2010-8-21 08:04

#70 的马步问题用一个十几行的CONNECT BY就可以做出来。

〇〇 · 发表于 2010-8-21 08:07

也就对暴力的次数消减有办法，你要用回溯／ＤＦＳ我就没辙了

lastwinner · 发表于 2010-8-21 17:32

原帖由〇〇于 10-8-21 05:42 发表
小型机不如PC服务器
ibm 595
71：已用时间:  00: 00: 04.12
61：已用时间:  00: 00: 04.91
62：已用时间:  00: 00: 08.15
xeon 5420
71：已用时间:  00: 00: 01.73
61：已用时间:  00: 00: 03.05
62：已用时间:  00: 00: 04.58

小型机稳定性高于PC服务器，单纯论计算性能，小型机跑不过1/5其价值的PC服务器

yellowlee · 发表于 2010-8-21 19:14

都好强悍。。学习了

〇〇 · 发表于 2010-8-21 19:37

原帖由 lastwinner 于 2010-8-21 17:32 发表

小型机稳定性高于PC服务器，单纯论计算性能，小型机跑不过1/5其价值的PC服务器

nice，记住这个比例

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

浏览过的版块