一个单偶数n (n=4N+2) 阶最接近完全正负对称幻方的构造法

李光伦akacha_tw

介绍一个不需穷举试错的快速单偶数幻方构造法, 附关键部分js代码, 完整代码会在下一篇文章<将8x8幻方表示成两个2x8矩阵之有限域matmul的实验>中提供.
<正负>指的是有限域的"正负", 下文有解释.

若将(由一阶等差数组构成的)n阶幻方中每一元素表示成p*(n*a+b)+q, 当(p=1, q=1)时, 即常见的由1起始的连续整数幻方,
本文取(p=1, q=0), 即表示为由零起始至n^2-1的连续整数幻方.  
简单地说, 即将幻方中每一元素表示成纯n*a+b, 不附带p与q的线性scale.
下一篇文章将称这种以ab表示幻方元素的方法为"二数字/二数位(2 digits)表示法".

已知, 当n为单偶数时, 能使n*n幻方M[y,x]中每一对(点对称的)元素, 即M[y,x]与M[n-1-y,n-1-x], 皆满足M[y,x]+M[n-1-y,n-1-x]=n^2-1之关系的排列法不存在.
至少需有两对(相加为n^2-1的)互补元素不是对中心点对称的. 例如以下6阶幻方, 幻和=105:

1. 07 16        27 18        32 05
   
2. 25 34        00 09        14 23
   
3. 
   
4. 02 20        22 31        24 06
   
5. 29 11        04 13        15 33
   
6. 
   
7. 12 21        35 26        01 10
   
8. 30 03        17 08        19 28
   

复制代码

除00--35与09--26外, 其余对称元素相加皆等于6*6-1=35, 例如7--28, 15--20等.

再以10阶为例, 以下幻方幻和=495:

1. 00 25        89 39        96 71        42 92        08 33
   
2. 50 75        64 14        21 46        17 67        58 83
   
3. 
   
4. 72 97        18 43        80 55        79 04        36 11
   
5. 22 47        68 93        05 30        29 54        86 61
   
6. 
   
7. 59 34        01 51        62 87        73 23        90 15
   
8. 84 09        76 26        12 37        48 98        65 40
   
9. 
   
10. 38 13        45 70        94 69        06 31        52 77
    
11. 88 63        95 20        44 19        56 81        02 27
    
12. 
    
13. 16 41        32 82        53 78        85 35        24 49
    
14. 66 91        07 57        28 03        60 10        74 99
    

复制代码

除05--94与30--69外, 其余对称元素相加皆等于10*10-1=99, 例如4--95, 36--63等.

我称这一类只有两对互补元素不对称的单偶数阶幻方为<最接近完全正负对称幻方>,
之所以称<正负>, 是因为在dim=n的有限域中, 若称一数u为"正数", 另一数v其与u的关系满足u+v=n^2-1, 则可称v为u的"负数"/变号数,
这种关系在二幂dim中显而易见, 例如在dim=8中, 假令数字3为"正数", 其二进制表示为b000011, 那么其"变号数"60的二进制表示就是b111100,
0与1恰好是反过来的, 3+60=8*8-1=63. 计算机中signed int的负数表示法与此类似.

又, 二维坐标M[y,x]若写成线性一维坐标, 即为M[y*n+x], 会编程的应该对此很熟悉,
如此前文所谓"对中心点对称"的二元素, 以一维坐标表示即M[y*n+x]与M[n^2-1-y*n-x], 这两个一维坐标相加对消后只剩下n^2-1, 与前述"正负数"相加为n^2-1共享同一规律.

现在我所谓<正负对称>的意义应该很明瞭了, 指的即是<既在数值上正负互补, 又在坐标上正负互补>,
以此故我将这种对称性视为一个幻方是否完美的重要指标, 在这个意义上我称这种<只有两对互补元素不对称的>单偶数阶幻方为<最接近完美的>.

-构造法(代码):
这种单偶数n的<最接近完美幻方>, 是由一个(n>>1)阶的奇幻方与一组通用LUXmap构成的,
就我在网上查幻方LUX构造法所知, 这种无需试错的LUXmap构造法应该尚未被人发现过.

首先是LUXmap的构造法, 这是本幻方构造法的关键所在:

1. 
   
2. var cur_lx_size=0;
   
3. const LUXele=[
   
4.         [0x1b,0x2d,0x6c],
   
5.         [0xe1,0xb1,0xe4]
   
6. ];
   
7. 
   
8. function buildlx(n)
   
9. {
   
10.         
    
11.         if(n<=cur_lx_size){return;}
    
12.         LUXmap_width=n>>1;
    
13.         var qoddn=LUXmap_width>>1;
    
14.         LUXmap_height=qoddn+1;
    
15.         LUXmap = new Uint8Array(LUXmap_width*LUXmap_height);
    
16.         var staidx=qoddn-1;
    
17.         var lyn0=staidx*(LUXmap_width+1);
    
18.         LUXmap.set(LUXele[0], lyn0);
    
19.         lyn0+=LUXmap_width;
    
20.         LUXmap.set(LUXele[1], lyn0);
    
21.         if(staidx>0)
    
22.         {
    
23.                 lyn0-=staidx;
    
24.                 var toSouth=3+staidx;
    
25.                 var wm1=LUXmap_width-1;
    
26.                 var wp1=LUXmap_width+1;
    
27.                 var gibidx=LUXmap_width+wm1;
    
28.                
    
29.                 for(var d=0;d<staidx;d++)
    
30.                 {
    
31.                         LUXmap[d*LUXmap_width+qoddn]=0x9c;        //west
    
32.                         var fynlin=lyn0+d;
    
33.                         LUXmap[fynlin]=0xe1;                //north
    
34.                         LUXmap[fynlin+toSouth]=0xb4;        //south
    
35.                         LUXmap[d*wp1]=0x1b;        //NW
    
36.                         LUXmap[(d+1)*wm1]=0x1b;        //SW
    
37.                         var fill_len=staidx-d;
    
38.                         for(var kk=0;kk<fill_len;kk++)
    
39.                         {
    
40.                                 var kk1d=kk+1+d;
    
41.                                 LUXmap[kk1d*LUXmap_width+d]=0xd8;        //NW-n
    
42.                                 LUXmap[d*LUXmap_width+kk1d]=0xb1;        //NW-w
    
43.                                 LUXmap[d*LUXmap_width+staidx+2+kk]=0x4e;        //SW-w
    
44.                                 LUXmap[kk1d*LUXmap_width+wm1-d]=0x27;        //SW-s
    
45.                         }
    
46.                         LUXmap[gibidx]=0x72;
    
47.                         gibidx+=wm1;
    
48.                 }
    
49.                
    
50.                
    
51.         }
    
52. 
    
53.         cur_lx_size=n;
    
54. }
    

复制代码

首先选定六阶LUX的两列作为"核"(第三列可由第一列算出来, 故省略), 这种"核"共3*19*16*2个,
透过穷举得出, 乘16应该是包含了旋转/镜像/内外互换等; 因那两组不对称的"例外组"在第一行或第二行而分成两类, 故乘2,
至于基本"核"为何是3x19=57个, 希望有板友能给出数学证明.

代码中

1. 
   
2. const LUXele=[
   
3.         [0x1b,0x2d,0x6c],
   
4.         [0xe1,0xb1,0xe4]
   
5. ];
   

复制代码

即是上述"核"中的一个, 其余一些可能的核有:

1. 
   
2. -xl        [0xc9,0x72,0xe1],        [0x1b,0x4e,0x4b]
   
3. -xl        [0xc9,0x72,0xe1],        [0x1e,0x4e,0x1b]
   
4. xlx        [0x27,0x2d,0x8d],        [0xe1,0xb1,0xe4]
   
5. xlx        [0x27,0x2d,0x8d],        [0xe4,0xb1,0xb4]
   
6. xlx        [0x72,0x78,0xd8],        [0x4b,0x1b,0x4e]
   
7. xlx        [0x72,0x78,0xd8],        [0x4e,0x1b,0x1e]
   
8. -xx        [0x93,0x8d,0xb1],        [0x4b,0xb1,0x4e]
   
9. ...等
   

复制代码

"核"中的hex数字实际上是四个2bit数字, 例如0x1b=0_1_2_3; 0x4e=1_0_3_2等, 表示四角的4!=24种排列.

选定了一个六阶核, 那么所有6+4N阶的LUXmap就能无须穷举试错地快速构造出来了, 即上述代码所做的事,
例如, 一个22阶的这种<最接近完美的>LUXmap看起来像这样:

1. 
   
2. 0x1b,0xb1,0xb1,0xb1,0xb1,                        0x9c,                        0x4e,0x4e,0x4e,0x4e,0x1b,        
   
3. 0xd8,        0x1b,0xb1,0xb1,0xb1,                0x9c,                        0x4e,0x4e,0x4e,0x1b,        0x72,
   
4. 0xd8,        0xd8,        0x1b,0xb1,0xb1,        0x9c,                0x4e,0x4e,0x1b,        0x72,        0x27,
   
5. 0xd8,        0xd8,        0xd8,        0x1b,0xb1,        0x9c,                0x4e,0x1b,        0x72,        0x27,        0x27,
   
6. 0xd8,        0xd8,        0xd8,        0xd8,        0x1b,0x2d,0x6c,        0x72,        0x27,        0x27,        0x27,
   
7. 0xe1,        0xe1,        0xe1,        0xe1,        0xe1,0xb1,0xe4,        0xb4,        0xb4,        0xb4,        0xb4]
   

复制代码

其中规律应该很易见, 就不多解说了.

其次是较不重要的实际幻方构造及LUXmap解码部分, 代码为:

1. 
   
2. function mkmgsq_4Np2(n)
   
3. {
   
4.         function fill_mir(y1,x1,zzsft)
   
5.         {
   
6.                 var vlu=ady+ ((lxv>>zzsft)&3) *mulp;
   
7.                 var ydx=(y0a+y1)*n+(x0a+x1);
   
8.                 ret[ydx]=vlu;
   
9.                 ret[lztm-ydx]=lztm-vlu;
   
10.         }
    
11. 
    
12.         function fill_nomir(y1,x1,zzsft) {ret[(y0a+y1)*n+(x0a+x1)]=ady+((lxv>>zzsft)&3)*mulp;}
    
13. 
    
14.         var oddhfn=n>>1;
    
15.         buildlx(n);
    
16. 
    
17.         var oddhf=odd_base_maker(oddhfn);
    
18.         var mulp=n*n;
    
19.         var lztm=mulp-1;
    
20.         var lztn=n-1;
    
21.         var ret = new Array(mulp);
    
22. 
    
23.         mulp>>=2;
    
24.         var oddhfhfn=(oddhfn>>1);
    
25. 
    
26.         var lxstp=LUXmap_height-oddhfhfn-1;
    
27. 
    
28.         for(var y=0;y<oddhfn;y++)
    
29.         {
    
30.                 var y0a=y<<1;
    
31.                 for(var x=0;x<oddhfhfn;x++)
    
32.                 {
    
33.                         var ady=oddhf[y*oddhfn+x];
    
34.                         var x0a=x<<1;
    
35.                         var lxv=LUXmap[(x+lxstp)*LUXmap_width+y+lxstp];
    
36.                         fill_mir(0,0,6);
    
37.                         fill_mir(0,1,4);
    
38.                         fill_mir(1,0,2);
    
39.                         fill_mir(1,1,0);
    
40.                         
    
41.                 }
    
42.                 var ady=oddhf[y*oddhfn+x];
    
43.                 var lxv=LUXmap[(oddhfhfn+lxstp)*LUXmap_width+y+lxstp];
    
44.                 var x0a=oddhfhfn<<1;
    
45.                 fill_nomir(0,0,6);
    
46.                 fill_nomir(0,1,4);
    
47.                 fill_nomir(1,0,2);
    
48.                 fill_nomir(1,1,0);
    
49.                
    
50.         }
    
51. 
    
52.         return ret;
    
53. 
    
54. }
    

复制代码

odd_base_maker()是一个奇幻方产生器, 可权且用最简单的siamese法奇数阶幻方产生器代之:

1. 
   
2. var siamcache={3:[7,0,5,        2,4,6,        3,8,1],5:[10, 9, 3, 22, 16,
   
3. 17, 11, 5, 4, 23,
   
4. 24, 18, 12, 6, 0,
   
5. 1, 20, 19, 13, 7,
   
6. 8, 2, 21, 15, 14]};
   
7. 
   
8. function simplesiam(n)
   
9. {
   
10.         return siamcache[n];
    
11. }
    
12. 
    
13. var odd_base_maker=simplesiam;
    

复制代码

在下一篇文章中, 这个奇数阶幻方产生器会用上我发现的奇数dim有限域matmul产生器,
这种奇数dim的异或表(xor表, xor是有限域中不进位的"加法"), 有着挺漂亮的规律, 例如其右转45度后:

五阶:

七阶:

十一阶:

这也是就我所知还未被人发现过的.

李光伦akacha_tw

附一个二十六阶的这种幻方, 幻和=8775, 对称组相加等于26*26-1=675:

1. 
   
2. 0 169        649 311        612 274        587 249        562 224        537 199        668 499        149 487        124 462        99 437        74 412        218 556        24 193
   
3. 338 507        480 142        443 105        418 80        393 55        368 30        161 330        318 656        293 631        268 606        243 581        49 387        362 531
   
4. 
   
5. 504 673        154 323        624 286        610 272        573 235        548 210        523 354        4 342        135 473        110 448        254 592        60 229        204 35
   
6. 166 335        492 661        455 117        441 103        404 66        379 41        16 185        173 511        304 642        279 617        85 423        398 567        542 373
   
7. 
   
8. 359 528        347 516        140 309        622 284        585 247        571 233        534 365        158 496        146 484        290 628        96 265        240 71        215 46
   
9. 21 190        9 178        478 647        453 115        416 78        402 64        27 196        327 665        315 653        121 459        434 603        578 409        553 384
   
10. 
    
11. 370 539        501 670        489 658        126 295        608 270        583 245        546 377        25 363        170 508        132 301        276 107        251 82        226 57
    
12. 32 201        163 332        151 320        464 633        439 101        414 76        39 208        194 532        1 339        470 639        614 445        589 420        564 395
    
13. 
    
14. 381 550        356 525        344 513        475 644        112 281        594 256        569 400        206 544        156 325        324 155        287 118        262 93        237 68
    
15. 43 212        18 187        6 175        137 306        450 619        425 87        62 231        37 375        494 663        662 493        625 456        600 431        575 406
    
16. 
    
17. 392 561        367 536        498 667        486 655        461 630        98 267        580 411        555 48        192 23        180 11        299 130        285 116        248 79
    
18. 54 223        29 198        160 329        148 317        123 292        436 605        73 242        217 386        530 361        518 349        637 468        623 454        586 417
    
19. 
    
20. 415 246        378 209        353 184        341 172        472 303        109 447        422 591        397 59        541 34        672 165        660 153        635 128        598 91
    
21. 584 77        547 40        522 15        510 3        641 134        616 278        84 253        228 566        372 203        503 334        491 322        466 297        429 260
    
22. 
    
23. 258 89        221 52        207 38        326 157        314 145        289 458        602 433        70 239        383 552        358 527        346 515        477 646        452 621
    
24. 596 427        559 390        545 376        664 495        652 483        627 120        264 95        408 577        45 214        20 189        8 177        139 308        114 283
    
25. 
    
26. 269 100        244 75        219 50        182 13        12 181        300 638        444 613        588 250        56 225        369 538        500 669        488 657        463 632
    
27. 607 438        582 413        557 388        520 351        350 519        131 469        275 106        419 81        394 563        31 200        162 331        150 319        125 294
    
28. 
    
29. 280 111        255 86        230 61        36 205        336 674        143 481        467 636        599 261        574 236        42 211        355 524        343 512        474 643
    
30. 618 449        593 424        568 399        374 543        167 505        312 650        298 129        430 92        405 67        380 549        17 186        5 174        136 305
    
31. 
    
32. 291 122        266 97        72 241        216 554        22 360        10 348        479 648        611 273        597 259        560 222        28 197        497 666        485 654
    
33. 629 460        604 435        410 579        47 385        191 529        179 517        310 141        442 104        428 90        391 53        366 535        159 328        147 316
    
34. 
    
35. 302 133        108 277        252 590        58 396        33 371        164 502        490 659        634 296        609 271        572 234        558 220        14 183        340 509
    
36. 640 471        446 615        83 421        227 565        202 540        333 671        321 152        465 127        440 102        403 65        389 51        352 521        2 171
    
37. 
    
38. 144 313        288 626        94 432        69 407        44 382        19 357        345 514        645 307        620 282        595 257        570 232        533 195        168 337
    
39. 482 651        119 457        263 601        238 576        213 551        188 526        176 7        476 138        451 113        426 88        401 63        364 26        506 675
    

复制代码

李光伦akacha_tw

附: 关于siamese法奇数阶幻方的"正确方位"

用玄一点的话说即幻方的"正向".
一般认为, 幻方是可以随意翻转的, 随意翻转并不影响纵横列相加相等等一般认定的幻方性质.

然而我认为幻方的固有性质是多于"纵横列相加相等"的, "纵横列相加相等"只是人类依据看上去"最简单的"3x3幻方而对所有幻方给出的一个过早推断.

因为不巧的是, 看上去"最简单的"3x3幻方恰好是一个特例, 三及其奇倍数阶的幻方严格来说并不是"奇数阶幻方".
同样的不凑巧发生在过去人对GF(2)以外的异或xor定义上, 将GF(2)以外dim=x阶有限域中a数与b数之异或定义为((a+b) mod x)同样是错误的, 理由会在下一篇文章详细说.

回来说siamese法构成的幻方, 假定存在函数f(y*n+x)=a*n+b, 即存在一个能将n阶幻方的一维坐标y*n+x转变为其数值a*n+b的函数,
那么其反函数f_neg(a*n+b)=y*n+x的意义就是将数值换算为所在的一维坐标.

在siamese法构成的奇数阶幻方中, 只有一种幻方"方位"能满足f(v)+f_neg(v)=n^2-1这条关系式, 即例如以五阶为例, 以如下"方位"排布的siamese幻方:

1. 10, 9, 3, 22, 16,
   
2. 17, 11, 5, 4, 23,
   
3. 24, 18, 12, 6, 0,
   
4. 1, 20, 19, 13, 7,
   
5. 8, 2, 21, 15, 14
   

复制代码

以左上角为(x=0, y=0), 可得f(0*5+0)=10, 0*5+0=0为左上角方格的一维坐标,
可得f_neg(0)=2*5+4=14,
最终10+14=5*5-1=24

同样f(1*5+2)=5, f_neg(7)=3*5+4=19, 19+5同样为5*5-1=24

只有这个数值10在左上角x=0, y=0处; 数值0在y=2, x=4处, 如此排布的幻方, 能使幻方中所有元素满足上述关系式.
以此我称这样的排布为siamese法幻方的<正向>.
同时可知幻方的固有性质并不止于"纵横列相加相等".