第２０講 一般種法による魔方陣ソフトの高速化
第４話 新しい番号付けのヒントその４

１８次の場合

では他の色の場合の一般化をしておきましょう。
数列５２，８３，１１２，１３９，１６４，１８７，２０８，２２７，２４４の一般項は、
２＊ｎ＊ｊ＋ｎ−ｊ＊ｊ−２＊ｊ＋１であり、
３６，６８，９８，１２６，１５２，１７６，１９８，２１８，２３６の一般項は、
２＊ｎ＊ｊ−ｊ＊ｊ−ｊ+２であることを前話で学びました。
したがって、

等の範囲は２＊ｎ＊ｊ＋ｎ−ｊ＊ｊ−２＊ｊ＋１≦ｉ＜２＊ｎ＊（ｊ＋１）−（ｊ＋１）＊（ｊ＋１）−（ｊ＋１）+２＝２＊ｎ＊ｊ＋２＊ｎ−ｊ＊ｊ−３＊ｊ
（後半のｊは一つずれます。例えば、０列目は５２≦ｉ＜６８ですが、５２は１番目の項であるのに対して６８は２番目の項だからです。）

白い番号（５２，８３，１１２など）のときｉ＝２＊ｎ＊ｊ＋ｎ−ｊ＊ｊ−２＊ｊ＋１ですから、
次のように一般化でいます。
for(j=1;j<m+1;j++){　　　　　　　　　　　　　　　//ｍはｎ／２
　　if((i>=2*n*j+n-j*j-2*j+1) && (i<2*n*j+2*n-j*j-3*j)){
　　　　x[i]=j-1;
　　　　y[i]=i-(2*n*j+n-j*j-2*j+1)+j;
　　　　if(x[i]>=n-y[i]-1)y[i]++;　　　　　　　//これは逆対角線を跨ぐときの処理
　　}
}

次に、オレンジの場合を考えるために

２つの数列２５２、２６８，２８２，２９４，３０４，３１２，３１８，３２２と２６０，２７５，２８８，２９９，３０８，３１５，３２０，３２３を考えます。
まず、数列２５２、２６８，２８２，２９４，３０４，３１２，３１８，３２２の階差は、
（ｎ／２−ｊ）＋（ｎ／２−ｊ）＝２＊（ｎ／２−ｊ）＝ｎ−２＊ｊ（ｊは表の一番右で、ｙとの対応はｙ＝ｊ＋ｍ−１すなわちｊ＝ｙ−ｍ＋１、またｍ＝ｎ／２）
で初項２５２＝ｎ＊ｎ＊（３／４）＋ｎ／２＝３＊ｍ＊ｍ＋ｍですから、
数列２５２、２６８，２８２，２９４，３０４，３１２，３１８，３２２の一般項は、
３＊ｍ＊ｍ＋ｍ＋Σ（ｎ−２＊ｋ）（ｋはｋ＝１からｋ＝ｊ−１まで）＝３＊ｍ＊ｍ＋ｍ＋（ｊ−１）＊（ｎ−ｊ）

数列２６０，２７５，２８８，２９９，３０８，３１５，３２０，３２３の階差は、
（ｎ／２−（ｊ−１））＋｛（ｎ／２−（ｊ−１）−１｝＝ｎ＋１−２＊ｊ
で初項２６０＝３＊ｍ＊ｍ＋ｍ＋ｎ／２−１＝３＊ｍ＊ｍ＋２＊ｍ−１なので、一般項は
３＊ｍ＊ｍ＋２＊ｍ−１＋Σ（ｎ＋１−２＊ｊ）（ｋはｋ＝２からｋ＝ｊ−１まで）＝３＊ｍ＊ｍ＋（ｊ−１）＊（ｎ＋１−ｊ）

ｙ［ｉ］は表の紺（ｙ）なのでｊ＋ｍ−１
ｘ［ｉ］は薄緑の番号（２５２，２８６，２８２など）のときｉ＝３＊ｍ＊ｍ＋ｍ＋（ｊ−１）＊（ｎ−ｊ）なので、
ｘ［ｉ］＝ｉ−（３＊ｍ＊ｍ＋ｍ＋（ｊ−１）＊（ｎ−ｊ））＋ｊ＋ｍ

したがって、オレンジの部分は
for(j=1;j<m;j++){　　　//ｍはｎ／２
　　if((i>=3*m*m+m+(j-1)*(n-j)) && (i<3*m*m+j*(n-j))){
　　　　y[i]=j+m-1;
　　　　x[i]=i-(3*m*m+m+(j-1)*(n-j))+j+m;
　　}
}
と一般化できます。

最後の薄紫は、ｉの範囲は
３＊ｍ＊ｍ＋（ｊ−１）＊（ｎ＋１−ｊ）≦ｉ＜３＊ｍ＊ｍ＋ｍ＋（ｊ−１）＊（ｎ−ｊ））（オレンジと薄紫は元々番号が１つずれているのでｊ＋１とする必要がない。）であり、

ｘ［ｉ］は表の赤（ｘ）なのでｊ＋ｍ−2（ｊは２から始まっているのに注意）、
ｙ［ｉ］は列の最初の番号（２６０，２７５，２８８など）のときｉ＝３＊ｍ＊ｍ＋（ｊ−１）＊（ｎ＋１−ｊ）なので、
ｙ［ｉ］＝ｉ−（３＊ｍ＊ｍ＋（ｊ−１）＊（ｎ＋１−ｊ））＋ｊ＋ｍ−１なので
薄紫の部分は
for(j=2;j<m+1;j++){　　　　　//ｍはｎ／２
　　if((i>=3*m*m+(j-1)*(n-(j-1))) && (i<3*m*m+m+(j-1)*(n-j))){
　　　　x[i]=j+m-2;
　　　　y[i]=i-(3*m*m+(j-1)*(n-(j-1)))+j+m-1;
　　}
}
と一般化できます。

では次話では、奇数版の番号付けの解答を示しましょう。

第２０講第３話へ 第２０講第５話へ



VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座