puzzleup 2011

newkid

〇〇



精华贴数 10
个人空间 0
技术积分 49719 (25)
社区积分 9647 (262)
注册日期 2008-1-16
论坛徽章:229                                       
                                       

                #55
使用道具  
发表于 2011-9-15 19:42  
一共9个2*2小方块
4个角1次
8个边2次
。。。



__________________
我的新浪微博，欢迎大家加我：http://weibo.com/lu01


剑破冰山—Oracle开发艺术 已经上架销售
网购地址：互动|京东电子工业出版社书店卓越亚马逊当当华储
在线阅读：5lcto华储
源代码：博文视点ITPUB
只看该作者              引用  回复  报告  编辑   

solomon_007
所罗门



精华贴数 2
个人空间 0
技术积分 1766 (1395)
社区积分 35 (11109)
注册日期 2006-5-14
论坛徽章:24                                       
                                       

                #56
使用道具  
发表于 2011-9-15 20:08  


QUOTE:
原帖由 〇〇 于 2011-9-15 19:42 发表
一共9个2*2小方块
4个角1次
8个边2次
。。。

能数学证明一下吗？ 为什么是恒定的之呢？ 推而广之，更高阶的幻方，具有一般性吗？



__________________
猫言猫语：
              人生无非是笑笑人家,再被人家笑笑而已.
              男人是用来靠的,所以要可靠;女人是用来爱的,所以要可爱.
              发怒一分钟便失去六十秒的幸福.
              人品就象内裤,表面看不出来,如果你没有还显摆,就挺讨厌.
              ......
只看该作者              引用  回复  报告  编辑   

newkid
资深新手
老程序员



来自 银河系
精华贴数 15
个人空间 0
技术积分 20748 (73)
社区积分 5 (22147)
注册日期 2004-6-26
论坛徽章:66                                       
                                       

                #57
使用道具  
发表于 2011-9-15 21:36  


QUOTE:
原帖由 solomon_007 于 2011-9-15 20:08 发表



能数学证明一下吗？ 为什么是恒定的之呢？ 推而广之，更高阶的幻方，具有一般性吗？

别的不知道，反正四阶的很容易证明是常数，等会有空来写一下。
你那个高尔夫的SQL呢？我不是答应给你5万P币了么？



__________________

世界上只有两种编程方法：Oracle的方法和错误的方法。

剑破冰山—Oracle开发艺术 即将隆重推出
http://www.china-pub.com/197199
http://www.huachu.com.cn/itbook/itbookinfo.asp?lbbh=10114321
只看该作者              引用  回复  报告  编辑   

newkid
资深新手
老程序员



来自 银河系
精华贴数 15
个人空间 0
技术积分 20748 (73)
社区积分 5 (22147)
注册日期 2004-6-26
论坛徽章:66                                       
                                       

                #58
使用道具  
发表于 2011-9-15 22:09  
S=(c11+c12+c21+c22)+(c12+c13+c22+c23)+(c13+c14+c23+c24)
+(c21+c22+c31+c32)+(c22+c23+c32+c33)+(c23+c24+c33+c34)
+(c31+c32+c41+c42)+(c32+c33+c42+c43)+(c33+c34+c43+c44)
对换位置：
(c11+c12+c13+c14)+(c21+c22+c23+c24)
+(c31+c32+c33+c34)+(c41+c42+c43+c44)
+(c12+c22+c32+c42)
+(c13+c23+c33+c43)
+(c21+c22+c23+c24)+(c31+c32+c33+c34)
+(c22+c23+c32+c33)

除了最后四个，其他的和都是34。
最后四个是中间的四个数，加上四个角就等于两条对角线：

(c22+c23+c32+c33)+C11+C14+C41+C44 = 68

这两条对角线之和也等于第一+第四行之和：
(c12+c13+c42+c43)+C11+C14+C41+C44 = 68

得到(c22+c23+c32+c33)=(c12+c13+c42+c43)
而(c22+c23+c32+c33)+(c12+c13+c42+c43)=第二列+第三列=68
因此(c22+c23+c32+c33)=34

由此得到s=34*9=306



__________________

世界上只有两种编程方法：Oracle的方法和错误的方法。

剑破冰山—Oracle开发艺术 即将隆重推出
http://www.china-pub.com/197199
http://www.huachu.com.cn/itbook/itbookinfo.asp?lbbh=10114321
只看该作者              引用  回复  报告  编辑   
-------------------------------------------------------
newkid
资深新手
老程序员



来自 银河系
精华贴数 15
个人空间 0
技术积分 20748 (73)
社区积分 5 (22147)
注册日期 2004-6-26
论坛徽章:66                                       
                                       

                #59
使用道具  
发表于 2011-9-15 22:15  
虽然这个题完全不用SQL, 但是利用SQL找出所有幻方也算意外收获。
一开始我写AND n1.s1 + n2.s1=34 半天出不来，估计走NESTED LOOPS了，改成AND n1.s1=34 - n2.s1才能HASH JOIN.



__________________

世界上只有两种编程方法：Oracle的方法和错误的方法。

剑破冰山—Oracle开发艺术 即将隆重推出
http://www.china-pub.com/197199
http://www.huachu.com.cn/itbook/itbookinfo.asp?lbbh=10114321
只看该作者              引用  回复  报告  编辑   

solomon_007
所罗门



精华贴数 2
个人空间 0
技术积分 1766 (1395)
社区积分 35 (11109)
注册日期 2006-5-14
论坛徽章:24                                       
                                       

                #60
使用道具  
发表于 2011-9-16 00:54  


QUOTE:
原帖由 newkid 于 2011-9-15 22:09 发表
S=(c11+c12+c21+c22)+(c12+c13+c22+c23)+(c13+c14+c23+c24)
+(c21+c22+c31+c32)+(c22+c23+c32+c33)+(c23+c24+c33+c34)
+(c31+c32+c41+c42)+(c32+c33+c42+c43)+(c33+c34+c43+c44)
对换位置：
(c11+c12+c13+c14)+(c21+c22+c23+c24)
+(c31+c32+c33+c34)+(c41+c42+c43+c44)
+(c12+c22+c32+c42)
+(c13+c23+c33+c43)
+(c21+c22+c23+c24)+(c31+c32+c33+c34)
+(c22+c23+c32+c33)

除了最后四个，其他的和都是34。
最后四个是中间的四个数，加上四个角就等于两条对角线：

(c22+c23+c32+c33)+C11+C14+C41+C44 = 68

这两条对角线之和也等于第一+第四行之和：
(c12+c13+c42+c43)+C11+C14+C41+C44 = 68

得到(c22+c23+c32+c33)=(c12+c13+c42+c43)
而(c22+c23+c32+c33)+(c12+c13+c42+c43)=第二列+第三列=68
因此(c22+c23+c32+c33)=34

由此得到s=34*9=306

我先想了半天，发现中间的出现了3次，4个角1次，其他2次，没有想到加4个角正好是两条对角线之和，就放弃了进一步思考。。。

真佩服！！



__________________
猫言猫语：
              人生无非是笑笑人家,再被人家笑笑而已.
              男人是用来靠的,所以要可靠;女人是用来爱的,所以要可爱.
              发怒一分钟便失去六十秒的幸福.
              人品就象内裤,表面看不出来,如果你没有还显摆,就挺讨厌.
              ......


solomon_007
所罗门



精华贴数 2
个人空间 0
技术积分 1766 (1395)
社区积分 35 (11109)
注册日期 2006-5-14
论坛徽章:24                                       
                                       

                #61
使用道具  
发表于 2011-9-16 00:57  


QUOTE:
原帖由 newkid 于 2011-9-15 22:15 发表
虽然这个题完全不用SQL, 但是利用SQL找出所有幻方也算意外收获。
一开始我写AND n1.s1 + n2.s1=34 半天出不来，估计走NESTED LOOPS了，改成AND n1.s1=34 - n2.s1才能HASH JOIN.

这个在调试是也碰到了，还觉的奇怪呢，没分析执行计划，就还原你的写法了。。。



__________________
猫言猫语：
              人生无非是笑笑人家,再被人家笑笑而已.
              男人是用来靠的,所以要可靠;女人是用来爱的,所以要可爱.
              发怒一分钟便失去六十秒的幸福.
              人品就象内裤,表面看不出来,如果你没有还显摆,就挺讨厌.
              ......
只看该作者              引用  回复  报告  编辑   

solomon_007
所罗门



精华贴数 2
个人空间 0
技术积分 1766 (1395)
社区积分 35 (11109)
注册日期 2006-5-14
论坛徽章:24                                       
                                       

                #62
使用道具  
发表于 2011-9-16 01:02  


QUOTE:
原帖由 newkid 于 2011-9-15 21:36 发表

别的不知道，反正四阶的很容易证明是常数，等会有空来写一下。
你那个高尔夫的SQL呢？我不是答应给你5万P币了么？

我看到了，试了一下，没搞出来，这个周末有时间再分析一下。。。



__________________
猫言猫语：
              人生无非是笑笑人家,再被人家笑笑而已.
              男人是用来靠的,所以要可靠;女人是用来爱的,所以要可爱.
              发怒一分钟便失去六十秒的幸福.
              人品就象内裤,表面看不出来,如果你没有还显摆,就挺讨厌.
              ......

newkid

#8:
Using all of the numbers once from 1 to 16, 4x4 magic squares are formed. What is the possible maximum value of the sum of four numbers in any 2x2 block on this 4x4 square.
Note: In a magic square, the numbers in all rows, all columns, and both diagonals sum to the same constant.

1-16排成4X4幻方，在这个4X4方阵中所有2X2小方阵之和的最大值是多少？
在一个幻方中所有行、列、两条对角线之和都相等。

这个难度不大。

newkid

四阶幻方：
WITH nums AS (SELECT LEVEL n, POWER(2,LEVEL-1) bit FROM DUAL CONNECT BY LEVEL<=16)
,num4 AS (
SELECT n1.n n1,n2.n n2,n3.n n3,n4.n n4
      ,n1.bit+n2.bit+n3.bit+n4.bit bit
  FROM nums n1,nums n2,nums n3,nums n4
WHERE n1.n+n2.n+n3.n+n4.n=34
       AND n1.n NOT IN (n2.n,n3.n,n4.n)
       AND n2.n NOT IN (n3.n,n4.n)
       AND n3.n<>n4.n
)
,num8 AS (
SELECT n1.n1,n1.n2,n1.n3,n1.n4,n2.n1 n5,n2.n2 n6,n2.n3 n7,n2.n4 n8
      ,n1.n1+n2.n1 s1
      ,n1.n2+n2.n2 s2
      ,n1.n3+n2.n3 s3
      ,n1.n4+n2.n4 s4
      ,n1.bit+n2.bit bit
      ,n1.n1+n2.n2 d1
      ,n1.n4+n2.n3 d2
      ,n1.n3+n2.n4 d3
      ,n1.n2+n2.n1 d4
  FROM num4 n1,num4 n2
WHERE BITAND(n1.bit,n2.bit)=0
)
,num16 AS (
SELECT
  FROM num8 n1,num8 n2
WHERE n1.bit = POWER(2,16)-1-n2.bit
       AND n1.s1=34 - n2.s1
       AND n1.s2=34 - n2.s2
       AND n1.s3=34 - n2.s3
       AND n1.s4=34 - n2.s4
       AND n1.d1=34 - n2.d3
       AND n1.d2=34 - n2.d4
)
SELECT count(*) FROM num16;

  COUNT(*)
----------
      7040

Elapsed: 00:00:10.62

剩下的就很好办了，明天继续。

solomon_007

SQL> with t as (
  2             select
  3                    substr(str,instr(str,'/',1, 1)+1,instr(str,'/',1, 2)-instr(str,'/',1, 1) -1) c11,
  4                    substr(str,instr(str,'/',1, 2)+1,instr(str,'/',1, 3)-instr(str,'/',1, 2) -1) c12,
  5                    substr(str,instr(str,'/',1, 3)+1,instr(str,'/',1, 4)-instr(str,'/',1, 3) -1) c13,
  6                    substr(str,instr(str,'/',1, 4)+1,instr(str,'/',1, 5)-instr(str,'/',1, 4) -1) c21,
  7                    substr(str,instr(str,'/',1, 5)+1,instr(str,'/',1, 6)-instr(str,'/',1, 5) -1) c22,
  8                    substr(str,instr(str,'/',1, 6)+1,instr(str,'/',1, 7)-instr(str,'/',1, 6) -1) c23,
  9                    substr(str,instr(str,'/',1, 7)+1,instr(str,'/',1, 8)-instr(str,'/',1, 7) -1) c31,
10                    substr(str,instr(str,'/',1, 8)+1,instr(str,'/',1, 9)-instr(str,'/',1, 8) -1) c32,
11                    substr(str,instr(str,'/',1, 9)+1,instr(str,'/',1,10)-instr(str,'/',1, 9) -1) c33
12              from (
13                    select sys_connect_by_path(rn,'/')||'/' str
14                      from (select rownum rn from dual connect by level <=9)
15                     where level=9
16                     connect by nocycle rn <> prior rn
17                    )
18            )
19  select *
20    from t
21   where c11 + c12 + c13 = c21 + c22 + c23
22     and c11 + c12 + c13 = c31 + c32 + c33
23     and c11 + c12 + c13 = c11 + c21 + c31
24     and c11 + c12 + c13 = c12 + c22 + c32
25     and c11 + c12 + c13 = c13 + c23 + c33
26     and c11 + c12 + c13 = c11 + c22 + c33
27     and c11 + c12 + c13 = c31 + c22 + c13
28  /



C11 C12 C13 C21 C22 C23 C31 C32 C33
--- --- --- --- --- --- --- --- ---
2   7   6   9   5   1   4   3   8
2   9   4   7   5   3   6   1   8
4   3   8   9   5   1   2   7   6
4   9   2   3   5   7   8   1   6
6   1   8   7   5   3   2   9   4
6   7   2   1   5   9   8   3   4
8   1   6   3   5   7   4   9   2
8   3   4   1   5   9   6   7   2


我上面的方法只能找3阶幻方，4阶 16! 这个太大了，跑不出来。。。

solomon_007

看明白了， NEWKID 用的是每4个=34的数据为单位进行填充的，4 join 4 得8 ,8 join 8 得16 ,高!

〇〇

原帖由 newkid 于 2011-9-14 22:03 发表
#8:
Using all of the numbers once from 1 to 16, 4x4 magic squares are formed. What is the possible maximum value of the sum of four numbers in any 2x2 block on this 4x4 square.
Note: In a magic square, the numbers in all rows, all columns, and both diagonals sum to the same constant.

1-16排成4X4幻方，在这个4X4方阵中所有2X2小方阵之和的最大值是多少？
在一个幻方中所有行、列、两条对角线之和都相等。

这个难度不大。

所有2X2小方阵之和的最大值:是否需要列举所有的幻方才能，还是有什么理论

solomon_007

采用newkid的：

with nums  as (select level n, power(2,level-1) bit from dual connect by level<=16),
     num4  as (
                select n1.n n1,
                       n2.n n2,
                       n3.n n3,
                       n4.n n4,
                       n1.bit+n2.bit+n3.bit+n4.bit bit
                  from nums n1,
                       nums n2,
                       nums n3,
                       nums n4
                where n1.n+n2.n+n3.n+n4.n=34
                  and n1.n not in (n2.n,n3.n,n4.n)
                  and n2.n not in (n3.n,n4.n)
                  and n3.n<>n4.n
               ),
     num8 as (
              select n1.n1,n1.n2,n1.n3,n1.n4,n2.n1 n5,n2.n2 n6,n2.n3 n7,n2.n4 n8
                    ,n1.n1+n2.n1 s1
                    ,n1.n2+n2.n2 s2
                    ,n1.n3+n2.n3 s3
                    ,n1.n4+n2.n4 s4
                    ,n1.bit+n2.bit bit
                    ,n1.n1+n2.n2 d1
                    ,n1.n4+n2.n3 d2
                    ,n1.n3+n2.n4 d3
                    ,n1.n2+n2.n1 d4
                from num4 n1,
                     num4 n2
              where bitand(n1.bit,n2.bit)=0
             ),
    num16 as (
              select n1.n1 c11,
                     n1.n2 c12,
                     n1.n3 c13,
                     n1.n4 c14,
                     n1.n5 c21,
                     n1.n6 c22,
                     n1.n7 c23,
                     n1.n8 c24,
                     n2.n1 c31,
                     n2.n2 c32,
                     n2.n3 c33,
                     n2.n4 c34,
                     n2.n5 c41,
                     n2.n6 c42,
                     n2.n7 c43,
                     n2.n8 c44  
                from num8 n1,
                     num8 n2
               where n1.bit = power(2,16) - 1 - n2.bit
                 and n1.s1 = 34 - n2.s1
                 and n1.s2 = 34 - n2.s2
                 and n1.s3 = 34 - n2.s3
                 and n1.s4 = 34 - n2.s4
                 and n1.d1 = 34 - n2.d3
                 and n1.d2 = 34 - n2.d4
              ),
      res as (
              select c11,c12,c13,c14,c21,c22,c23,c24,c31,c32,c33,c34,c41,c42,c43,c44,
                     (c11+c12+c21+c22)+(c12+c13+c22+c23)+(c13+c14+c23+c24)
                    +(c21+c22+c31+c32)+(c22+c23+c32+c33)+(c23+c24+c33+c34)
                    +(c31+c32+c41+c42)+(c32+c33+c42+c43)+(c33+c34+c43+c44) s
                from num16     
             )   
select *
from (select t.*,dense_rank() over(order by s) rk from res t)
where rk = 1                           
;


1        8        11        6        9        12        7        10        5        1        2        15        16        13        14        3        4        306        1
2        7        6        11        10        14        9        8        3        1        4        13        16        12        15        2        5        306        1
3        12        9        8        5        6        7        10        11        1        4        13        16        15        14        3        2        306        1
4        8        5        12        9        10        11        6        7        1        4        13        16        15        14        3        2        306        1
5        12        9        6        7        8        5        10        11        1        4        15        14        13        16        3        2        306        1
6        8        5        10        11        12        9        6        7        1        4        15        14        13        16        3        2        306        1
7        10        11        7        6        8        5        9        12        1        4        16        13        15        14        2        3
                306        1

.......

(7040 组 )

是定值，恒等于306

[ 本帖最后由 solomon_007 于 2011-9-15 17:23 编辑 ]

〇〇

一共9个2*2小方块
4个角1次
8个边2次
。。。

solomon_007

原帖由 〇〇 于 2011-9-15 19:42 发表
一共9个2*2小方块
4个角1次
8个边2次
。。。

能数学证明一下吗？ 为什么是恒定的之呢？ 推而广之，更高阶的幻方，具有一般性吗？

newkid

原帖由 solomon_007 于 2011-9-15 20:08 发表



能数学证明一下吗？ 为什么是恒定的之呢？ 推而广之，更高阶的幻方，具有一般性吗？

别的不知道，反正四阶的很容易证明是常数，等会有空来写一下。
你那个高尔夫的SQL呢？我不是答应给你5万P币了么？