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

お約束の通り１行１行解説していきます。
　　　　　　　　　kk=rand()%n;
はkk=rand()%n*n;　から変更されています。
n*nがnに変更された理由は何でしょうか。
a[y[g]][x[g]]に入れる数字が、１からn*nだったのに対して、
特殊種を作るソフトでは、０からｎ−１になっているからです。
kkは、整数をｎで割った余りですから、ｎ未満の整数
すなわち、０，１，２，３，・・・，ｎ−１のいずれかになります。
　　　　　　　　　　　kkk=(kk+i)%n;
についても同様です。ｎ＊ｎがｎに変更されています。
ｋｋが２であったとすると、ｋｋｋは
２，３，４，・・・，ｎ−１，０，１と動いていきます。
ｋｋｋははじまりを０に固定しないために用意されました。
はじまりを０，１，２，３，・・・，ｎ−１のいずれかをランダムに選ぶことによって、
任意性を高めているのです。ランダムにすることによって、作成速度を速めているのです。
次の、
　　　　　　　　　　　h=1;
　　　　　　　　　　　if(g<n){
　　　　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　　　　if(a[y[g]][x[g]]==a[j][j]){
　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
　　　　　　　　　　　}

if文if(g<n)は対角線の重複を調べています。

ではh=1;　は何のために用意されているのでしょうか。
ｈの役割は何でしょうか。
特殊種は、

□0□ □1□ □2□ □3□ □4□
3 4 0 1 2
1 2 3 4 0
4 0 1 2 3
2 3 4 0 1

対角線上にも列にも行にも同じ数字が並んではいけません。
ｈ＝１；　以降の探索は、対角線→逆対角線→列→行の順で探索されますが、
対角線、逆対角線、列、行のいずれかに数字の重複が発見されれば、
それ以上の探索は必要なくなります。
一つでも禁則を犯せば特殊種でなくなってしまうので、
例えば、対角線上で重複が存在すれば、逆対角線、列、行の重複探索は無駄になります。
次のような例を考えてみましょう。

□0□ □1□ □2□ □3□ □4□
3 0 0 1 2
1 2 3 4 0
4 0 1 2 3
2 3 4 0 1

もうすでに禁則を犯しています。
ですから、逆対角線上の重複がないか
列の重複はないか、行の重複がないか、
は調べる必要がなく、数字を次の場合に進めて















□0□ □1□ □2□ □3□ □4□
3 3 0 1 2
1 2 3 4 0
4 0 1 2 3
2 3 4 0 1

対角線上→逆対角線上→列→行に重複がないか、
順に調べればよいのです。
もちろんこの場合は逆対角線上にも同一列上にも同一行上にも、
数字が入っていないわけですから、
重複はなく、次の世界へと進めるわけです。

□0□ □1□ □2□ □3□ □4□
3 3 0 1 2
1 2 3 4 0
4 0 1 2 3
2 3 4 0 1


ｈは何のために用意されているかと申しますと、
無駄な重複探索をやめさせるためにあります。
左のように重複が発見されると、
if(a[y[g]][x[g]]==a[j][j]){
　　　h=0;
　　　break;
}
によって、h=0となります。
以後のコーティングは、必ず
if(h==1){
から始まっていますから、
h=0ならすべて実行されないわけです。
C言語にもgoto文がありますので、
これですべての行を飛ばしてもいいわけですが、
goto文はスパゲティプログラムの元凶とされてきました。



BASICではこのGOTO文が多用され、あっちいったりこっちに行ったりで全体がスパゲティのように混線し、
訳の分からないプログラムになることが多かったわけです。
C言語では、そこが反省され基本的にはgoto文は使わず、構造化プログラミングという見通しのよいプログラミングが心がけられています。

尚、break;の役割ですが、

□0□ □1□ □2□ □3□ □4□
3 3 0 1 2
1 2 2 4 0
4 0 1 1 3
2 3 4 0 0

例えば、一番目に重複が発見された場合
for(j=0;j<g;j++){
　　if(a[y[g]][x[g]]==a[j][j]){
　　　　h=0;
　　　　break;
　　}
}
３，２，１との重複探査は意味がありません。
なので、for文を強制的にやめさせて時間を節約しているのです。


















第１９講第２話へ 第１９講第４話へ