# 第一届SQL大赛第一期优秀解题思路汇总

SQL大赛第一期解题方法的公布，让我领略了各种新颖巧妙的解题方法。精神也为之一振，就决定写篇总结，把大家好的方法记下来。

1、每行不得超过两个球；
2、每列不得超过两个球；
3、每个45度斜线不得超过两个球（包括左倾斜和右倾斜，及对角线）

***************************************************************
1、递归法（这是我自己的方法(GO)，所以先拿出来晒晒）
***************************************************************

SQL> select floor(rownum/(dim + cnt - 1)) n, rownum r, dim
2    from dual, (select 5 dim, length('11') cnt  from dual) dims
3  connect by rownum <= dim+cnt
4  /

N          R        DIM
---------- ---------- ----------
0          1          5
.................
0          5          5
1          6          5
1          7          5

7 rows selected

SQL> with
2  dims as(select 5 dim, 2 cnt from dual)
3  select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
4    from dual, dims
5  connect by rownum <= dim+cnt
6  /

N          R        DIM
---------- ---------- ----------
0          1          5
...................
0          5          5
1          6          5
1          7          5

7 rows selected

SQL> with
2  dims as(select 6 dim, 2 cnt from dual)
3  select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
4    from dual, dims
5  connect by rownum <= dim+cnt
6  /

N          R        DIM
---------- ---------- ----------
0          1          6
..................
0          6          6
1          7          6
1          8          6

8 rows selected

SQL> with
2  dims as(select 5 dim, 2 cnt from dual),
3  nums as(
4  select n, to_number(substr(n, 1, 1)) n1,
5         to_number(substr(n, 2, 1)) n2, to_number(substr(n, 3, 1)) n3,
6         to_number(substr(n, 4, 1)) n4, to_number(substr(n, 5, 1)) n5
7    from (select distinct replace(sys_connect_by_path(n, ','), ',') n
8            from (select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
9                    from dual, dims
10                  connect by rownum <= dim+cnt)
11           where level = dim
12          connect by nocycle prior r <> r and level <= dim))
13  select * from nums
14  /

N                   N1         N2         N3         N4         N5
----------- ---------- ---------- ---------- ---------- ----------
00001                0          0          0          0          1
.................................
10001                1          0          0          0          1
11000                1          1          0          0          0

16 rows selected

***************************************************************
2、逐个递推法
***************************************************************

【代码】：
SQL> with t1 as
2  (
3  select iid, x, y, x + y + 25 z1, x - y z2
4    from (select rownum iid, mod(rownum - 1, 5) + 1 x, ceil(rownum / 5) y
5            from dual
6          connect by rownum <= 25)
7    )
8  select x,y,substr('00000', 1, y - 1) || '1' ||
9         substr('00000', y, x - y - 1) || '1' ||
10         substr('00000', x, 5 - x) rr
11    from t1
12   where x > y
13     and x != y
14  /

X          Y RR
---------- ---------- --------------------------------
2          1 11000
.........
5          3 00101
5          4 00011

10 rows selected

***************************************************************
3、排列组合法
***************************************************************

【代码】
(select 0 v11 from dual union all select 1 from dual) a1,
.................
(select 0 v55 from dual union all select 1 from dual) a25

【代码】
SQL> with c as
2   (select rownum - 1 c from dual connect by rownum <= 2)
3  select to_number (c1.c || c2.c || c3.c || c4.c || c5.c) line
4    from c c1, c c2, c c3, c c4, c c5
5   where c1.c + c2.c + c3.c + c4.c + c5.c = 2
6   order by 1 desc
7  /

LINE
----------
11000
.....
101
11

10 rows selected

***************************************************************
4、二进制构造（想不出好的名字，就这么命名了）
***************************************************************

【代码】
SQL>  select col1 || col2 || col3 || col4 || col5 strings,
2          col1 + col2 + col3 + col4 + col5 balls,
3          r.*
4     from (select mod(floor(rownum / 16), 2) col1,
5                  mod(floor(rownum / 8), 2) col2,
6                  mod(floor(rownum / 4), 2) col3,
7                  mod(floor(rownum / 2), 2) col4,
8                  mod(floor(rownum), 2) col5
9             from dual
10           connect by rownum <= 32) r
11    where col1 + col2 + col3 + col4 + col5 <= 5
12    ORDER BY 1 desc
13  /

STRINGS           BALLS       COL1       COL2       COL3       COL4       COL5
------------ ---------- ---------- ---------- ---------- ---------- ----------
11111                5          1          1          1          1          1
..............
00001                1          0          0          0          0          1
00000                0          0          0          0          0          0

32 rows selected

***************************************************************
1、坐标点相加法（这个是我，也是其他很多人用的）
***************************************************************

【代码】
n15 + n24 + n33 + n42 + n51 <= 2 --对角线相加
n21 + n32 + n43 + n54 <= 2
n31 + n42 + n53 <= 2
n41 + n52 <= 2
n12 + n23 + n34 + n45 <= 2
n13 + n24 + n35 <= 2
n14 + n24 <= 2--右倾斜
n14 + n23 + n32 + n41 <= 2
n31 + n22 + n13 <= 2
n21 + n12 <= 2
n52 + n43 + n34 + n25 <= 2
n53 + n44 + n35 <= 2
n45 + n54 <= 2

***************************************************************
2、移位相加法
***************************************************************

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

【代码】：
with c as
(select rownum - 1 c from dual connect by rownum <= 2),
lines as
(select to_number(c1.c || c2.c || c3.c || c4.c || c5.c) line
from c c1, c c2, c c3, c c4, c c5
where c1.c + c2.c + c3.c + c4.c + c5.c = 2
order by 1 desc)
select rownum, ltrim(to_char(line1.line, '09999')) ||
ltrim(to_char(line2.line, '09999')) ||
ltrim(to_char(line3.line, '09999')) ||
ltrim(to_char(line4.line, '09999')) ||
ltrim(to_char(line5.line, '00009')) result
from lines line1, lines line2, lines line3, lines line4, lines line5
where line1.line + line2.line + line3.line + line4.line + line5.line = 22222
and ltrim(to_char(line1.line + 10 * line2.line + 100 * line3.line + 1000 * line4.line + 10000 * line5.line), '012') is null
and ltrim(to_char(10000 * line1.line + 1000 * line2.line + 100 * line3.line + 10 * line4.line + line5.line), '012') is null;

***************************************************************
3、等值分组法
***************************************************************

【代码】：
with t1 as
(--构造坐标点，对坐标点标号，并取每个坐标点的横竖坐标差和和
select iid, x, y, x + y + 25 z1, x - y z2
from (select rownum iid, mod(rownum - 1, 5) + 1 x, ceil(rownum / 5) y
from dual
connect by rownum <= 25)
)
,t2 as (
--取出每条斜线坐标点数大于2的集合
select iid, zz
from (select iid, z1 zz, count(*) over(partition by z1) cnt
from t1
union all
select iid, z2, count(*) over(partition by z2) cnt from t1)
where cnt > 2
)
,t3 as (--构造5+2
select rr,
to_number(substr(rr, 1, 1)) c1,
to_number(substr(rr, 2, 1)) c2,
to_number(substr(rr, 3, 1)) c3,
to_number(substr(rr, 4, 1)) c4,
to_number(substr(rr, 5, 1)) c5
from (select substr('00000', 1, y - 1) || '1' ||
substr('00000', y, x - y - 1) || '1' ||
substr('00000', x, 5 - x) rr
from t1
where x > y
and x != y)
)
select rownum, chr
from (select chr
from (select a.chr,
b.zz,
sum(to_number(substr(a.chr, b.iid, 1))) n1
from (select r1.rr || r2.rr || r3.rr || r4.rr || r5.rr chr
from t3 r1, t3 r2, t3 r3, t3 r4, t3 r5
where r1.c1 + r2.c1 + r3.c1 + r4.c1 + r5.c1 < 3
and r1.c2 + r2.c2 + r3.c2 + r4.c2 + r5.c2 < 3
and r1.c3 + r2.c3 + r3.c3 + r4.c3 + r5.c3 < 3
and r1.c4 + r2.c4 + r3.c4 + r4.c4 + r5.c4 < 3
and r1.c5 + r2.c5 + r3.c5 + r4.c5 + r5.c5 < 3) a,
t2 b
group by a.chr, b.zz)
group by chr
having max(n1) < 3
order by chr desc);

按道理，每次写blog，都应该写篇总结，尤其是这篇总结的总结。但是由于每次写完blog，能够一样样写好并举例，都感到很疲劳了，本身已经很不易，再写个结论更累。呵呵，所以这次结论是在这篇原始版的blog写完后几天后才补充的。

说了这么多，开始写结论吧。

这次题目，主要思想是解决N×N矩阵中，球体摆放的问题。
面对的最主要问题是如何用只能生成行数据的一个SQL语句来解决二维的矩阵数据的生成和条件的判断。
因此，我们很自然的把问题分解为两个方面：
一、数据的生成
二、数据的判断
数据的生成，我们又可以按如下思路来考虑：
首先，按照题目要求，是5×5的矩阵，且每行不得超过2个球，所以，每个行他的可能性只有：
C(5,2) +C(5,1) + 1 = 10 + 5 + 1 = 16种

于是，我们得到了构造一行所需要的16种基本数据，其他行也是这个规则。于是总的可能性就有：
16^5 = 1048576种。
现在，我们要解决的就是如何从这100多万种方案中筛选出题目所要求的矩阵了。于是，下一步的问题就变成了数据的判断了。其实，数据的判断虽然在方法上比数据的构造多种多样，但是本质却是一致的。就是判断斜线的和不大于2。沿着这个思路，大家充分发挥了想象力，看到其他人尤其是几位得分靠前的高手的答案后，我真是惊叹，大千世界，学无止境啊。
其中的对斜线分组法及移位相加法，是我很崇拜的方法，因为其扩展性和效率都很好，而且也很简洁。这个是这次大赛值得我们学习的地方。

• 博文量
257
• 访问量
1084122