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

newkid

我的递归WITH也受益于OO的FBO, 现在只需不到0.2秒：

WITH c1 AS (
  SELECT ROWNUM id, MOD(ROWNUM-1,8)+1 x,CEIL(ROWNUM/8) y FROM DUAL CONNECT BY ROWNUM<=64
  )
,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=64
   START WITH c2.id=1
  CONNECT BY c1.id = PRIOR c1.id AND c2.id = PRIOR c2.id+1
  )
,t(id,cover,result,lvl,x) AS (
  SELECT id,cover,'('||x||','||y||')' AS result,1,x
    FROM cells
   WHERE x =1
  UNION ALL
  SELECT c2.id
        ,LPAD(SUBSTR(c1.cover,1,32)+SUBSTR(c2.cover,1,32),32,'0')
         ||LPAD(SUBSTR(c1.cover,33)+SUBSTR(c2.cover,33),32,'0')
        ,result||'('||c2.x||','||c2.y||')'
        ,c1.lvl+1
        ,c2.x
    FROM t c1,cells c2
   WHERE c1.lvl<8
         AND c1.x+1=c2.x AND SUBSTR(c1.cover,c2.id,1)='0'
)
SELECT result FROM t
WHERE lvl=8;

熊猫儿

好贴。。。

熊猫儿

佩服newkid，厉害。。。。

newkid

#70马步问题：


WITH c AS (
SELECT LEVEL id, MOD(LEVEL-1,4)+1 x,CEIL(LEVEL/4) y
  FROM DUAL
WHERE LEVEL NOT IN (1,4,13,16) ---去除四个角
CONNECT BY LEVEL<=16
)
,moves AS ( ---- 构造所有马步的两点坐标
   SELECT c1.*
         ,c2.id id2
     FROM c c1,c c2
    WHERE c2.x IN (c1.x-2,c1.x+2) AND c2.y IN (c1.y-1,c1.y+1)  ---- 马步的坐标关系
          OR c2.x IN (c1.x-1,c1.x+1) AND c2.y IN (c1.y-2,c1.y+2)
)
SELECT SYS_CONNECT_BY_PATH('('||x||','||y||')',' ')
  FROM moves
WHERE LEVEL=12   ---- 12格全部走遍
       AND id2=CONNECT_BY_ROOT(id)   ----- 最终回到起点
START WITH id =2 ---- 任取一个起点，因为每点都会走到，其他都是对称的
CONNECT BY NOCYCLE id = PRIOR id2;


SYS_CONNECT_BY_PATH('('||X||','||Y||')','')
--------------------------------------------------------------------------
(2,1) (4,2) (2,3) (3,1) (4,3) (2,2) (3,4) (1,3) (3,2) (2,4) (1,2) (3,3)
(2,1) (1,3) (3,2) (2,4) (4,3) (2,2) (3,4) (4,2) (2,3) (3,1) (1,2) (3,3)
(2,1) (3,3) (1,2) (3,1) (2,3) (4,2) (3,4) (2,2) (4,3) (2,4) (3,2) (1,3)
(2,1) (3,3) (1,2) (2,4) (3,2) (1,3) (3,4) (2,2) (4,3) (3,1) (2,3) (4,2)

8 rows selected.

regonly1

看得云里雾里，要是能把具体的思想或想法说出来就更好了.....希望大师能够多多分享你们的思想

newkid

这个马步问题应该很好懂的啊？第一个查询集合C构造出4X4的棋盘对每一格进行1-16编码，算出对应的行列坐标（我的X,Y表示的是笛卡尔坐标,如果要用行列表示，对调一下即可），根据题意去掉了四个角。
第二个查询moves找出每一个点对应的马步点，两个点之间的关系是行坐标相差1, 列坐标相差2; 或者行坐标相差2, 列坐标相差1
主查询用CONNECT BY模拟一个马的路径。每一步都是首位相接的(id = PRIOR id2), 走过的点不能重复所以用NOCYCLE, 要求全部走遍所以层数必须为12, 最终必须回到起点所以最后一步的ID2必须等于第一步的ID.
这条路径是一个环,所以任意选一个起点 START WITH ID=2, 这样可以排除一些重复答案.

〇〇

学习

tree_new_bee

newkid推荐的帖子， 过来试试。
弄了一下八皇后， 好像不是太难。

1. 
   
2. 
   
3. with t as (select  rownum-1 c from dual connect by rownum<=8)
   
4. , tt as (
   
5. select t1.c c1, t2.c c2, t3.c c3, t4.c c4, t5.c c5, t6.c c6, t7.c c7, t8.c c8
   
6. ,0 r1, 1 r2, 2 r3, 3 r4, 4 r5, 5 r6, 6 r7, 7 r8 --行不同
   
7. from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8  
   
8. )
   
9. select
   
10. '('||r1||','||c1||') ' ||
    
11. '('||r2||','||c2||') ' ||
    
12. '('||r3||','||c3||') ' ||
    
13. '('||r4||','||c4||') ' ||
    
14. '('||r5||','||c5||') ' ||
    
15. '('||r6||','||c6||') ' ||
    
16. '('||r7||','||c7||') ' ||
    
17. '('||r8||','||c8||') ' queen8
    
18. from tt
    
19. --列不同
    
20. where c2 not in (c1)
    
21. and c3 not in (c1, c2)
    
22. and c4 not in (c1, c2, c3)
    
23. and c5 not in (c1, c2, c3, c4)
    
24. and c6 not in (c1, c2, c3, c4, c5)
    
25. and c7 not in (c1, c2, c3, c4, c5, c6)
    
26. and c8 not in (c1, c2, c3, c4, c5, c6, c7)
    
27. --斜线不同
    
28. and r2+c2 not in (r1+c1)
    
29. and r3+c3 not in (r1+c1, r2+c2)
    
30. and r4+c4 not in (r1+c1, r2+c2, r3+c3)
    
31. and r5+c5 not in (r1+c1, r2+c2, r3+c3, r4+c4)
    
32. and r6+c6 not in (r1+c1, r2+c2, r3+c3, r4+c4, r5+c5)
    
33. and r7+c7 not in (r1+c1, r2+c2, r3+c3, r4+c4, r5+c5, r6+c6)
    
34. and r8+c8 not in (r1+c1, r2+c2, r3+c3, r4+c4, r5+c5, r6+c6, r7+c7)
    
35. --另一条斜线不同
    
36. and r2-c2 not in (r1-c1)
    
37. and r3-c3 not in (r1-c1, r2-c2)
    
38. and r4-c4 not in (r1-c1, r2-c2, r3-c3)   
    
39. and r5-c5 not in (r1-c1, r2-c2, r3-c3, r4-c4)   
    
40. and r6-c6 not in (r1-c1, r2-c2, r3-c3, r4-c4, r5-c5)  
    
41. and r7-c7 not in (r1-c1, r2-c2, r3-c3, r4-c4, r5-c5, r6-c6)
    
42. and r8-c8 not in (r1-c1, r2-c2, r3-c3, r4-c4, r5-c5, r6-c6, r7-c7)
    

复制代码

1. 
   
2. (0,3) (1,1) (2,6) (3,2) (4,5) (5,7) (6,4) (7,0)
   
3. (0,4) (1,1) (2,3) (3,6) (4,2) (5,7) (6,5) (7,0)
   
4. (0,2) (1,4) (2,1) (3,7) (4,5) (5,3) (6,6) (7,0)
   
5. (0,2) (1,5) (2,3) (3,1) (4,7) (5,4) (6,6) (7,0)
   
6. (0,4) (1,6) (2,0) (3,2) (4,7) (5,5) (6,3) (7,1)
   
7. (0,3) (1,5) (2,7) (3,2) (4,0) (5,6) (6,4) (7,1)
   
8. (0,2) (1,5) (2,7) (3,0) (4,3) (5,6) (6,4) (7,1)
   
9. (0,4) (1,2) (2,7) (3,3) (4,6) (5,0) (6,5) (7,1)
   
10. (0,4) (1,6) (2,3) (3,0) (4,2) (5,7) (6,5) (7,1)
    
11. (0,3) (1,0) (2,4) (3,7) (4,5) (5,2) (6,6) (7,1)
    
12. (0,2) (1,5) (2,3) (3,0) (4,7) (5,4) (6,6) (7,1)
    
13. (0,3) (1,6) (2,4) (3,2) (4,0) (5,5) (6,7) (7,1)
    
14. (0,5) (1,3) (2,1) (3,7) (4,4) (5,6) (6,0) (7,2)
    
15. (0,5) (1,3) (2,6) (3,0) (4,7) (5,1) (6,4) (7,2)
    
16. (0,0) (1,6) (2,3) (3,5) (4,7) (5,1) (6,4) (7,2)
    
17. (0,5) (1,7) (2,1) (3,3) (4,0) (5,6) (6,4) (7,2)
    
18. (0,5) (1,1) (2,6) (3,0) (4,3) (5,7) (6,4) (7,2)
    
19. (0,3) (1,6) (2,0) (3,7) (4,4) (5,1) (6,5) (7,2)
    
20. (0,4) (1,7) (2,3) (3,0) (4,6) (5,1) (6,5) (7,2)
    
21. (0,3) (1,7) (2,0) (3,4) (4,6) (5,1) (6,5) (7,2)
    
22. (0,1) (1,6) (2,4) (3,7) (4,0) (5,3) (6,5) (7,2)
    
23. (0,0) (1,6) (2,4) (3,7) (4,1) (5,3) (6,5) (7,2)
    
24. (0,1) (1,4) (2,6) (3,3) (4,0) (5,7) (6,5) (7,2)
    
25. (0,3) (1,1) (2,6) (3,4) (4,0) (5,7) (6,5) (7,2)
    
26. (0,4) (1,6) (2,0) (3,3) (4,1) (5,7) (6,5) (7,2)
    
27. (0,5) (1,3) (2,0) (3,4) (4,7) (5,1) (6,6) (7,2)
    
28. (0,4) (1,0) (2,3) (3,5) (4,7) (5,1) (6,6) (7,2)
    
29. (0,4) (1,1) (2,5) (3,0) (4,6) (5,3) (6,7) (7,2)
    
30. (0,5) (1,2) (2,6) (3,1) (4,7) (5,4) (6,0) (7,3)
    
31. (0,1) (1,6) (2,2) (3,5) (4,7) (5,4) (6,0) (7,3)
    
32. (0,6) (1,2) (2,0) (3,5) (4,7) (5,4) (6,1) (7,3)
    
33. (0,4) (1,0) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3)
    
34. (0,0) (1,4) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3)
    
35. (0,2) (1,5) (2,7) (3,0) (4,4) (5,6) (6,1) (7,3)
    
36. (0,5) (1,2) (2,0) (3,6) (4,4) (5,7) (6,1) (7,3)
    
37. (0,6) (1,4) (2,2) (3,0) (4,5) (5,7) (6,1) (7,3)
    
38. (0,6) (1,2) (2,7) (3,1) (4,4) (5,0) (6,5) (7,3)
    
39. (0,4) (1,2) (2,0) (3,6) (4,1) (5,7) (6,5) (7,3)
    
40. (0,1) (1,4) (2,6) (3,0) (4,2) (5,7) (6,5) (7,3)
    
41. (0,2) (1,5) (2,1) (3,4) (4,7) (5,0) (6,6) (7,3)
    
42. (0,5) (1,0) (2,4) (3,1) (4,7) (5,2) (6,6) (7,3)
    
43. (0,7) (1,2) (2,0) (3,5) (4,1) (5,4) (6,6) (7,3)
    
44. (0,1) (1,7) (2,5) (3,0) (4,2) (5,4) (6,6) (7,3)
    
45. (0,4) (1,6) (2,1) (3,5) (4,2) (5,0) (6,7) (7,3)
    
46. (0,2) (1,5) (2,1) (3,6) (4,4) (5,0) (6,7) (7,3)
    
47. (0,5) (1,1) (2,6) (3,0) (4,2) (5,4) (6,7) (7,3)
    
48. (0,2) (1,6) (2,1) (3,7) (4,5) (5,3) (6,0) (7,4)
    
49. (0,5) (1,2) (2,6) (3,1) (4,3) (5,7) (6,0) (7,4)
    
50. (0,3) (1,1) (2,6) (3,2) (4,5) (5,7) (6,0) (7,4)
    
51. (0,6) (1,0) (2,2) (3,7) (4,5) (5,3) (6,1) (7,4)
    
52. (0,0) (1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,4)
    
53. (0,2) (1,7) (2,3) (3,6) (4,0) (5,5) (6,1) (7,4)
    
54. (0,5) (1,2) (2,6) (3,3) (4,0) (5,7) (6,1) (7,4)
    
55. (0,6) (1,3) (2,1) (3,7) (4,5) (5,0) (6,2) (7,4)
    
56. (0,3) (1,5) (2,7) (3,1) (4,6) (5,0) (6,2) (7,4)
    
57. (0,1) (1,5) (2,0) (3,6) (4,3) (5,7) (6,2) (7,4)
    
58. (0,1) (1,3) (2,5) (3,7) (4,2) (5,0) (6,6) (7,4)
    
59. (0,2) (1,5) (2,7) (3,1) (4,3) (5,0) (6,6) (7,4)
    
60. (0,5) (1,2) (2,0) (3,7) (4,3) (5,1) (6,6) (7,4)
    
61. (0,7) (1,3) (2,0) (3,2) (4,5) (5,1) (6,6) (7,4)
    
62. (0,3) (1,7) (2,0) (3,2) (4,5) (5,1) (6,6) (7,4)
    
63. (0,1) (1,5) (2,7) (3,2) (4,0) (5,3) (6,6) (7,4)
    
64. (0,6) (1,1) (2,5) (3,2) (4,0) (5,3) (6,7) (7,4)
    
65. (0,2) (1,5) (2,1) (3,6) (4,0) (5,3) (6,7) (7,4)
    
66. (0,3) (1,6) (2,2) (3,7) (4,1) (5,4) (6,0) (7,5)
    
67. (0,3) (1,7) (2,4) (3,2) (4,0) (5,6) (6,1) (7,5)
    
68. (0,2) (1,4) (2,7) (3,3) (4,0) (5,6) (6,1) (7,5)
    
69. (0,3) (1,1) (2,7) (3,4) (4,6) (5,0) (6,2) (7,5)
    
70. (0,4) (1,6) (2,1) (3,3) (4,7) (5,0) (6,2) (7,5)
    
71. (0,6) (1,3) (2,1) (3,4) (4,7) (5,0) (6,2) (7,5)
    
72. (0,7) (1,1) (2,3) (3,0) (4,6) (5,4) (6,2) (7,5)
    
73. (0,6) (1,1) (2,3) (3,0) (4,7) (5,4) (6,2) (7,5)
    
74. (0,4) (1,0) (2,7) (3,3) (4,1) (5,6) (6,2) (7,5)
    
75. (0,3) (1,0) (2,4) (3,7) (4,1) (5,6) (6,2) (7,5)
    
76. (0,4) (1,1) (2,7) (3,0) (4,3) (5,6) (6,2) (7,5)
    
77. (0,2) (1,6) (2,1) (3,7) (4,4) (5,0) (6,3) (7,5)
    
78. (0,2) (1,0) (2,6) (3,4) (4,7) (5,1) (6,3) (7,5)
    
79. (0,7) (1,1) (2,4) (3,2) (4,0) (5,6) (6,3) (7,5)
    
80. (0,2) (1,4) (2,1) (3,7) (4,0) (5,6) (6,3) (7,5)
    
81. (0,2) (1,4) (2,6) (3,0) (4,3) (5,1) (6,7) (7,5)
    
82. (0,4) (1,1) (2,3) (3,5) (4,7) (5,2) (6,0) (7,6)
    
83. (0,5) (1,2) (2,4) (3,7) (4,0) (5,3) (6,1) (7,6)
    
84. (0,4) (1,7) (2,3) (3,0) (4,2) (5,5) (6,1) (7,6)
    
85. (0,3) (1,1) (2,4) (3,7) (4,5) (5,0) (6,2) (7,6)
    
86. (0,3) (1,5) (2,0) (3,4) (4,1) (5,7) (6,2) (7,6)
    
87. (0,5) (1,2) (2,0) (3,7) (4,4) (5,1) (6,3) (7,6)
    
88. (0,4) (1,2) (2,0) (3,5) (4,7) (5,1) (6,3) (7,6)
    
89. (0,3) (1,1) (2,7) (3,5) (4,0) (5,2) (6,4) (7,6)
    
90. (0,5) (1,2) (2,4) (3,6) (4,0) (5,3) (6,1) (7,7)
    
91. (0,5) (1,3) (2,6) (3,0) (4,2) (5,4) (6,1) (7,7)
    
92. (0,3) (1,6) (2,4) (3,1) (4,5) (5,0) (6,2) (7,7)
    
93. (0,4) (1,6) (2,1) (3,5) (4,2) (5,0) (6,3) (7,7)
    
94. 
    
95. 已选择92行。
    
96. 
    
97. 已用时间:  00: 00: 00.02
    
98. 
    

复制代码

排重的时候，什么花哨技巧都不如老老实实的一个一个排除， 用translate/connect by 之类的方法，能慢死。

[ 本帖最后由 tree_new_bee 于 2010-12-5 15:59 编辑 ]

tree_new_bee

顶楼的4皇后问题， 结果有个有趣的发现： 无论怎么旋转， 结果按序号排列的话， 最小和最大序号和=中间两个序号的和

lastwinner

connect by的代价是低level的必须要列出，这点很讨厌，估计oracle 12g里能有改进