(3.3.1)--3.3DURER魔方.pdf

3.3 3.3 DurerDurer魔方魔方一、引入4+9+24+3+84+5+6153+5+79+5+1158+1+62+7+68+5+215行列对角线和三阶三阶幻方：幻方：二、幻方2437865911、幻方的构造幻方的构造2、幻方的计数、幻方的计数二、幻方幻方源于中国，历史上最早研究幻方是南宋的数学家杨辉，与秦九韶、李冶、朱世杰并称“宋元数学四大家”。杨 辉续古摘奇算法续古摘奇算法列出列出20个纵横图，即幻方。其中第一个为河个纵横图，即幻方。其中第一个为河图，第二个为图，第二个为洛洛书，其次，四行、五行、六行、七行、八行幻书，其次，四行、五行、六行、七行、八行幻方各两个，九行、十行幻方各一个，最后有“聚五”“聚六”：方各两个，九行、十行幻方各一个，最后有“聚五”“聚六”：聚八”“攒九”“八阵”“连环”等图。有一些图有文字说明，聚八”“攒九”“八阵”“连环”等图。有一些图有文字说明，但但每一个图都有构造方法，每一个图都有构造方法，使图中各自然数“多寡相资，邻壁使图中各自然数“多寡相资，邻壁相兼”凑成相等的相兼”凑成相等的和数和数.1、是否存在任意阶的幻方？、是否存在任意阶的幻方？2、幻方的构造？、幻方的构造？3、幻方的计数幻方的计数？二、幻方二、幻方1、3阶幻方的计数：阶幻方的计数：1 82、4阶阶幻方的计数幻方的计数：880 70403、5阶阶幻方的计数幻方的计数：2亿多个亿多个4、6阶阶幻方的计数幻方的计数：范围：范围：1.7710的19次方左右5、7阶阶幻方的计数幻方的计数：？：？德国著名的艺术家德国著名的艺术家 Albrecht Durer(1471Albrecht Durer(1471-1521)1521)于于15141514年曾铸造了一枚名为年曾铸造了一枚名为“MelenMelen cotiacotia I I”的铜币。令人奇的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数学数字和几何怪的是在这枚铜币的画面上充满了数学符号、数学数字和几何图形。这里我们仅研究铜币右上角的数字问题。图形。这里我们仅研究铜币右上角的数字问题。二、幻方二、幻方艺术家杜勒艺术家杜勒的画的画忧郁忧郁163213510118967124151411632135101189671241514116+3+2+1316+5+9+416+3+5+10345+10+11+83+10+6+1516+10+7+12+13+11+8349+6+7+122+11+7+1410+11+6+7344+15+14+113+8+12+14+6+11+139+6+4+15347+12+14+134行列对角线小方块和所出现的数是所出现的数是1至至16的自然数。的自然数。四角之四角之和为和为34。最下边一行中心数为最下边一行中心数为1514，正是制币的时间。，正是制币的时间。三、Durer 魔方定义定义如果如果44数字方，它的每一行、数字方，它的每一行、每一列、每一对角线及每个小方每一列、每一对角线及每个小方块上的数字之和都为一确定的数，则称这个数字方为块上的数字之和都为一确定的数，则称这个数字方为 Durer 魔方。魔方。三、Durer 魔方1、是否存在是否存在其他其他的的Durer 魔方魔方？2、如何构造、如何构造Durer 魔方魔方？3、Durer 魔方魔方如何计数？如何计数？0000000000000000O=1111111111111111E=06118910 6015 091199607118910 7016 0911997108010015014011050407020160901201303060三、Durer 魔方三、Durer 魔方a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44A=b11b12b13b14b21b22b23b24b31b32b33b34b41b42b43b44B=类似于矩阵的加法和数乘，定义魔方的加法和数乘类似于矩阵的加法和数乘，定义魔方的加法和数乘。D 加法和数乘封闭，且构成加法和数乘封闭，且构成一一线性空间线性空间。记记 M=所有的所有的44数字方数字方，则其维数为，则其维数为16。而。而D是是M的子集，则的子集，则D是是有限维有限维的线的线性空间。性空间。根据线性空间的性质，如果能得到根据线性空间的性质，如果能得到D的一组基的一组基，则，则任一个任一个Durer方均可方均可由这组基线由这组基线性表示。性表示。Q1=1000001000010100Q2=1000000101000010Q3=Q4=00011000001001000001010010000010Q5=0010100001000001Q6=0100001010000001Q7=0010010000011000Q8=0100000100101000076328541QQQQQQQQ三、Durer 魔方076328541QQQQQQQQ三、Durer 魔方077665544332211QrQrQrQrQrQrQr000000000000000021rr 6r75rr 43rr 53rr 74rr 2r64rr 52rr 3r71rr 61rr 7r31rr 42rr 65rr=07654321rrrrrrr线性无关线性无关任任一一Durer方可方可由其余由其余7个线性表示？个线性表示？2、任一、任一Durer方可方可由它们线性表示？由它们线性表示？1、是、是Durer方一方一组基吗？组基吗？高高代：代：如果如果44数字方，它的每一行、数字方，它的每一行、每一列、每一每一列、每一对角线数字对角线数字之和都为一确定的数，构成线性空间，之和都为一确定的数，构成线性空间，线性空间的维数为线性空间的维数为8。三、Durer 魔方01-10000000000-1102、哪个线性空间的维数大？、哪个线性空间的维数大？1、属于哪个线性空间？、属于哪个线性空间？结论：结论：1 Durer方方有无穷多个有无穷多个。2 Durer方可由方可由721QQQ,线性组合得到。线性组合得到。Albrecht Durer的数字方的构成：的数字方的构成：77665544332211QrQrQrQrQrQrQrD三、Durer 魔方21rr 6r75rr 43rr 53rr 74rr 2r64rr 52rr 3r71rr 61rr 7r31rr 42rr 65rr=1632135101189671241514143367887654321rrrrrrr,三、Durer 魔方7655432214336788QQQQQQQD三、Durer 魔方2、能否构造出其他、能否构造出其他维数维数(例：例：99)的的数字方数字方？1、把、把Durer方条件加强或减弱，维数是多少，如何构造基？方条件加强或减弱，维数是多少，如何构造基？3、能否、能否构造出其他形式的数字方？构造出其他形式的数字方？44数字方，它的每一行、数字方，它的每一行、每一列、每一对角线及每个小方块上的数字之和都为一确定的每一列、每一对角线及每个小方块上的数字之和都为一确定的数数 744数字方，它的每一行、数字方，它的每一行、每一列、每一每一列、每一对角线数字对角线数字之和都为一确定的之和都为一确定的数数 844数字方，它的每一行、数字方，它的每一行、每一每一列和列和都为一确定的都为一确定的数数1044数字方，它数字方，它的每个元素的每个元素都都为一确定的为一确定的数数144数字方，它数字方，它的每个元素没有要求的每个元素没有要求16四、数独2、编写算法构造幻方？、编写算法构造幻方？1、建立模型分析、建立模型分析Durer 魔方.3、是、是线性空间吗？线性空间吗？4、合格的数独题？、合格的数独题？5、构造合格的数独题？、构造合格的数独题？6、理论分析最小多少个数能构造合格数独题？、理论分析最小多少个数能构造合格数独题？7、编写算法编写算法求解数独题？求解数独题？算法分析算法分析四、数独MCM:MCM:Creating Sudoku Creating Sudoku PuzzlesPuzzlesDevelop an algorithm to construct Develop an algorithm to construct Sudoku puzzles of varying difficulty.Sudoku puzzles of varying difficulty.Develop metrics to define a difficulty Develop metrics to define a difficulty level.The algorithm and metrics should level.The algorithm and metrics should be extensible to a varying number of be extensible to a varying number of difficulty levels.You should difficulty levels.You should illustrate the algorithm with at least illustrate the algorithm with at least 4 difficulty levels.Your algorithm 4 difficulty levels.Your algorithm should guarantee a unique solution.should guarantee a unique solution.Analyze the complexity of your Analyze the complexity of your algorithm.Your objective should be to algorithm.Your objective should be to minimize the complexity of the minimize the complexity of the algorithm and meet the above algorithm and meet the above requirements.requirements.包中祥包中祥每个幻方的四行四列的和是每个幻方的四行四列的和是2008，每行的个位数字和为，每行的个位数字和为8，每列的个位数字的和是每列的个位数字的和是8，到处，到处呈现出一个呈现出一个2008.8.8的数字系列。的数字系列。这是一个纪念这是一个纪念2008年年8月月8日奥日奥运会召开的绝妙智力佳品，独运会召开的绝妙智力佳品，独一无二。一无二。五、完美幻方