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

newkid · 发表于 2010-8-19 22:17

经典的八皇后问题：
八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

把我的递归WITH稍微改写一下即可：
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) 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,32)+SUBSTR(c2.cover,1,32),32,'0') ---- 位数太多NUMBER型不支持，所以拆成两截分别相加再拼回来
      ||LPAD(SUBSTR(c1.cover,33)+SUBSTR(c2.cover,33),32,'0')
      ,result||'('||c2.x||','||c2.y||')'
      ,c1.lvl+1
FROM t c1,cells c2
WHERE c1.lvl<8
      AND c1.id<c2.id AND SUBSTR(c1.cover,c2.id,1)='0'
)
SELECT result FROM t
WHERE lvl=8;

RESULT
----------------------------------------------
(5,1)(2,2)(4,3)(6,4)(8,5)(3,6)(1,7)(7,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)(8,5)(5,6)(1,7)(4,8)
(4,1)(7,2)(3,3)(8,4)(2,5)(5,6)(1,7)(6,8)
(2,1)(7,2)(3,3)(6,4)(8,5)(5,6)(1,7)(4,8)
(6,1)(4,2)(2,3)(8,4)(5,5)(7,6)(1,7)(3,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)
(1,1)(6,2)(8,3)(3,4)(7,5)(4,6)(2,7)(5,8)
(6,1)(3,2)(5,3)(8,4)(1,5)(4,6)(2,7)(7,8)
(6,1)(3,2)(5,3)(7,4)(1,5)(4,6)(2,7)(8,8)
(7,1)(1,2)(3,3)(8,4)(6,5)(4,6)(2,7)(5,8)
(7,1)(3,2)(1,3)(6,4)(8,5)(5,6)(2,7)(4,8)
(6,1)(4,2)(7,3)(1,4)(3,5)(5,6)(2,7)(8,8)
(3,1)(8,2)(4,3)(7,4)(1,5)(6,6)(2,7)(5,8)
(5,1)(8,2)(4,3)(1,4)(3,5)(6,6)(2,7)(7,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)
(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)(7,3)(4,4)(1,5)(8,6)(2,7)(5,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)
(4,1)(7,2)(5,3)(2,4)(6,5)(1,6)(3,7)(8,8)
(7,1)(4,2)(2,3)(8,4)(6,5)(1,6)(3,7)(5,8)
(4,1)(2,2)(5,3)(8,4)(6,5)(1,6)(3,7)(7,8)
(4,1)(2,2)(8,3)(5,4)(7,5)(1,6)(3,7)(6,8)
(4,1)(6,2)(8,3)(2,4)(7,5)(1,6)(3,7)(5,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)
(4,1)(1,2)(5,3)(8,4)(2,5)(7,6)(3,7)(6,8)
(5,1)(1,2)(8,3)(4,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)
(4,1)(6,2)(1,3)(5,4)(2,5)(8,6)(3,7)(7,8)
(2,1)(6,2)(1,3)(7,4)(4,5)(8,6)(3,7)(5,8)
(5,1)(7,2)(2,3)(6,4)(3,5)(1,6)(4,7)(8,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)
(5,1)(3,2)(1,3)(6,4)(8,5)(2,6)(4,7)(7,8)
(6,1)(3,2)(1,3)(8,4)(5,5)(2,6)(4,7)(7,8)
(5,1)(7,2)(1,3)(3,4)(8,5)(6,6)(4,7)(2,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)
(1,1)(7,2)(4,3)(6,4)(8,5)(2,6)(5,7)(3,8)
(6,1)(4,2)(7,3)(1,4)(8,5)(2,6)(5,7)(3,8)
(4,1)(2,2)(8,3)(6,4)(1,5)(3,6)(5,7)(7,8)
(4,1)(6,2)(8,3)(3,4)(1,5)(7,6)(5,7)(2,8)
(6,1)(8,2)(2,3)(4,4)(1,5)(7,6)(5,7)(3,8)
(3,1)(6,2)(8,3)(1,4)(4,5)(7,6)(5,7)(2,8)
(6,1)(2,2)(7,3)(1,4)(4,5)(8,6)(5,7)(3,8)
(4,1)(2,2)(7,3)(3,4)(6,5)(8,6)(5,7)(1,8)
(7,1)(3,2)(8,3)(2,4)(5,5)(1,6)(6,7)(4,8)
(5,1)(3,2)(8,3)(4,4)(7,5)(1,6)(6,7)(2,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)
(5,1)(3,2)(1,3)(7,4)(2,5)(8,6)(6,7)(4,8)
(5,1)(7,2)(4,3)(1,4)(3,5)(8,6)(6,7)(2,8)
(2,1)(5,2)(7,3)(1,4)(3,5)(8,6)(6,7)(4,8)
(5,1)(2,2)(4,3)(7,4)(3,5)(8,6)(6,7)(1,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)
(3,1)(6,2)(2,3)(5,4)(8,5)(1,6)(7,7)(4,8)
(6,1)(4,2)(1,3)(5,4)(8,5)(2,6)(7,7)(3,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)
(5,1)(1,2)(4,3)(6,4)(8,5)(2,6)(7,7)(3,8)
(6,1)(1,2)(5,3)(2,4)(8,5)(3,6)(7,7)(4,8)
(4,1)(1,2)(5,3)(8,4)(6,5)(3,6)(7,7)(2,8)
(2,1)(6,2)(8,3)(3,4)(1,5)(4,6)(7,7)(5,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)
(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)
(3,1)(6,2)(4,3)(1,4)(8,5)(5,6)(7,7)(2,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)
(3,1)(5,2)(7,3)(1,4)(4,5)(2,6)(8,7)(6,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)
(5,1)(2,2)(6,3)(1,4)(7,5)(4,6)(8,7)(3,8)
(6,1)(2,2)(7,3)(1,4)(3,5)(5,6)(8,7)(4,8)
(4,1)(7,2)(5,3)(3,4)(1,5)(6,6)(8,7)(2,8)

92 rows selected.

有没有人用其他方法做一下？

newkid · 发表于 2010-8-19 22:46

用正宗的二进制位操作实现，效率反而更低, 从原来的2秒变为3秒多：

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
      ,SUM(POWER(2,c2.id-1)*(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
      ,POWER(2,c1.id-1) p
FROM c1, c1 c2
GROUP BY c1.id,c1.x,c1.y
  )
,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
      ,c1.cover+c2.cover-BITAND(c1.cover,c2.cover)    --- BITOR 的等价写法
      ,result||'('||c2.x||','||c2.y||')'
      ,c1.lvl+1
FROM t c1,cells c2
WHERE c1.lvl<8
      AND c1.id<c2.id
      AND MOD(TRUNC(c1.cover/c2.p),2)=0
)
SELECT result FROM t
WHERE lvl=8;

lastwinner · 发表于 2010-8-19 22:56

八皇后，按中国象棋的马步走法试试看

newkid · 发表于 2010-8-19 23:04

原帖由 lastwinner 于 2010-8-19 22:56 发表
八皇后，按中国象棋的马步走法试试看

啥意思啊？那样覆盖面就少了很多，比原来的答案应该更多？
后面确实有几个马步的题目，等我转来。

lastwinner · 发表于 2010-8-19 23:19

原帖由 newkid 于 10-8-19 23:04 发表

啥意思啊？那样覆盖面就少了很多，比原来的答案应该更多？
后面确实有几个马步的题目，等我转来。

就是选定起点后，按马步去走
如下图所示：

不过这纯粹是猜想，要睡觉了，也没仔细去验证了

newkid · 发表于 2010-8-19 23:22

明白了......你是说按马步法就可以避开攻击。值得验证一下。

newkid · 发表于 2010-8-19 23:26

随便拿个答案：

Q*******
******Q*
****Q***
*******Q
*Q******
***Q****
******Q*
**Q*****

第一行和第七行找不到马步。

lastwinner · 发表于 2010-8-20 09:29

原帖由 newkid 于 10-8-19 23:26 发表
随便拿个答案：

Q*******
******Q*
****Q***
*******Q
*Q******
***Q****
******Q*
**Q*****

第一行和第七行找不到马步。

边缘部分的，可设想将此棋盘扩大为9倍原始大小
原始棋盘在中间，周围八个方向上棋盘的棋子摆放都与该棋盘一致
这样就能看出马步了

Q*******Q*******
******Q*
****Q***
*******Q
*Q******
***Q****
******Q*
**Q*****

比如我在右侧增加第一行，这下就能看出新增的第一行与原来的第二行之间是一个马步
同时也可以发现，第二行和第七行的皇后在同一竖线上，相互攻击了，因此你给的这个答案并不满足八皇后问题"不能互相攻击"的假设

[ 本帖最后由 lastwinner 于 2010-8-20 09:31 编辑 ]

lastwinner · 发表于 2010-8-20 09:30

事实上，第七行这么改就对了

Q*******
******Q*
****Q***
*******Q
*Q******
***Q****
*****Q**
**Q*****

这样就都能找到马步了

newkid · 发表于 2010-8-20 22:46

那个答案确实是我抄错了。

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

The Knight's Tour
	after Martin Gardner

Home / Puzzle Playground / Puzzles / Chess 'n' Checkers /

Draw the chess board shown in Figure 1 or use our special Print 'n' Play PDF Version. Place a chess knight (or a simple coin) in any cell of this board.

The object is to visit with the knight every cell of the board exactly once, and return to the initial cell where your trip began from.

Figure 2, a and b, shows some possible moves of the chess knight which always moves either one cell in one direction, and then two cells in another direction, or vice versa.

上面是一个十字形的期盼。一匹马从出发点开始，所有的棋格都访问恰好一次，最后回到起点，路线是怎样的？

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