“盛拓传媒杯”SQL数据库编程大赛第二期评分及所有参赛选手答题公布！

~贝贝~

第二期答题的评审结果终于出炉了，此答题中涌现了太多的劳模啊，暴力语句，人肉法解题，冗长的代码，让评委们在崩溃的边缘完成了此次评审，让大家久等了。现在将大家的得分、评委的点评/建议、所有人的答题整理以及出题人newkid的解题思路详解内容整理发布如下：

所有答题的压缩包及得分及评语表在附件中，请大家下载！

评审结果仍以评审代号匿名公布，这期代号不以字母命名，而是在答题结束后，由论坛助理无序派予的序号，稍后我将会给第二期答题的puber发送站内短信，告知其对应的评审代号，好让大家自己能查阅到自己的对应评审结果！

评分代号	第一题得分	第二题得分	总得分	第一题评语	第二题评语
SQL2-11	77.8	37.5	115.3	列、斜线的判断方法采用移位相加的办法，很简洁，但是缺乏注释。递归的第一层做了对称优化。去除重复的思路也很新颖独特，采用的是把答案转换为8种排列后再分别转换为二进制数的办法。作者采用加法sum(bit)代替各位字符的合并操作，二进制可以比十进制表示更多的位。	第一题已经考虑了扩展性，所以第二题很轻松。
SQL2-6	79.04	35.7	114.74	代码直接而高效；最后增补的优化条件很有特点。合理的运用了count(distinct greatest(parm1,parm2..)的组合达到了简化的目的，美中不足的是注释稍后有些简单。斜边判断两个球的条件可以省略的。	通过把代码写两遍的方法来实现扩展性显得有些笨拙。第一题的优化代码在M变大的情况下就成了累赘。采用5×5和6×6叠加的办法实现，可扩展性差，整体效率也很低。
SQL2-15	77.3	35.8	113.1	性能优越。移位求和来判断列和斜线的思路很简洁，而且还追加了优化条件，但注释不够清晰。	通过递归实现变形处理，处理逻辑别出心裁，不过没有注释很难看懂。变形方法的复杂性也导致开销的上升，限制了扩展性。
SQL2-10	74.5	37	111.5	性能优越。本答案为mssql代码，结构清晰，使用递归cte来实现mssql无法实现的connect by的功能和变形逻辑。	结果无可挑剔，效率也好，可扩展性比较高，虽然是mssql版本，经过少量修改就能用于oracle，通用性不错，性能良好。
SQL2-25	75.9	35.5	111.4	该答案从扩展性到递归的运用堪称经典。移位求和来判断列和斜线的思路很简洁。在递归的同时也考虑了各种变形供后续使用。在去除重复时使用了相关子查询，若用LEAST/GREATEST的方法将更高效。	第一题已经充分考虑了扩展性，第二题只是稍微修改，并继承了所有优缺点。
SQL2-30	75.2	35	110.2	变形处理比较巧妙，但缺乏注解	结果正确，性能较好，变形处理比较巧妙
SQL2-7	75.1	34.3	109.4	思路清晰，代码较为简洁，第一个条件l1.str =greatest(l1.str, reverse(l1.str)一定程度上优化了整体执行速度。依据抽屉原则，列条件可以直接写=2。该答案的妙处在于对reverse和greatest函数的综合运用，可谓别具特色，注释部分稍显不足。	尽管filter的生成原理很费解，但是该思路十分奇妙, 用BITAND就能完成所有列和斜线的判断。matrix_t的第一层还考虑到对称的优化。在变形的时候还是采用了枚举六个列的方法，有些美中不足。
SQL2-3	73.8	35.5	109.3	在题目明显要求每行2球的情况下仍然用<=2构造可能的行排列,效率不高。yh的递归条件b.sum_h<=2有错，应该是b.sum_h+c.is_fq<=2。但是后面加了过滤条件纠正了这个错。jz的移位求和来判断斜线的思路很好，但递归条件也有类似问题，同样要靠后续的过滤解决。最后一个子查询中，没有必要把V_UID再拼起来，求出每组ANS的最大或最小即可。WMSYS.WM_CONCAT在新版本(11GR2.2)上演变为CLOB类型导致报错，改为LISTAGG之后能够运行。	第二题沿用了第一题的做法，由于采用了递归写法使得扩展性良好，但性能稍差。
SQL2-9	74.5	33.8	108.3	思路和结果正确，完全人肉法，代码写的过于复杂，代码TT1-TT6部分可用with减轻目前的臃肿程度。这代码评委看的眼花缭乱，作者写的辛苦了！	基本沿用了第一题的写法，只是对N作了5和6的判断，扩展的写法不是很好。从第一题照抄的注释要注意修改，比如“因为要放置12个球，所以每行只能2个”。
SQL2-12	75.1	32.6	107.7	作者用手工方法把所有变换的36个坐标各写一遍，显得有些辛苦，但结果是对的。该答案的亮点在于bin_to_num这个不常用的进制转换函数的应用。但bin_to_num的使用其实并没提高效率，与直接拼接为字符串的效率一样，开头拼一行两个球的不同摆法写得有些臃肿。	暴力破解的另一个典型，采用5×5和6×6叠加的办法实现，把代码写两遍的方法可扩展性差，整体效率也很低。
SQL2-27	71.6	34	105.6	该答案几乎安全采用枚举的爆破方式，结果正确，作者辛苦了！row的构造用with代替会简洁很多。	手工枚举所有变形，写得很辛苦但是结果正确。扩展性采用了DECODE的办法只适应5和6。
SQL2-29	73.5	30.5	104	采用递归和变形的方式都很有特色，但效率比较低下。在已知n和m的时候，另外引入一个=n*m的x变量没有必要，用number的字面值保存各位0/1，缺乏扩展性,如果把f_each_line <=2改为=2,则时间从23分缩短为1秒	和第一题一样的问题
SQL2-2	69.7	32.1	101.8	思路比较清晰，代码稍显臃肿，一些不必要的条件如AND A5.P1+A6.P2<=2其实是可以去掉的。使用symmetry_group实现了行列转换，变换了思路求出了结果，注释够简洁但略欠清晰。作者的思路是：每个不同的结果加上其各种变换，总共8个结果，去掉重复的之后，可能就没8种了，可能就是X种（X为8、4、2、1中的一个）。如果某结果的x种变换完全不一样，那么根据对称性，说明其他(x-1)种的不同变换也不一样，也就是其他(x-1)种变换也会被计数，所以所有的有x种不同变换的方阵个数相加，再除以x，就可以得到不重复的方阵个数了。人肉构造各种变形的解比较辛苦。	第二题沿用了第一题的做法，大部分代码重复写了两遍来达到对N=5和N=6的适应，显得比较笨拙，可扩展性较差，不过针对此题还算有效。
SQL2-22	75.7	24.9	100.6	代码过于复杂，但是思路是正确的。完全人肉法，同样的子查询写六遍，手工枚举所有变形，虽然写得辛苦但是结果正确而且效率不错。 人肉法也可以简化的，比如下面代码写了数次重复，应该用with子句保存，后面引用就简单了	程序很难读懂，效率也很低，对临时表空间要求很大，无法验证N=6，M=3的结果。
SQL2-8	77.9	19	96.9	代码简洁明了，效率极高。在递归的同时也完成了变形，十分奇妙！前面已经假定了最大个数为12,后面的max_cnt可以不要。V的第一层做了对称优化。注释不是很清楚，期待作者本人的讲解。	n=5的不重复值全错了，但n=6是正确的。
SQL2-19	77.3	15.1	92.4	本答案的解题思路堪称经典，从对正则表达式的运用到运行效率上均无可挑剔。移位求和来判断列和斜线的思路很简洁，逐行叠加的方法保证了无效数据能够尽早过滤从而提高效率。用SUM来求不重复个数的方法很独特。正则表达式有效简化了代码量，注释很清楚。若各个BLOCK如果写成WITH, 将会增强可读性。	未能实现去重复。
SQL2-23	72.8	0	72.8	MSSQL。提前过滤的思路不错，不过实现方法较为臃肿。该代码从构造全部方阵到处理变形问题均拖沓冗长。	未答第二题
SQL2-17	60.7	11.9	72.6	构造数据过于复杂，36个对象的笛卡尔积，最后剔重思路错误。按每行<=2计算的，降低了性能，注释太少了几乎未能阐明作者的思路。代码中不应包含作者ID。	还是和1的构造差不多，笛卡尔积太多。写的巨复杂，太辛苦了，真是佩服。可惜思路有误，先求出所有的结果，然后再选择，显然在速度上是无法忍受的，同学，你怎么能怎么能这样做！！！
SQL2-21	49.8	16.3	66.1	正确求出重复的总记录数，但去重复的结果错误。方案A与方案B沿中心横线对称或旋转相同，则sumx = sumy 并且sumz=sumw; 对角线对称，则sumx=sumz 或 sumy=sumw;并不满足剔重条件。另外，PL/SQL答题不符合要求。	和第一题一样的问题
SQL2-14	45.7	18.1	63.8	按每行<=2计算的，降低了性能，变换不完全正确【绕中心顺时针旋转270度 与 左上右下对角线对称 重复，上下半对称和左右半对称非要求的变换】。用PM中的代码可以得到正确的结果。	没有做变换也没有去除重复。
SQL2-13	41.2	17.4	58.6	本代码也属暴力性和苦力性的，而且最终变形错误。代码过于臃肿，判断逻辑过于复杂，变形算法有误导致最终结果错误，很可惜。	仅m=1时结果正确，其他结果均错，很可惜了长长的代码。
SQL2-4	57.1	0	57.1	tab4的移位求和来判断斜线的思路很好。列别名取得有些费解且未加注释。判断重复的逻辑有错, 只是在同一种答案的各种变形之中去重复，而不是在不同答案之间去重复。不过最后剔重理解错误，导致结果错误，可惜！另外代码格式化较差，命名方式不容易懂。	未答第二题
SQL2-1	53.4	0	53.4	答题求出所有排列的结果是对的，求变形的结果也是对的，而且利用正反行列组合求各种变形的思路很不错，但在最后如何计算不重复时出错了，属于题意没理解清楚，否则当是上作。。另外，题目已经指定了每行两个球，那就不必在行列上再用<=2的条件了，如果把行列和<=2改为=2，则时间从8分14.39秒缩短为7.94秒。1分18.42秒得出了错误的结果	未答第二题
SQL2-24	35.9	16	51.9	求出了正确带重复的总记录数，但没能求出去重复的结果	用绑定变量实现了简单的重复计算，但未实现去重，而且两个棋盘也用了两条SQL去做，不符合题目要求。
SQL2-28	35.4	14.2	49.6	求出了正确带重复的总记录数，但没能求出去重复的结果。未利用=2的条件而是采用了<=2，降低了性能，另外，未求出各种变换，最后当然也就无法去重了。	性能较差，没有去除重复结果。
SQL2-18	32	13.3	45.3	本答案的总体求解思路是正确的，但一开始的重复组合即出现了问题。2^36里找符合条件的结果，性能较低，变形中有错误，后续去重的思路不正确，结果错误。作者似乎想利用 where substr(str,1,3)>1 去掉左右翻转后重复的变换，但这样其实将一些符合条件的结果也给过滤掉了，一开始的这个错误，导致后面无论怎么做，其实结果都不会对。	与第1题的思路类似，同样的问题导致结果不正确。
SQL2-5	44.7	0	44.7	代码正确的列举了两个球的15种摆法和全部的方阵算法，但是最后的剔重错误。复杂注释太少代码未格式化，代码可读性不高。构造一行6个球的sql过于臃肿，用1出现的位置坐标来判断是否超过两个球的做法也是不错的，不过多层函数嵌套导致了效率低下。通过count(distinct(least(p1,p2,...,pn)))的方式去求不重复的思路是正确的，尽管一层一层的套用distinct(least(p1,p2,...,pn))显得罗嗦，然而最致命的是每次变换都在上一次的结果上进行，还将所有变换都挨个执行了一遍，显然成就了一个悲剧……	未答第二题
SQL2-20	31.4	10	41.4	SQL语法有错误，未能正常运行。最后改为“SELECT :m M, :n N, count(*) "AllCnt" from che union select :m M, :n N, count(*) "NoReptCnt" FROM che_4” 后可以运行，但算法不对导致结果错误	SQL错误，无法运行，即便修改后的结果也是错误的
SQL2-16	35.5	0	35.5	代码拖沓冗长过于复杂，求出了正确带重复的总记录数，但未能求出各种变换，自然也就无法达到去重复的要求。tab的构造比较笨拙，主查询用的判断方法也很繁复。	未答第二题
SQL2-26	19.6	11.1	30.7	没有给出需要的临时表，语句不能独立运行，评委按照注释提示提供了临时表后，11分36.49秒得出了错误的结果。但借助外部表，不符合答题要求。建表后，运行结果是错的，这是因为作者斜线上判断条件不足造成的，可能是题意理解错误导致的。	和第一题一样的问题

附上此次SQL大赛活动相关链接，目前第四期答题正在进行中，期待更多人参与答题：
第四期SQL大赛活动链接（正在进行中）：http://www.itpub.net/thread-1411495-1-1.html
第三期SQL大赛活动链接：http://www.itpub.net/thread-1408182-1-1.html
第二期SQL大赛活动链接：http://www.itpub.net/thread-1403356-1-1.html
第一期SQL大赛活动链接：http://www.itpub.net/thread-1400067-1-1.html
SQL数据库编程大赛第一期评分及所有答题公布链接：http://www.itpub.net/thread-1407072-1-1.html

~贝贝~

此题newkid解题思路总结公布如下，另此贴还附上此解题思路的文档下载，方便大家查阅：

本期题目是在上期基础上要求去除重复解。重复的定义在题目中已经说得很清楚了，现在的任务是如何判断两个解是否重复。如果我们能够找到一种方法，为两个重复的解赋予同样的一个特征值，那么只要算一下总共有多少个不同的特征值COUNT(DISTINCT)就可以了。通过观察我们可以得到八种变形（连同自身）的座标变换公式，如果两个答案重复，它们变换出来的8种将会是同一个集合，只是集合中的顺序可能不同。不重复的答案则变换之后也没有交集。通过给这个集合排序，取其中最大或最小值，可以判断是否重复。重复的答案将会取到相同的最大（或最小）值，这个就是我们要的特征值。
上述结论没有严格证明，数学爱好者可以做一下证明。
技术上实现八种变换的难度不大，只是比较繁琐。因为无非就是座标的换算，我们先把所有解法编号answer_id，每个解法拆开为N*N行，每行带有0,1值及其座标，然后对其座标做8种变换运算，再按运算后的顺序重新组合为一个字符串。这样原来的一个字符串就变成了八个，每个字符串都对应原来的解法编号answer_id。只要用MIN(或者MAX)... GROUP BY answer_id就可以得到这个特征值，再进行计数即可。
下面就是这个思路的5X5放两个球的示例：

1. WITH d AS (    ---------- 一行里放两个球，这两个球所处的列位置的所有组合。这里尝试了和上面不一样的写法。
   
2. SELECT s ---- 下面的c1到c5表示该列有没有球
   
3.       ,SUBSTR(s,1,1) c1,SUBSTR(s,2,1) c2,SUBSTR(s,3,1) c3,SUBSTR(s,4,1) c4,SUBSTR(s,5,1) c5
   
4.   FROM (SELECT RPAD(LPAD('1',n1,'0')||LPAD('1',n2-n1,'0'),:N,'0') s    ---- LPAD, RPAD用于在空位置填入0
   
5.           FROM (SELECT ROWNUM n1 FROM DUAL CONNECT BY ROWNUM<=:N)
   
6.               ,(SELECT ROWNUM n2 FROM DUAL CONNECT BY ROWNUM<=:N)
   
7.          WHERE n1<n2
   
8.        )
   
9. )
   
10. ,m AS (
    
11. SELECT answer_id
    
12.       ,SUBSTR(str,seq,1) AS val
    
13.       ,CEIL(seq/5) r    ---- 行号
    
14.       ,MOD(seq-1,5)+1 c ---- 列号
    
15.   FROM (SELECT ROWNUM answer_id
    
16.               ,d1.s||d2.s||d3.s||d4.s||d5.s str
    
17.           FROM d d1,d d2,d d3,d d4,d d5     -------- 下面d1-d5表示第1-5行。这些行里面的球的位置，都来自于d
    
18.          WHERE d1.c1+d2.c1+d3.c1+d4.c1+d5.c1=2 ------- 竖线，所有行的第一列的总球数
    
19.            AND d1.c2+d2.c2+d3.c2+d4.c2+d5.c2=2
    
20.            AND d1.c3+d2.c3+d3.c3+d4.c3+d5.c3=2
    
21.            AND d1.c4+d2.c4+d3.c4+d4.c4+d5.c4=2
    
22.            AND d1.c5+d2.c5+d3.c5+d4.c5+d5.c5=2
    
23.            AND d1.c3+d2.c2+d3.c1            <=2 ------- 右上到左下的斜线, 13,22,31 ---- 坐标13表示1行3列，下同
    
24.            AND d1.c4+d2.c3+d3.c2+d4.c1      <=2 ------- 右上到左下的斜线, 14,23,32,41
    
25.            AND d1.c5+d2.c4+d3.c3+d4.c2+d5.c1<=2 ------- 右上到左下的斜线, 15,24,33,42,51
    
26.            AND       d2.c5+d3.c4+d4.c3+d5.c2<=2 ------- 右上到左下的斜线, 25,34,43,52   
    
27.            AND             d3.c5+d4.c4+d5.c3<=2 ------- 右上到左下的斜线, 35,44,53      
    
28.            AND d1.c3+d2.c4+d3.c5            <=2 ------- 左上到右下的斜线, 13,24,35
    
29.            AND d1.c2+d2.c3+d3.c4+d4.c5      <=2 ------- 左上到右下的斜线, 12,23,34,45
    
30.            AND d1.c1+d2.c2+d3.c3+d4.c4+d5.c5<=2 ------- 左上到右下的斜线, 11,22,33,44,55
    
31.            AND       d2.c1+d3.c2+d4.c3+d5.c4<=2 ------- 左上到右下的斜线, 21,32,43,54
    
32.            AND             d3.c1+d4.c2+d5.c3<=2 ------- 左上到右下的斜线, 31,42,53
    
33.        )
    
34.       ,(SELECT ROWNUM seq FROM DUAL CONNECT BY ROWNUM<=25) ---- 用于把1行拆为
    
35. )
    
36. ,m2 AS (
    
37. SELECT answer_id,0 AS m_type,val,r,c FROM m       ----- m_type=0: 未经变换
    
38. UNION ALL
    
39. SELECT answer_id,1 AS m_type,val,r,6-c FROM m     ----- m_type=1: 沿竖线中轴对折
    
40. UNION ALL
    
41. SELECT answer_id,2 AS m_type,val,6-r,c FROM m     ----- m_type=2: 沿横线中轴对折
    
42. UNION ALL
    
43. SELECT answer_id,3 AS m_type,val,6-r,6-c FROM m   ----- m_type=3: 2,3 的叠加, 或顺时针180度
    
44. UNION ALL
    
45. SELECT answer_id,4 AS m_type,val,c,r FROM m       ----- m_type=4: 以左上至右下斜线为轴对折
    
46. UNION ALL
    
47. SELECT answer_id,5 AS m_type,val,6-c,6-r FROM m   ----- m_type=5: 以右上至左下斜线为轴对折
    
48. UNION ALL
    
49. SELECT answer_id,6 AS m_type,val,c,6-r FROM m     ----- m_type=6: 顺时针90度
    
50. UNION ALL
    
51. SELECT answer_id,7 AS m_type,val,6-c,r FROM m     ----- m_type=7: 逆时针90度
    
52. )
    
53. ,m3 AS (
    
54. SELECT answer_id
    
55.       ,MIN(SYS_CONNECT_BY_PATH(val,' ')) matrix_str  --- 用CONNECT BY进行字符串拼接，取最小值作为8种变换的共同特征值
    
56.   FROM m2
    
57. WHERE r=5 AND c=5
    
58. START WITH c=1 AND r=1
    
59. CONNECT BY answer_id = PRIOR answer_id
    
60.            AND m_type = PRIOR m_type
    
61.            AND (r = PRIOR r AND c = PRIOR c+1
    
62.                 OR r = PRIOR r+1 AND c=1 AND PRIOR c=5
    
63.                )
    
64. GROUP BY answer_id
    
65. )
    
66. SELECT COUNT(DISTINCT matrix_str) distinct_cnt,COUNT(*) all_cnt
    
67.   FROM m3;
    
68. 上述思路可以改良一下，当我们把一个解拆为N*N行时，那些没有球的格子可以过滤掉，这样一个解只拆成10行，在做座标变换的时候计算量会少一些。采用这方法，最后拼字符串就有所不同，因为我们只有1没有0, 下面展示了一种利用十进制的加法来拼字符串的技巧。
    
69. WITH d AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
    
70. SELECT s ---- 下面的c1到c5表示该列有没有球
    
71.       ,SUBSTR(s,1,1) c1,SUBSTR(s,2,1) c2,SUBSTR(s,3,1) c3,SUBSTR(s,4,1) c4,SUBSTR(s,5,1) c5
    
72.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
    
73.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
    
74.          WHERE LEVEL=:N
    
75.         CONNECT BY LEVEL<=:N
    
76.        )
    
77. WHERE LENGTH(s)-NVL(LENGTH(REPLACE(s,'1')),0)=:M
    
78. )
    
79. ,m AS (
    
80. SELECT answer_id
    
81.       ,CEIL(seq/5) r    ---- 行号
    
82.       ,MOD(seq-1,5)+1 c ---- 列号
    
83.   FROM (SELECT ROWNUM answer_id
    
84.               ,d1.s||d2.s||d3.s||d4.s||d5.s str
    
85.           FROM d d1,d d2,d d3,d d4,d d5     -------- 下面d1-d5表示第1-5行。这些行里面的球的位置，都来自于d
    
86.          WHERE d1.c1+d2.c1+d3.c1+d4.c1+d5.c1=2 ------- 竖线，所有行的第一列的总球数
    
87.            AND d1.c2+d2.c2+d3.c2+d4.c2+d5.c2=2
    
88.            AND d1.c3+d2.c3+d3.c3+d4.c3+d5.c3=2
    
89.            AND d1.c4+d2.c4+d3.c4+d4.c4+d5.c4=2
    
90.            AND d1.c5+d2.c5+d3.c5+d4.c5+d5.c5=2
    
91.            AND d1.c3+d2.c2+d3.c1            <=2 ------- 右上到左下的斜线, 13,22,31 ---- 坐标13表示1行3列，下同
    
92.            AND d1.c4+d2.c3+d3.c2+d4.c1      <=2 ------- 右上到左下的斜线, 14,23,32,41
    
93.            AND d1.c5+d2.c4+d3.c3+d4.c2+d5.c1<=2 ------- 右上到左下的斜线, 15,24,33,42,51
    
94.            AND       d2.c5+d3.c4+d4.c3+d5.c2<=2 ------- 右上到左下的斜线, 25,34,43,52   
    
95.            AND             d3.c5+d4.c4+d5.c3<=2 ------- 右上到左下的斜线, 35,44,53      
    
96.            AND d1.c3+d2.c4+d3.c5            <=2 ------- 左上到右下的斜线, 13,24,35
    
97.            AND d1.c2+d2.c3+d3.c4+d4.c5      <=2 ------- 左上到右下的斜线, 12,23,34,45
    
98.            AND d1.c1+d2.c2+d3.c3+d4.c4+d5.c5<=2 ------- 左上到右下的斜线, 11,22,33,44,55
    
99.            AND       d2.c1+d3.c2+d4.c3+d5.c4<=2 ------- 左上到右下的斜线, 21,32,43,54
    
100.            AND             d3.c1+d4.c2+d5.c3<=2 ------- 左上到右下的斜线, 31,42,53
     
101.        )
     
102.       ,(SELECT ROWNUM seq FROM DUAL CONNECT BY ROWNUM<=25) ---- 用于把1行拆为
     
103. WHERE SUBSTR(str,seq,1)=1  ------- 只留下有球的格子
     
104. )
     
105. ,m2 AS (
     
106. SELECT answer_id,0 AS m_type,r,c FROM m       ----- m_type=0: 未经变换
     
107. UNION ALL
     
108. SELECT answer_id,1 AS m_type,r,6-c FROM m     ----- m_type=1: 沿竖线中轴对折
     
109. UNION ALL
     
110. SELECT answer_id,2 AS m_type,6-r,c FROM m     ----- m_type=2: 沿横线中轴对折
     
111. UNION ALL
     
112. SELECT answer_id,3 AS m_type,6-r,6-c FROM m   ----- m_type=3: 2,3 的叠加, 或顺时针180度
     
113. UNION ALL
     
114. SELECT answer_id,4 AS m_type,c,r FROM m       ----- m_type=4: 以左上至右下斜线为轴对折
     
115. UNION ALL
     
116. SELECT answer_id,5 AS m_type,6-c,6-r FROM m   ----- m_type=5: 以右上至左下斜线为轴对折
     
117. UNION ALL
     
118. SELECT answer_id,6 AS m_type,c,6-r FROM m     ----- m_type=6: 顺时针90度
     
119. UNION ALL
     
120. SELECT answer_id,7 AS m_type,6-c,r FROM m     ----- m_type=7: 逆时针90度
     
121. )
     
122. ,m3 AS (
     
123. SELECT MIN(s) AS matrix_str -- 取最小值作为8种变换的共同特征值
     
124.   FROM (SELECT answer_id,m_type
     
125.               ,LPAD(SUM(POWER(10,:N*(:N-r) + :N-c)),:N*:N,'0') s  ---- 小技巧：利用10的幂对该位置1，间接达到拼字符串的目的, 假设所有位数仍在NUMBER支持之内
     
126.           FROM m2
     
127.         GROUP BY answer_id,m_type
     
128.        )
     
129. GROUP BY answer_id
     
130. )
     
131. SELECT COUNT(DISTINCT matrix_str) distinct_cnt,COUNT(*) all_cnt
     
132.   FROM m3;
     
133. 上述方法都是把一个解拆开后再作座标运算，然后又拼回来。有没有一种方法可以不拆开，一下子就完成字符串的重排列呢？这里我要隆重推荐〇〇发明的TRANSLATE办法：
     
134. TRANSLATE(expr, from_string, to_string)
     
135. 它的作用是把一个字符串expr里面的字符作一个映射变换，而原来的字符顺序保持不变。如果expr是from_string的重新排列，会怎么样呢？它其实相当于会把to_string重新排列！
     
136. 观察下列例子：
     
137. SELECT TRANSLATE('bdca','abcd','1234') from dual;
     
138. TRAN
     
139. ----
     
140. 2431
     
141. 假设abcd是对原排列顺序的一种抽象表示，bdca表示我们要的新排列顺序，它对1234的作用就是重新排成了2431。这实在是太巧妙了。以5X5为例，我们可以用abcdefghijklmnopqrstuvwxy表示原顺序，把其他7种顺序手工列举出来，作为TRANSLATE的模版：
     
142. WITH d AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
     
143. SELECT s ---- 下面的c1到c5表示该列有没有球
     
144.       ,SUBSTR(s,1,1) c1,SUBSTR(s,2,1) c2,SUBSTR(s,3,1) c3,SUBSTR(s,4,1) c4,SUBSTR(s,5,1) c5
     
145.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
     
146.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
     
147.          WHERE LEVEL=:N
     
148.         CONNECT BY LEVEL<=:N
     
149.        )
     
150. WHERE LENGTH(s)-NVL(LENGTH(REPLACE(s,'1')),0)=:M
     
151. )
     
152. ,m AS ( SELECT ROWNUM answer_id
     
153.               ,d1.s||d2.s||d3.s||d4.s||d5.s s
     
154.           FROM d d1,d d2,d d3,d d4,d d5     -------- 下面d1-d5表示第1-5行。这些行里面的球的位置，都来自于d
     
155.          WHERE d1.c1+d2.c1+d3.c1+d4.c1+d5.c1=2 ------- 竖线，所有行的第一列的总球数
     
156.            AND d1.c2+d2.c2+d3.c2+d4.c2+d5.c2=2
     
157.            AND d1.c3+d2.c3+d3.c3+d4.c3+d5.c3=2
     
158.            AND d1.c4+d2.c4+d3.c4+d4.c4+d5.c4=2
     
159.            AND d1.c5+d2.c5+d3.c5+d4.c5+d5.c5=2
     
160.            AND d1.c3+d2.c2+d3.c1            <=2 ------- 右上到左下的斜线, 13,22,31 ---- 坐标13表示1行3列，下同
     
161.            AND d1.c4+d2.c3+d3.c2+d4.c1      <=2 ------- 右上到左下的斜线, 14,23,32,41
     
162.            AND d1.c5+d2.c4+d3.c3+d4.c2+d5.c1<=2 ------- 右上到左下的斜线, 15,24,33,42,51
     
163.            AND       d2.c5+d3.c4+d4.c3+d5.c2<=2 ------- 右上到左下的斜线, 25,34,43,52   
     
164.            AND             d3.c5+d4.c4+d5.c3<=2 ------- 右上到左下的斜线, 35,44,53      
     
165.            AND d1.c3+d2.c4+d3.c5            <=2 ------- 左上到右下的斜线, 13,24,35
     
166.            AND d1.c2+d2.c3+d3.c4+d4.c5      <=2 ------- 左上到右下的斜线, 12,23,34,45
     
167.            AND d1.c1+d2.c2+d3.c3+d4.c4+d5.c5<=2 ------- 左上到右下的斜线, 11,22,33,44,55
     
168.            AND       d2.c1+d3.c2+d4.c3+d5.c4<=2 ------- 左上到右下的斜线, 21,32,43,54
     
169.            AND             d3.c1+d4.c2+d5.c3<=2 ------- 左上到右下的斜线, 31,42,53
     
170. )
     
171. ,h as (    ----- 这里也可以用UNION ALL写7行，最后MIN/MAX+GROUP BY
     
172. select 'abcdefghijklmnopqrstuvwxy'  org  --原始
     
173.       ,'edcbajihgfonmlktsrqpyxwvu'  m1
     
174.       ,'uvwxypqrstklmnofghijabcde'  m2
     
175.       ,'yxwvutsrqponmlkjihgfedcba'  m3  --旋转180度
     
176.       ,'upkfavqlgbwrmhcxsnidytoje'  m4  --旋转90度
     
177.       ,'ejotydinsxchmrwbglqvafkpu'  m5  --旋转270度
     
178.       ,'afkpubglqvchmrwdinsxejoty'  m6  --按左上右下对角线对称
     
179.       ,'ytojexsnidwrmhcvqlgbupkfa'  m7  --按右上左下对角线对称
     
180.   FROM DUAL
     
181.   )
     
182. SELECT COUNT(DISTINCT
     
183.        GREATEST(s  
     
184.                ,translate(m1,org,s) -------- 各种对称位置的重排模版，每种模版都会把S里面的0和1重新排列
     
185.                ,translate(m2,org,s)
     
186.                ,translate(m3,org,s)
     
187.                ,translate(m4,org,s)
     
188.                ,translate(m5,org,s)
     
189.                ,translate(m6,org,s)
     
190.                ,translate(m7,org,s)
     
191.                )
     
192.        ) AS distinct_cnt
     
193.       ,COUNT(*) AS all_cnt
     
194.   FROM m,h
     
195. ;
     
196. 虽然手工写七种模版有些辛苦，但这个新思路令人振奋。其实，结合前面一种方法，我们可以自动生成这8种模版，因为它就是对任意一个字符串（原始顺序）进行座标变换然后再拼接起来。因为只有一个原始串，所以计算量很小，比原来对所有结果进行座标运算要好得多。而变换完的模版就可以被后来利用了。这种自动生成模版的方法，还可以应用于不同的M值。
     
197. 下面就把第一期的递归WITH写法，连同这种自动生成TRANSLATE模版的思路结合起来：
     
198. var m number;
     
199. exec :m:=2
     
200. var n number;
     
201. exec :n:=6
     
202. WITH r AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
     
203. SELECT s as one_row
     
204.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
     
205.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
     
206.          WHERE LEVEL=:N
     
207.         CONNECT BY LEVEL<=:N
     
208.        )
     
209. WHERE LENGTH(s)-LENGTH(REPLACE(s,'1'))=:M
     
210. )
     
211. ,balls (row_cnt    -- 当前行数
     
212.        ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
     
213.        ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
     
214.        ,diag_cnt1  -- 此数字表示在右上至左下的斜线上各位的和
     
215.        ,diag_cnt2  -- 此数字表示在左上至右下的斜线上各位的和
     
216.        )
     
217. AS (
     
218.    SELECT 1,one_row,TO_NUMBER(one_row),TO_NUMBER(one_row),TO_NUMBER(one_row) ---初始化第一行数据
     
219.      FROM r
     
220.    UNION ALL
     
221.    SELECT balls.row_cnt+1  ---- 行数递增
     
222.          ,balls.all_rows||r.one_row  ---当前行拼入总结果
     
223.          ,balls.col_cnt+r.one_row    --- 在列方向各位进行累加
     
224.          ,balls.diag_cnt1*10+r.one_row  ---- 在斜线方向各位进行累加
     
225.          ,balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt)
     
226.      FROM balls,r
     
227.     WHERE balls.row_cnt<:N ---- 递归出口
     
228.           AND INSTR(balls.col_cnt+r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
229.           AND INSTR(balls.diag_cnt1*10+r.one_row,:M+1)=0
     
230.           AND INSTR(balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt),:M+1)=0
     
231. )
     
232. ,m AS (
     
233.   SELECT CEIL(LEVEL/:N) r
     
234.         ,MOD(LEVEL-1,:N)+1 c
     
235.         ,LEVEL seq
     
236.     FROM DUAL
     
237.    CONNECT BY LEVEL<=:N*:N
     
238. )
     
239. ,m2 AS (
     
240. SELECT seq,0 AS tpl_id,r,c FROM m       ----- tpl_id=0: 原样
     
241. UNION ALL
     
242. SELECT seq,1 AS tpl_id,r,:N+1-c FROM m       ----- tpl_id=1: 沿竖线中轴对折
     
243. UNION ALL
     
244. SELECT seq,2 AS tpl_id,:N+1-r,c FROM m       ----- tpl_id=2: 沿横线中轴对折
     
245. UNION ALL
     
246. SELECT seq,3 AS tpl_id,:N+1-r,:N+1-c FROM m       ----- tpl_id=3: 1,2 的叠加, 或顺时针180度
     
247. UNION ALL
     
248. SELECT seq,4 AS tpl_id,c,r FROM m       ----- tpl_id=4: 以左上至右下斜线为轴对折
     
249. UNION ALL
     
250. SELECT seq,5 AS tpl_id,:N+1-c,:N+1-r FROM m       ----- tpl_id=5: 以右上至左下斜线为轴对折
     
251. UNION ALL
     
252. SELECT seq,6 AS tpl_id,c,:N+1-r FROM m       ----- tpl_id=6: 顺时针90度
     
253. UNION ALL
     
254. SELECT seq,7 AS tpl_id,:N+1-c,r FROM m       ----- tpl_id=7: 逆时针90度
     
255. )
     
256. ,templates AS (
     
257. SELECT tpl_id
     
258.       ,tpl_str
     
259.       ,MAX(CASE WHEN tpl_id=0 THEN tpl_str END) OVER() AS tpl_org
     
260.   FROM (SELECT m2.tpl_id
     
261.               ,REPLACE(SYS_CONNECT_BY_PATH(all_chars.ch,'/'),'/') tpl_str ----- 拼接模版
     
262.           FROM m2
     
263.                JOIN (SELECT ROWNUM seq
     
264.                            ,ch
     
265.                        FROM (SELECT CHR(LEVEL) ch ----- 用ASCII码表作为模板. 0,1要排除掉,斜杠/作为分隔符也要排除
     
266.                                FROM DUAL
     
267.                               WHERE CHR(LEVEL) NOT IN ('0','1','/')
     
268.                               CONNECT BY LEVEL<=255
     
269.                             )
     
270.                     ) all_chars
     
271.                ON m2.seq = all_chars.seq
     
272.          WHERE LEVEL = :N*:N
     
273.         START WITH r=1
     
274.         CONNECT BY tpl_id = PRIOR tpl_id  ---- 同一种模版
     
275.                    AND (PRIOR c <:N AND r=PRIOR r AND c = PRIOR c+1   ---- 同一行的下一列
     
276.                         OR PRIOR c =:N AND r=PRIOR r+1 AND c = 1  ---- 下一行的第一列
     
277.                         )
     
278.        )
     
279. )
     
280. SELECT COUNT(DISTINCT matrix_str) AS  distinct_cnt, MAX(all_cnt) all_cnt
     
281.   FROM (SELECT  MIN(TRANSLATE(tpl_str,tpl_org,all_rows)) AS matrix_str
     
282.                ,MAX(all_cnt) all_cnt
     
283.           FROM (SELECT ROWNUM AS answer_id
     
284.                       ,all_rows
     
285.                       ,COUNT(*) OVER() AS all_cnt
     
286.                  FROM balls
     
287.                 WHERE row_cnt=:N
     
288.                ) CROSS JOIN templates
     
289.          GROUP BY answer_id
     
290.          );
     
291. 如果纯粹是要求不重复的解，那么有些明显是对称的解就可以事先排除掉。比如在递归的第一层，那些左右对称的很容易识别出来，一下子就砍掉一半。到最后一层，上下对称的也可以识别出来，也可以去掉一半。这样剩下的去重复工作量就小得多了。这个优化办法也是〇〇贡献出来的，优化之后执行时间差不多只有原来的一半。这个优化方法保证了所有不重复解都被覆盖到，但它的中间结果并没有求出所有的解，而仅仅是一个子集。要还原出所有的解也很简单，在8次变换之后就会覆盖所有的解，在此基础上去除重复就是了:
     
292. WITH r AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
     
293. SELECT s as one_row
     
294.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
     
295.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
     
296.          WHERE LEVEL=:N
     
297.         CONNECT BY LEVEL<=:N
     
298.        )
     
299. WHERE LENGTH(s)-LENGTH(REPLACE(s,'1'))=:M
     
300. )
     
301. ,balls (row_cnt    -- 当前行数
     
302.        ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
     
303.        ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
     
304.        ,diag_cnt1  -- 此数字表示在右上至左下的斜线上各位的和
     
305.        ,diag_cnt2  -- 此数字表示在左上至右下的斜线上各位的和
     
306.        )
     
307. AS (
     
308.    SELECT 1,one_row,TO_NUMBER(one_row),TO_NUMBER(one_row),TO_NUMBER(one_row) ---初始化第一行数据
     
309.      FROM r where one_row>=reverse(one_row) --左右镜像取大
     
310.    UNION ALL
     
311.    SELECT balls.row_cnt+1  ---- 行数递增
     
312.          ,balls.all_rows||r.one_row  ---当前行拼入总结果
     
313.          ,balls.col_cnt+r.one_row    --- 在列方向各位进行累加
     
314.          ,balls.diag_cnt1*10+r.one_row  ---- 在斜线方向各位进行累加
     
315.          ,balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt)
     
316.      FROM balls,r
     
317.     WHERE balls.all_rows >= case when balls.row_cnt=:n-1 then r.one_row else '0' end --上下镜像取大
     
318.           and balls.row_cnt<:N ---- 递归出口
     
319.           AND INSTR(balls.col_cnt+r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
320.           AND INSTR(balls.diag_cnt1*10+r.one_row,:M+1)=0
     
321.           AND INSTR(balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt),:M+1)=0
     
322. )
     
323. ,m AS (
     
324.   SELECT CEIL(LEVEL/:N) r
     
325.         ,MOD(LEVEL-1,:N)+1 c
     
326.         ,LEVEL seq
     
327.     FROM DUAL
     
328.    CONNECT BY LEVEL<=:N*:N
     
329. )
     
330. ,m2 AS (
     
331. SELECT seq,0 AS tpl_id,r,c FROM m       ----- tpl_id=0: 原样
     
332. UNION ALL
     
333. SELECT seq,1 AS tpl_id,r,:N+1-c FROM m       ----- tpl_id=1: 沿竖线中轴对折
     
334. UNION ALL
     
335. SELECT seq,2 AS tpl_id,:N+1-r,c FROM m       ----- tpl_id=2: 沿横线中轴对折
     
336. UNION ALL
     
337. SELECT seq,3 AS tpl_id,:N+1-r,:N+1-c FROM m       ----- tpl_id=3: 1,2 的叠加, 或顺时针180度
     
338. UNION ALL
     
339. SELECT seq,4 AS tpl_id,c,r FROM m       ----- tpl_id=4: 以左上至右下斜线为轴对折
     
340. UNION ALL
     
341. SELECT seq,5 AS tpl_id,:N+1-c,:N+1-r FROM m       ----- tpl_id=5: 以右上至左下斜线为轴对折
     
342. UNION ALL
     
343. SELECT seq,6 AS tpl_id,c,:N+1-r FROM m       ----- tpl_id=6: 顺时针90度
     
344. UNION ALL
     
345. SELECT seq,7 AS tpl_id,:N+1-c,r FROM m       ----- tpl_id=7: 逆时针90度
     
346. )
     
347. ,templates AS (
     
348. SELECT tpl_id
     
349.       ,tpl_str
     
350.       ,MAX(CASE WHEN tpl_id=0 THEN tpl_str END) OVER() AS tpl_org
     
351.   FROM (SELECT m2.tpl_id
     
352.               ,REPLACE(SYS_CONNECT_BY_PATH(all_chars.ch,'/'),'/') tpl_str ----- 拼接模版
     
353.           FROM m2
     
354.                JOIN (SELECT ROWNUM seq
     
355.                            ,ch
     
356.                        FROM (SELECT CHR(LEVEL) ch ----- 用ASCII码表作为模板. 0,1要排除掉,斜杠/作为分隔符也要排除
     
357.                                FROM DUAL
     
358.                               WHERE CHR(LEVEL) NOT IN ('0','1','/')
     
359.                               CONNECT BY LEVEL<=255
     
360.                             )
     
361.                     ) all_chars
     
362.                ON m2.seq = all_chars.seq
     
363.          WHERE LEVEL = :N*:N
     
364.         START WITH r=1
     
365.         CONNECT BY tpl_id = PRIOR tpl_id  ---- 同一种模版
     
366.                    AND (PRIOR c <:N AND r=PRIOR r AND c = PRIOR c+1   ---- 同一行的下一列
     
367.                         OR PRIOR c =:N AND r=PRIOR r+1 AND c = 1  ---- 下一行的第一列
     
368.                         )
     
369.        )
     
370. )
     
371. SELECT COUNT(DISTINCT transformed),MAX(all_cnt)
     
372.   FROM (SELECT answer_id,MIN(transformed) transformed,MAX(all_cnt) all_cnt
     
373.           FROM (SELECT answer_id,transformed,COUNT(DISTINCT transformed) OVER() all_cnt
     
374.                   FROM (SELECT answer_id,TRANSLATE(tpl_str,tpl_org,all_rows) transformed
     
375.                           FROM  (SELECT ROWNUM AS answer_id
     
376.                                        ,all_rows
     
377.                                   FROM balls
     
378.                                  WHERE row_cnt=:N
     
379.                                  ) CROSS JOIN templates
     
380.                         )
     
381.                )
     
382.         GROUP BY answer_id
     
383.        );
     
384. 在第一期讲评时我们提到了一种手工模拟递归WITH的方法，下面就展示这种写法，在做变换的时候对模版做了一个行转列，这样原来的8行模版就变为一行，再用LEAST或GREATEST来代替MIN/MAX, 这种做法的好处是不会产生很大的中间结果。缺点就是当采用对称优化求不重复的解，需要在此基础上再对8行的模版做一个笛卡尔积再次进行转换，还原所有的解，但转换的成本很低，值得采用。
     
385. EXEC :M:=2;
     
386. EXEC :N:=7;
     
387. WITH r AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
     
388. SELECT s as one_row
     
389.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
     
390.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
     
391.          WHERE LEVEL=:N
     
392.         CONNECT BY LEVEL<=:N
     
393.        )
     
394. WHERE LENGTH(s)-LENGTH(REPLACE(s,'1'))=:M
     
395. )
     
396. ,b1 AS (
     
397.    SELECT 1 row_num,one_row all_rows,TO_NUMBER(one_row) col_cnt,TO_NUMBER(one_row) diag_cnt1,TO_NUMBER(one_row) diag_cnt2---初始化第一行数据
     
398.      FROM r where one_row>=reverse(one_row) --左右镜像取大
     
399.    )
     
400. ,b2 AS (
     
401.    SELECT b.row_num+1                                      AS row_num
     
402.          ,b.all_rows||r.one_row                            AS all_rows
     
403.          ,b.col_cnt+r.one_row                              AS col_cnt
     
404.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
405.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
406.      FROM b1 b,r
     
407.     WHERE     INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
408.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
409.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
410. )
     
411. ,b3 AS (
     
412.    SELECT b.row_num+1                                      AS row_num
     
413.          ,b.all_rows||r.one_row                            AS all_rows
     
414.          ,b.col_cnt+r.one_row                              AS col_cnt
     
415.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
416.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
417.      FROM b2 b,r
     
418.     WHERE     INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
419.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
420.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
421. )
     
422. ,b4 AS (
     
423.    SELECT b.row_num+1                                      AS row_num
     
424.          ,b.all_rows||r.one_row                            AS all_rows
     
425.          ,b.col_cnt+r.one_row                              AS col_cnt
     
426.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
427.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
428.      FROM b3 b,r
     
429.     WHERE     INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
430.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
431.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
432. )
     
433. ,b5 AS (
     
434.    SELECT b.row_num+1                                      AS row_num
     
435.          ,b.all_rows||r.one_row                            AS all_rows
     
436.          ,b.col_cnt+r.one_row                              AS col_cnt
     
437.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
438.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
439.      FROM b4 b,r
     
440.     WHERE     INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
441.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
442.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
443. )
     
444. ,b6 AS (
     
445.    SELECT b.row_num+1                                      AS row_num
     
446.          ,b.all_rows||r.one_row                            AS all_rows
     
447.          ,b.col_cnt+r.one_row                              AS col_cnt
     
448.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
449.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
450.      FROM b5 b,r
     
451.     WHERE :n>=6 and  b.all_rows >= case when :n=6 then r.one_row else '0' end --如果N=6,上下对称取大
     
452.           and INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
453.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
454.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
455.    union all
     
456.    select * from b5 where :n<6       -- 若N=5,则b6就是b5的结果集
     
457. )
     
458. ,b7 AS (
     
459.    SELECT b.row_num+1                                      AS row_num
     
460.          ,b.all_rows||r.one_row                            AS all_rows
     
461.          ,b.col_cnt+r.one_row                              AS col_cnt
     
462.          ,b.diag_cnt1*10+r.one_row                         AS diag_cnt1
     
463.          ,b.diag_cnt2+r.one_row*POWER(10,b.row_num)        AS diag_cnt2
     
464.      FROM b6 b,r
     
465.     WHERE :n>=7 and b.all_rows >= r.one_row --如果N=7,上下对称取大
     
466.           AND INSTR(b.col_cnt     +r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
     
467.           AND INSTR(b.diag_cnt1*10+r.one_row,:M+1)=0
     
468.           AND INSTR(b.diag_cnt2+r.one_row*POWER(10,b.row_num),:M+1)=0
     
469.    union all
     
470.    select * from b6 where :n<7       -- 若N=6,则b7就是b6的结果集
     
471. )
     
472. ,m AS (
     
473.   SELECT CEIL(LEVEL/:N) r
     
474.         ,MOD(LEVEL-1,:N)+1 c
     
475.         ,LEVEL seq
     
476.     FROM DUAL
     
477.    CONNECT BY LEVEL<=:N*:N
     
478. )
     
479. ,m2 AS (
     
480. SELECT seq,0 AS tpl_id,r,c FROM m       ----- tpl_id=0: 原样
     
481. UNION ALL
     
482. SELECT seq,1 AS tpl_id,r,:N+1-c FROM m       ----- tpl_id=1: 沿竖线中轴对折
     
483. UNION ALL
     
484. SELECT seq,2 AS tpl_id,:N+1-r,c FROM m       ----- tpl_id=2: 沿横线中轴对折
     
485. UNION ALL
     
486. SELECT seq,3 AS tpl_id,:N+1-r,:N+1-c FROM m       ----- tpl_id=3: 1,2 的叠加, 或顺时针180度
     
487. UNION ALL
     
488. SELECT seq,4 AS tpl_id,c,r FROM m       ----- tpl_id=4: 以左上至右下斜线为轴对折
     
489. UNION ALL
     
490. SELECT seq,5 AS tpl_id,:N+1-c,:N+1-r FROM m       ----- tpl_id=5: 以右上至左下斜线为轴对折
     
491. UNION ALL
     
492. SELECT seq,6 AS tpl_id,c,:N+1-r FROM m       ----- tpl_id=6: 顺时针90度
     
493. UNION ALL
     
494. SELECT seq,7 AS tpl_id,:N+1-c,r FROM m       ----- tpl_id=7: 逆时针90度
     
495. )
     
496. ,templates AS (
     
497. SELECT tpl_id
     
498.       ,tpl_str
     
499.       ,MAX(CASE WHEN tpl_id=0 THEN tpl_str END) OVER() AS tpl_org
     
500.   FROM (SELECT m2.tpl_id
     
501.               ,REPLACE(SYS_CONNECT_BY_PATH(all_chars.ch,'/'),'/') tpl_str ----- 拼接模版
     
502.           FROM m2
     
503.                JOIN (SELECT ROWNUM seq
     
504.                            ,ch
     
505.                        FROM (SELECT CHR(LEVEL) ch ----- 用ASCII码表作为模板. 0,1要排除掉,斜杠/作为分隔符也要排除
     
506.                                FROM DUAL
     
507.                               WHERE CHR(LEVEL) NOT IN ('0','1','/')
     
508.                               CONNECT BY LEVEL<=255
     
509.                             )
     
510.                     ) all_chars
     
511.                ON m2.seq = all_chars.seq
     
512.          WHERE LEVEL = :N*:N
     
513.         START WITH r=1
     
514.         CONNECT BY tpl_id = PRIOR tpl_id  ---- 同一种模版
     
515.                    AND (PRIOR c <:N AND r=PRIOR r AND c = PRIOR c+1   ---- 同一行的下一列
     
516.                         OR PRIOR c =:N AND r=PRIOR r+1 AND c = 1  ---- 下一行的第一列
     
517.                         )
     
518.        )
     
519. )
     
520. ,temp2 AS (
     
521. SELECT MAX(DECODE(tpl_id,0,tpl_str)) tpl0
     
522.       ,MAX(DECODE(tpl_id,1,tpl_str)) tpl1
     
523.       ,MAX(DECODE(tpl_id,2,tpl_str)) tpl2
     
524.       ,MAX(DECODE(tpl_id,3,tpl_str)) tpl3
     
525.       ,MAX(DECODE(tpl_id,4,tpl_str)) tpl4
     
526.       ,MAX(DECODE(tpl_id,5,tpl_str)) tpl5
     
527.       ,MAX(DECODE(tpl_id,6,tpl_str)) tpl6
     
528.       ,MAX(DECODE(tpl_id,7,tpl_str)) tpl7
     
529.   FROM templates
     
530. )
     
531. ,dist as(
     
532. SELECT DISTINCT
     
533.              LEAST(all_rows
     
534.                  ,TRANSLATE(tpl1,tpl0,all_rows)
     
535.                  ,TRANSLATE(tpl2,tpl0,all_rows)
     
536.                  ,TRANSLATE(tpl3,tpl0,all_rows)
     
537.                  ,TRANSLATE(tpl4,tpl0,all_rows)
     
538.                  ,TRANSLATE(tpl5,tpl0,all_rows)
     
539.                  ,TRANSLATE(tpl6,tpl0,all_rows)
     
540.                  ,TRANSLATE(tpl7,tpl0,all_rows)
     
541.                   )
     
542.              AS all_rows
     
543.          FROM b7 CROSS JOIN temp2)
     
544. SELECT :N,:M,MAX(distinct_cnt),COUNT(*)
     
545.   FROM (
     
546.         SELECT DISTINCT
     
547.                TRANSLATE(tpl_str,tpl_org,all_rows) all_rows
     
548.               ,distinct_cnt
     
549.           FROM (SELECT all_rows,count(*) OVER() AS distinct_cnt
     
550.                  FROM dist
     
551.                ) CROSS JOIN templates -------- 把不重复解再次和模板进行笛卡尔连接，还原出其他解
     
552. )
     
553. ;
     
554. 这个写法在 N=7, M=3的时候还能跑出答案，其他写法都崩溃了：
     
555. 
     
556.         :N         :M MAX(DISTINCT_CNT)   COUNT(*)
     
557. ---------- ---------- ----------------- ----------
     
558.          7          3            164991    1319016
     
559. 已用时间:  00: 09: 54.24

复制代码

〇〇

我在巨人基础上修改的解法
http://www.itpub.net/thread-1411686-1-2.html

lastwinner

牛人辈出，Oracle提供的功能真是很强大

jvkojvko

思路和结果正确，完全人肉法，代码写的过于复杂，代码TT1-TT6部分可用with减轻目前的臃肿程度。这代码评委看的眼花缭乱，作者写的辛苦了！

完全人肉法，hoho
还能有第9满意了

jvkojvko

两期得分总和才194.4，看来玄了，人家分都那么高

jiqing1004

哎呀  中招了   
用了 UTL_RAW.BIT_OR 函数
看了newkid的帖子才发现，UTL_RAW.BIT_OR总是返回偶数位长度，奇数则左边会补一个零
导致奇数的全算错了  555555555

jvkojvko

原帖由 jiqing1004 于 2011-3-28 16:59 发表
哎呀  中招了   
用了 UTL_RAW.BIT_OR 函数
看了newkid的帖子才发现，UTL_RAW.BIT_OR总是返回偶数位长度，奇数则左边会补一个零
导致奇数的全算错了  555555555

我研究了好久的BIT_OR，没研究出个啥来，然后用人肉法了，

regonly1

看来只能混个参与了

rollingpig

郁闷，光注释就扣了我2-3分。