第１９講 特殊種による魔方陣ソフトの高速化
第４話 特殊種ソフトソース解説その２（逆対角線）

今日は、
　　　　　　　　　　　if(h==1){
　　　　　　　　　　　　　if(x[g]==n-y[g]-1 && g>n-1){
　　　　　　　　　　　　　　　if(a[y[g]][x[g]]==a[y[g]][y[g]])h=0;
　　　　　　　　　　　　　　　if(h==1)if(a[y[g]][x[g]]==a[x[g]][x[g]])h=0;
　　　　　　　　　　　　　　　if(n%2==1)if(a[y[g]][x[g]]==a[m][m])h=0;
　　　　　　　　　　　　　　　if(h==1 && y[g]>0){
　　　　　　　　　　　　　　　　　for(j=0;j<y[g];j++){
　　　　　　　　　　　　　　　　　　　if(a[y[g]][x[g]]==a[j][n-j-1]){
　　　　　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
　　　　　　　　　　　}
の部分を解説します。
ここは、逆対角線の重複を調べています。
逆対角線に重複が発見されたら、ｈを０にして以後の処理が行われないようにしているわけです。
探索される範囲x[g]==n-y[g]-1 && g>n-1に注目してください。x[g]==n-y[g]-1はy[g]==n-x[g]-1でも同じです。
これは1度、解説していますが、なぜ対角線になるのかもう一度確認しておきましょう。
x[g]==n-y[g]-1でトレースしてみましょう。
y[g]が０，１，・・・，ｎ−２，ｎ−１と動いていくと、x[g]は逆にｎ−１，ｎ−２，・・・，２，１を動いていきます。

（赤の番号はx、濃紺の番号はy、ピンクの番号はgに対応）
x[g]==n-y[g]-1の場合は、上から斜め下への下がっていきます。
の場合はどうでしょうか。
x[g]が０，１，・・・，ｎ−２，ｎ−１と動いていくと、y[g]は逆にｎ−１，ｎ−２，・・・，２，１となります。
今度はしたから斜め上に上がります。
ですからx[g]==n-y[g]-1とy[g]==n-x[g]-1の２つは同じ逆対角線を表しますが、
番号付けｇに対応しているのは、x[g]==n-y[g]-1の方です。
範囲指定としては、y[g]==n-x[g]-1でもよいのですがコーティングが複雑になるので、x[g]==n-y[g]-1が採用されているわけです
因みに、y[g]==n-x[g]-1でコーティングするとどうなるか考えてみてください。

さて、ではg>n-1は何のために付けられているのでしょうか。
偶数次（４次）と奇数次（５次）の両方を例示したのは、この説明のためです。
偶数次の場合は、範囲指定はx[g]==n-y[g]-1のみで充分です。
ところが、奇数次の場合対角線と逆対角線が交錯するセル

が存在するので、
g>n-1を入れなくてはならないのです。
なぜなら、

と来たときに、

のセルとは比較する必要はありません。
なぜなら、まだこのセルには数字が入っていないので、
初めから重複の可能性はないわけです。
無駄な検索はできるだけさせない、これが高速化するための鉄則です。

範囲指定x[g]==n-y[g]-1 && g>n-1については後理解して頂けたと思います。
次の３行
　　　　　　　　　　　　　　　if(a[y[g]][x[g]]==a[y[g]][y[g]])h=0;
　　　　　　　　　　　　　　　if(h==1)if(a[y[g]][x[g]]==a[x[g]][x[g]])h=0;
　　　　　　　　　　　　　　　if(n%2==1)if(a[y[g]][x[g]]==a[m][m])h=0;
は何をしているのでしょう。

左のセルの色と上のコーティングの色を対応させて読んでください。

各色コーティングでは

がコーティングと同色対応のセルと
重複していないか調べているわけです。


if(a[y[g]][x[g]]==a[y[g]][y[g]])h=0;では、

との重複を




if(h==1)if(a[y[g]][x[g]]==a[x[g]][x[g]])h=0;では、

との重複を





最後if(n%2==1)if(a[y[g]][x[g]]==a[m][m])h=0;では、

との重複を調べているわけです。
数字がすでに入っているのでそれらと重複していないか調べなければならないわけです。
最後のif(n%2==1)if(a[y[g]][x[g]]==a[m][m])h=0;は奇数の場合のみ調べればよいので、
n%2==1が入っているです。

第１９講第３話へ 第１９講第５話へ

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