第19講 座標の工夫による魔方陣自動生成ソフトの高速化

第８話 各セルに入れる数字の始まりを変える
コード主要部分再掲
long f(int **x,int n,long cn,int g){
　　 int i,j,s,t,w,v;
　　 s=g/n;
　　 t=g%n;
　　 for(i=1;i<n*n+1;i++){
　　　　　x[s][t]=i;
　　　　　v=0;
　　　　　if(k[i-1]==0){
　　　　　　　　k[i-1]=1;
　　　　　　　　v=1;
　　　　　}
　　　　　else{
　　　　　　　　goto tobi;
　　　　　}
　　　　　if(s==n-1 && t==n-1){
　　　　　　　 w=0;
　　　　　　　 for(j=0;j<n;j++)w=w+x[j][j];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　if(s==n-1 && t==0){
　　　　　　　 w=0;
　　　　　　　 for(j=0;j<n;j++)w=w+x[j][n-1-j];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　if(s==0 && t==n-2){
　　　　　　　 w=0;
　　　　　　　 for(j=0;j<n;j++)w+=x[s][j];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　for(j=0;j<n;j++)w+=x[j][t];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　if(s>0 && s<n-1 && t==n-1){
　　　　　　　 w=0;
　　　　　　　 for(j=0;j<n;j++)w+=x[s][j];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　if(s==n-1 && t>0 && t<n-1){
　　　　　　　 w=0;
　　　　　　　 for(j=0;j<n;j++)w+=x[j][t];
　　　　　　　 if(w!=n*(n*n+1)/2)goto tobi;
　　　　　}
　　　　　if(g+1<n*n){
　　　　　　　 cn=f(x,n,cn,g+1);
　　　　　　　 if(cn==100)return(cn);
　　　　　}
　　　　　else{
　　　　　　　 h(x,n);
　　　　　　　 cn++;
　　　　　　　 if(cn==100)return(cn);
　　　　　}
　　　　　tobi:;
　　　　　if(cn==100)return(cn);
　　　　　if(v==1)k[i-1]=0;
　　 }
　　 return(cn);
}


このプログラムでは、各セルに
４次魔方陣の場合
１，２，３，４，・・・・，１５，１６
５次魔方陣場合
１，２，３，４，・・・・，２４，２５
と順番に入れています。
ですから、セルは

のように動いていきます。
４次魔方陣の場合は、すでに破綻しています。

最後のセルに最大の２５入れても、
合計を３４にすることは出来ません。
それで1つ前の段階の修正を余儀なくされ、

までいって、次ぎに

最初の対角線が完成します。


もし順番に入れていくのではなく、
各セル毎に
１４，１５，１６，１，２，３，４，５，６，７，８，９，１０，１１，１２，１３
４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１，２，３
９，１０，１１，１２，１３，１４，１５，１６，１，２，３，４，５，６，７，８
などと、始まりの数字を変えることができれば、

のような数字の重複を防ぐことが出来て、

早い段階の破綻を防ぐことが出来ます。
それぞれの場合、

1つ前に戻って修正をし続ける必要がなく、
圧倒的に効率が良くなります。

では、各セル毎の始まりの数字を変えるにはどうしたらよいでしょうか。