|
|
第六题的参考SQL:
--优化：
按照先行后列的顺序选择。当新加入的格子是在新的一行，那么已经出现的行就不可能从横向进行变化了，未来只能从列的方向受影响。把此时的布局从列方向切开来看，前面一截都必须满足黑白相间的条件。比如8X8行号列号都编为 0-7, 假如新加入的格子行号为3, 那么 0-2 行的横向不会变，每列的前三格看起来都必须是“黑白黑”或者“白黑白”。
VAR N NUMBER;
EXEC :N:=8;
WITH c AS (
SELECT POWER(2,LEVEL-1) id ------- 8x8 格子按行列顺序编号0~63, 每个看作二进制的一位作唯一ID
,CEIL(LEVEL/:N)-1 R -------- 行号0~7
,MOD(LEVEL-1,:N) C -------- 列号0~7
,LEVEL-1 seq
FROM DUAL CONNECT BY LEVEL<=:N*:N
)
,goal AS (SELECT SUM(id) goal FROM c WHERE MOD(R,2)=MOD(C,2)) ---- 目标是排成黑白相间的标准棋盘，黑色的二进制位取1
,c2 AS ( ------------------------当一格被选中，同行同列全部取反，即那一位和1做XOR操作
SELECT c1.id,c1.r,c1.c,c1.seq
,SUM(c2.id) AS mask -------需要取反的那些位之和作为掩码
FROM c c1,c c2
WHERE c1.r=c2.r OR c1.c=c2.c
GROUP BY c1.id,c1.r,c1.c,c1.seq
)
,c3 AS ( ----------------- 当选择的是一个新的行，已经出现的N-1行在所有列上都必须是黑白相间的，参见上述优化思路
SELECT c1.r,c1.c
,NVL(SUM(c2.id),0) AS chk_mask
,NVL(SUM(CASE WHEN MOD(c2.R,2)=MOD(c2.C,2) THEN c2.id END),0) AS chk_goal1
,NVL(SUM(CASE WHEN MOD(c2.R,2)<>MOD(c2.C,2) THEN c2.id END),0) AS chk_goal2
FROM c c1,c c2
WHERE c2.r<c1.r AND c2.c=c1.c
GROUP BY c1.r,c1.c
)
,t(last_id,s,cnt,last_r) AS (
SELECT id,mask,0,r FROM c2 WHERE c<=r AND r<=CEIL(:N/2) ------ 由于对称，出发点仅限于1/8即可
UNION ALL
SELECT c2.id
,t.s+c2.mask - BITAND(t.s,c2.mask)*2 ----XOR
,COUNT(CASE WHEN t.s+c2.mask - BITAND(t.s,c2.mask)*2=goal THEN 1 END) OVER() ---- 答案是否已经出现
,c2.r
FROM t,c2,goal
WHERE t.last_id<c2.id AND t.cnt=0
AND (c2.r=t.last_r ------ 要么新选择的格子和上一格在同一行
OR c2.r>t.last_r AND (SELECT COUNT(*) FROM c3 WHERE c3.r=c2.r AND BITAND(t.s,c3.chk_mask) IN (c3.chk_goal1,c3.chk_goal2))=:N --- 或者新的行，则N个列的前几行都必须是黑白相间
)
)
,res AS ( ----- 取出满足结果的答案
SELECT s
FROM t
WHERE t.cnt>0 AND t.s=(SELECT goal FROM goal)
AND ROWNUM=1
)
SELECT c.seq -----把答案的每一位展开转变成0~63的格子编号
FROM res,c
WHERE BITAND(res.s,c.id)>0;
SEQ
----------
0
2
4
6
9
11
13
15
16
18
20
22
25
27
29
31
32
34
36
38
41
43
45
47
48
50
52
54
57
59
61
63
32 rows selected.
Elapsed: 00:06:12.82
|
|
楼主: newkid
IP卡
狗仔卡
楼主
显身卡
发表于 2015-9-10 08:04
