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

newkid

6666444的做法其实和滚珠是很类似的，只是用标量子查询代替了表连接。t2里面那些trunc, mod都可以预先在t中算好。a.l*1e6+b.l*1e4+c.l*1e2+d.l可以改用带分隔符的字符串合并，然后后面用instr判断。
我的两个答案其实是旋转对称的。

newkid

把我最后的四表连接改用11GR2的递归WITH实现，consistent gets从3360下降到22, 虽然执行时间没有什么差别。
WITH c1 AS (
   SELECT ROWNUM id, MOD(ROWNUM-1,7)+1 x,CEIL(ROWNUM/7) y FROM DUAL CONNECT BY ROWNUM<=49
   )
  ,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=49
    START WITH c2.id=1
   CONNECT BY c1.id = PRIOR c1.id AND c2.id = PRIOR c2.id+1
   )
  ,t(id,cover,result,lvl) AS (
   SELECT id,cover,'('||x||','||y||')' AS result,1
     FROM cells
    WHERE x BETWEEN 1 AND 4
          AND y BETWEEN 1 AND 4
          AND x <= y
   UNION ALL
   SELECT c2.id
         ,LPAD(SUBSTR(c1.cover,1,25)+SUBSTR(c2.cover,1,25),25,'0')   ---- 位数太多NUMBER型不支持，所以拆成两截分别相加再拼回来
          ||LPAD(SUBSTR(c1.cover,26)+SUBSTR(c2.cover,26),24,'0')
         ,result||'('||c2.x||','||c2.y||')'
         ,c1.lvl+1
     FROM t c1,cells c2
    WHERE c1.lvl<4
          AND c1.id<c2.id AND SUBSTR(c1.cover,c2.id,1)='0'
  )
SELECT result FROM t
WHERE lvl=4
       AND INSTR(cover,'0')=0;


RESULT
----------------------------
(2,2)(5,3)(1,6)(4,7)
(3,3)(7,4)(2,6)(6,7)

newkid

http://www.puzzles.com/puzzleplayground/UnattackedCells/UnattackedCells.htm

Unattacked Cells after Martin Gardner

Home / Puzzle Playground / Puzzles / Chess 'n' Checkers / It's quite easy to place four chess queens on a 4x4 board to leave one unattacked vacant cell - see the diagram at right. The only unattacked cell is marked with a red dot. This cell can't be reached by any of the queens according to their allowed moves. Your task is to place five chess queens on a 5x5 board in such a way that a maximum number of vacant cells are unattacked. By the way, if you've forgotten the chess queen's moves the diagram at left will remind it to you. It shows that you may move the queen in any of the eight directions and on any number of the vacant cells. For more convenient solving you may print out the board, and use five quarters as queens and some pennies to mark the unattacked vacant cells. 新任务： 5X5的棋盘上摆放5个皇后，使得它们攻击不到的安全点最多（各皇后之间可以互相攻击）。

anlinew

可以试试Oracle Spatial

〇〇

我猜把棋子放到角上挤成一团会好

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

〇〇

猜错了

rollingpig

hehe
论性能，还是newkid厉害。

不过，我写的时候的是这样考虑的：
1。 首先，大家能看懂
2。 然后，跑得快

lastwinner

五皇后



6个红圈处任选一处摆放，仅能消除掉中路三个未被攻击的单元格中的一个
若在其他位置摆放，则能消除掉中路三个未被攻击的单元格中的两个或三个（即全部）

此摆法最多剩余 2个未被攻击的单元格

yellowlee

看能不能摆下6个皇后，我sql出来是不能，sql不贴了


猜下，5*5棋盘最多只能放下5个皇后？
那么位置是这些，没有管对称性的：
SQL> with temp as (
  2  select level node,
  3         trunc((level+4)/5) -1 row_num,
  4         mod(level+4,5) col_num,
  5         case when mod(level,5) >0 then  mod(level+4,5)+trunc(level/5)
  6              when mod(level,5) = 0 then mod(level+4,5)+trunc(level/5 -1)
  7         end a_num,
  8         level -6*(trunc((level+4)/5) -1)+12   b_num
  9   from dual connect by level <= 25
10  )
11  select a.node,b.node,c.node,d.node,e.node
12      from temp a ,temp b ,temp c,temp d,temp e
13  where a.node < b.node
14      and b.node < c.node
15      and c.node < d.node
16      and d.node < e.node
17      and not (
18          a.row_num = b.row_num or a.row_num = c.row_num or a.row_num = d.row_num or a.row_num = e.row_num
19          or b.row_num = c.row_num or b.row_num = d.row_num or b.row_num = e.row_num
20          or c.row_num = d.row_num or c.row_num = e.row_num
21          or d.row_num = e.row_num
22          )
23      and not (
24          a.col_num = b.col_num or a.col_num = c.col_num or a.col_num = d.col_num or a.col_num = e.col_num
25          or b.col_num = c.col_num or b.col_num = d.col_num or b.col_num = e.col_num
26          or c.col_num = d.col_num or c.col_num = e.col_num  
27          or d.col_num = e.col_num
28          )
29      and not (
30          a.a_num = b.a_num or a.a_num = c.a_num or a.a_num = d.a_num or a.a_num = e.a_num
31          or b.a_num = c.a_num or b.a_num = d.a_num or b.a_num = e.a_num
32          or c.a_num = d.a_num or c.a_num = e.a_num
33          or d.a_num = e.a_num
34          )
35      and not (
36          a.b_num = b.b_num or a.b_num = c.b_num or a.b_num = d.b_num or a.b_num = e.b_num
37          or b.b_num = c.b_num or b.b_num = d.b_num or b.b_num = e.b_num
38          or c.b_num = d.b_num or c.b_num = e.b_num
39          or d.b_num = e.b_num
40          )
41  ;

      NODE       NODE       NODE       NODE       NODE
---------- ---------- ---------- ---------- ----------
         1          8         15         17         24
         1          9         12         20         23
         2          9         11         18         25
         2         10         13         16         24
         3          6         14         17         25
         3         10         12         19         21
         4          6         13         20         22
         4          7         15         18         21
         5          7         14         16         23
         5          8         11         19         22

10 rows selected.

SQL>

[ 本帖最后由 yellowlee 于 2010-8-19 09:58 编辑 ]

6666444

俺写的性能最差....
第二个题直接摆比用SQL快N多