一个单偶数n (n=4N+2) 阶最接近完全正负对称幻方的构造法
介绍一个不需穷举试错的快速单偶数幻方构造法, 附关键部分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中每一对(点对称的)元素, 即M与M, 皆满足M+M=n^2-1之关系的排列法不存在.
至少需有两对(相加为n^2-1的)互补元素不是对中心点对称的. 例如以下6阶幻方, 幻和=105:
07 16 27 18 32 05
25 34 00 09 14 23
02 20 22 31 24 06
29 11 04 13 15 33
12 21 35 26 01 10
30 03 17 08 19 28
除00--35与09--26外, 其余对称元素相加皆等于6*6-1=35, 例如7--28, 15--20等.
再以10阶为例, 以下幻方幻和=495:
00 25 89 39 96 71 42 92 08 33
50 75 64 14 21 46 17 67 58 83
72 97 18 43 80 55 79 04 36 11
22 47 68 93 05 30 29 54 86 61
59 34 01 51 62 87 73 23 90 15
84 09 76 26 12 37 48 98 65 40
38 13 45 70 94 69 06 31 52 77
88 63 95 20 44 19 56 81 02 27
16 41 32 82 53 78 85 35 24 49
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若写成线性一维坐标, 即为M, 会编程的应该对此很熟悉,
如此前文所谓"对中心点对称"的二元素, 以一维坐标表示即M与M, 这两个一维坐标相加对消后只剩下n^2-1, 与前述"正负数"相加为n^2-1共享同一规律.
现在我所谓<正负对称>的意义应该很明瞭了, 指的即是<既在数值上正负互补, 又在坐标上正负互补>,
以此故我将这种对称性视为一个幻方是否完美的重要指标, 在这个意义上我称这种<只有两对互补元素不对称的>单偶数阶幻方为<最接近完美的>.
-构造法(代码):
这种单偶数n的<最接近完美幻方>, 是由一个(n>>1)阶的奇幻方与一组通用LUXmap构成的,
就我在网上查幻方LUX构造法所知, 这种无需试错的LUXmap构造法应该尚未被人发现过.
首先是LUXmap的构造法, 这是本幻方构造法的关键所在:
var cur_lx_size=0;
const LUXele=[
,
];
function buildlx(n)
{
if(n<=cur_lx_size){return;}
LUXmap_width=n>>1;
var qoddn=LUXmap_width>>1;
LUXmap_height=qoddn+1;
LUXmap = new Uint8Array(LUXmap_width*LUXmap_height);
var staidx=qoddn-1;
var lyn0=staidx*(LUXmap_width+1);
LUXmap.set(LUXele, lyn0);
lyn0+=LUXmap_width;
LUXmap.set(LUXele, lyn0);
if(staidx>0)
{
lyn0-=staidx;
var toSouth=3+staidx;
var wm1=LUXmap_width-1;
var wp1=LUXmap_width+1;
var gibidx=LUXmap_width+wm1;
for(var d=0;d<staidx;d++)
{
LUXmap=0x9c; //west
var fynlin=lyn0+d;
LUXmap=0xe1; //north
LUXmap=0xb4; //south
LUXmap=0x1b; //NW
LUXmap[(d+1)*wm1]=0x1b; //SW
var fill_len=staidx-d;
for(var kk=0;kk<fill_len;kk++)
{
var kk1d=kk+1+d;
LUXmap=0xd8; //NW-n
LUXmap=0xb1; //NW-w
LUXmap=0x4e; //SW-w
LUXmap=0x27; //SW-s
}
LUXmap=0x72;
gibidx+=wm1;
}
}
cur_lx_size=n;
}
首先选定六阶LUX的两列作为"核"(第三列可由第一列算出来, 故省略), 这种"核"共3*19*16*2个,
透过穷举得出, 乘16应该是包含了旋转/镜像/内外互换等; 因那两组不对称的"例外组"在第一行或第二行而分成两类, 故乘2,
至于基本"核"为何是3x19=57个, 希望有板友能给出数学证明.
代码中
const LUXele=[
,
];
即是上述"核"中的一个, 其余一些可能的核有:
-xl ,
-xl ,
xlx ,
xlx ,
xlx ,
xlx ,
-xx ,
...等
"核"中的hex数字实际上是四个2bit数字, 例如0x1b=0_1_2_3; 0x4e=1_0_3_2等, 表示四角的4!=24种排列.
选定了一个六阶核, 那么所有6+4N阶的LUXmap就能无须穷举试错地快速构造出来了, 即上述代码所做的事,
例如, 一个22阶的这种<最接近完美的>LUXmap看起来像这样:
0x1b,0xb1,0xb1,0xb1,0xb1, 0x9c, 0x4e,0x4e,0x4e,0x4e,0x1b,
0xd8, 0x1b,0xb1,0xb1,0xb1, 0x9c, 0x4e,0x4e,0x4e,0x1b, 0x72,
0xd8, 0xd8, 0x1b,0xb1,0xb1, 0x9c, 0x4e,0x4e,0x1b, 0x72, 0x27,
0xd8, 0xd8, 0xd8, 0x1b,0xb1, 0x9c, 0x4e,0x1b, 0x72, 0x27, 0x27,
0xd8, 0xd8, 0xd8, 0xd8, 0x1b,0x2d,0x6c, 0x72, 0x27, 0x27, 0x27,
0xe1, 0xe1, 0xe1, 0xe1, 0xe1,0xb1,0xe4, 0xb4, 0xb4, 0xb4, 0xb4]
其中规律应该很易见, 就不多解说了.
其次是较不重要的实际幻方构造及LUXmap解码部分, 代码为:
function mkmgsq_4Np2(n)
{
function fill_mir(y1,x1,zzsft)
{
var vlu=ady+ ((lxv>>zzsft)&3) *mulp;
var ydx=(y0a+y1)*n+(x0a+x1);
ret=vlu;
ret=lztm-vlu;
}
function fill_nomir(y1,x1,zzsft) {ret[(y0a+y1)*n+(x0a+x1)]=ady+((lxv>>zzsft)&3)*mulp;}
var oddhfn=n>>1;
buildlx(n);
var oddhf=odd_base_maker(oddhfn);
var mulp=n*n;
var lztm=mulp-1;
var lztn=n-1;
var ret = new Array(mulp);
mulp>>=2;
var oddhfhfn=(oddhfn>>1);
var lxstp=LUXmap_height-oddhfhfn-1;
for(var y=0;y<oddhfn;y++)
{
var y0a=y<<1;
for(var x=0;x<oddhfhfn;x++)
{
var ady=oddhf;
var x0a=x<<1;
var lxv=LUXmap[(x+lxstp)*LUXmap_width+y+lxstp];
fill_mir(0,0,6);
fill_mir(0,1,4);
fill_mir(1,0,2);
fill_mir(1,1,0);
}
var ady=oddhf;
var lxv=LUXmap[(oddhfhfn+lxstp)*LUXmap_width+y+lxstp];
var x0a=oddhfhfn<<1;
fill_nomir(0,0,6);
fill_nomir(0,1,4);
fill_nomir(1,0,2);
fill_nomir(1,1,0);
}
return ret;
}
odd_base_maker()是一个奇幻方产生器, 可权且用最简单的siamese法奇数阶幻方产生器代之:
var siamcache={3:,5:[10, 9, 3, 22, 16,
17, 11, 5, 4, 23,
24, 18, 12, 6, 0,
1, 20, 19, 13, 7,
8, 2, 21, 15, 14]};
function simplesiam(n)
{
return siamcache;
}
var odd_base_maker=simplesiam;
在下一篇文章中, 这个奇数阶幻方产生器会用上我发现的奇数dim有限域matmul产生器,
这种奇数dim的异或表(xor表, xor是有限域中不进位的"加法"), 有着挺漂亮的规律, 例如其右转45度后:
五阶:
七阶:
十一阶:
这也是就我所知还未被人发现过的.
附一个二十六阶的这种幻方, 幻和=8775, 对称组相加等于26*26-1=675:
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
附: 关于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幻方:
10, 9, 3, 22, 16,
17, 11, 5, 4, 23,
24, 18, 12, 6, 0,
1, 20, 19, 13, 7,
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法幻方的<正向>.
同时可知幻方的固有性质并不止于"纵横列相加相等".
页:
[1]