第１話 末項確定法とは?

今回も
初心者のための VC++ 入門 （C++ 入門） 講義 基礎から応用まで（第３部）
第21講第1話末項確定法とは?
から、引用させて頂きます。
－－－以下引用－－－

今回はいつもと手法を変えて、
最初に、今回の成果を最初に紹介した後に、
末項確定法とは何か説明しましょう。
以下のデータは各次魔方陣を１００個作るのにかかった時間です。

１個あたり０．０１５９１２秒です。
前話のデータが０．０７２８４秒ですから、約４．６倍のスピード差です。
さらに、10次魔方陣の場合

1個あたり０．３９８８９２秒ですから、約５．６倍です。
今までソフトがバージョンアップする度に、
１万倍とか１１００万倍とかとう桁外れの性能アップを見せていたのに比べるとかなり地味に見えるかもしれませんが、
結構大きな戦果だと思います。
プログラミングの世界では、１．１倍でも大きな成果です。
（例えば、数独問題作成ソフトのスピードを１．１倍にするのに私は数日も場合によっては数週間費やしていました。
皆さんからすれば結果だけ見ているので、その苦労は見えないと思いますが、
プログラミングとは地味な研究の積み重ねなのです。
ただ、前々話で紹介したようにときには驚愕の成果を見せることもあります。）
ですから５，６倍はかなり大きな成果です。
さらに、今回の改良によって１１次魔方陣も１個あたり約０．０５６秒でできています。
前話のときは途中で実験を打ち切ってしまったので、単純比較はできませんが、
２０秒まで探索範囲を広げて、６０分も実験を続けましたが最適乱数系列を発見できませんでしたので、
仮に前話のソフトが２０秒であると前提しても、
２０÷０．０５６＝約３６０倍です。

末講確定法とは、水色以外のセルについては、初めから入る数字は確定していることに、
着眼した方法です。
例えば、

と来たときに、青のセルに入る数字は決まっています。

（表を見るときには、セルに入っている数字がセル番号のｇかそのセルに実際に入っている数字かを常に区別してください。
上表の数字は、セル番号ｇではなく、そのセルに入っている実際の数字です。
本講義においては、セル番号ｇのときは基本的にはピンクとしています。）
６＋４＋９＋４＋１＋０＋８＋３＋４＝３９
対角線の合計は、
０＋１＋２＋３＋４＋５＋６＋７＋８＋９＝４５
ですから、

に入る数字は
４５－３９＝６
と確定してしまうのです。


ですから、このセルについてはfor文で探索するのは無駄です。

に来たら、for文は通らないで次の世界（ｇ＋１）に進むか、
前の世界（ｇ－１）に戻るしかないのです。
戻る場合の言うのは、例えば

なら、６＋４＋９＋４＋１＋０＋８＋０＋２＝３４ですが、
合計の４５との差をとると、４５－３４＝１１

にはいる最大数は９ですから、
このセルのある対角線の合計を４５にするのは不可能になっているわけです。
この場合には1つ前のセル

に戻ってやり直すしかありません。



あるいは

の場合も６＋４＋９＋４＋１＋２＋８＋５＋７＝４６となり、

に入る数字が－１となってしまいこれも禁則に反します。
セルに入る数字は０から９までですから。
この場合にも

に戻ってやり直すしかありません。


－－－以上引用－－－

末項確定法とは、
一番最後の項（セル）は決まっていることに着目する
魔方陣自動生成方法です。
確定できるセルは、

少なくとも、20カ所に上ります。
皆さん、
前講で作った対角線法魔方陣自動生成ソフト
#include<iostream>
#include <time.h>
using namespace std;
long f(int *k,int **x,int n,long cn,int g,int *p,int *q);
void ts(int **x,int n,int *p,int *q);
void h(int **x,int n);
void syokika(int n,int *k);
void zh(int n,int *p,int *q);
void main(){
　　 int n;
　　 cout<<"何次魔方陣を生成しますか？"<<endl;
　　 scanf("%d",&n);
　　 int **x=(int **)malloc(sizeof(int)*n);
　　 for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*n);
　　 int *k=(int *)malloc(sizeof(int)*n*n);
　　 int p[100],q[100];
　　 cout<<endl;
　　 clock_t hj,ow; //clock_t型の宣言、プログラム開始時間を取得するための変数
　　 hj=clock();
　　 syokika(n,k);
　　 zh(n,p,q);
　　 //ts(x,n,p,q);
　　 //cout<<n<<"次魔方陣が"<<f(k,x,n,0,0)<<"個生成されました。"<<endl;
　　 ow=clock();
　　 cout<<"魔方陣生成にかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
}
void ts(int **x,int n,int *p,int *q){
　　 int i,j;
　　 for(i=0;i<n*n;i++)x[q[i]][p[i]]=i;
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　 if(x[i][j]<10)cout<<"0"<<x[i][j]<<" "; else cout<<x[i][j]<<" ";
　　　　　}
　　　　　cout<<endl;
　　 }
}
void zh(int n,int *p,int *q){
　　 int i,j,cn;
　　 int a[10][10];
　　 for(i=0;i<n;i++)
　　　　　for(j=0;j<n;j++)
　　　　　　　 a[i][j]=-1;
　　 for(i=0;i<n;i++)a[i][i]=i;
　　 cn=n;
　　 for(i=0;i<n;i++){
　　　　　if(a[i][n-1-i]==-1){
　　　　　　　 a[i][n-1-i]=cn;
　　　　　　　 cn++;
　　　　　}
　　 }
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　 if(a[i][j]==-1){
　　　　　　　　　　a[i][j]=cn;
　　　　　　　　　　cn++;
　　　　　　　 }
　　　　　}
　　 }
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　 p[a[i][j]]=j;
　　　　　　　 q[a[i][j]]=i;
　　　　　}
　　 }
}

void syokika(int n,int *k){
　　 for(int i=0;i<n*n;i++)k[i]=0;
}

long f(int *k,int **x,int n,long cn,int g,int *p,int *q){
　　 int i,j,s,t,w,v;
　　 s=q[g];
　　 t=p[g];
　　 int ii,iii;
　　 if(n==5)srand(14);
　　 ii=rand()%(n*n);
　　 for(iii=1;iii<n*n+1;iii++){
　　　　　i=(iii+ii)%(n*n)+1;
　　　　　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);
}

void h(int **x,int n){
　　 for(char i=0;i<n;i++){
　　　　　for(char j=0;j<n;j++){
　　　　　　　 if(n==3)cout<<x[i][j]<<" ";
　　　　　　　 if(n>3)if(x[i][j]<10)cout<<"0"<<x[i][j]<<" "; else cout<<x[i][j]<<" ";
　　　　　}
　　　　　cout<<endl;
　　 }
　　 cout<<endl;
}
参考ダウンロードファイル

を改良していきましょう。
といっても、ここまでついていらっしゃった優秀な皆さんでも、
いきなりすべてご自分で行うのは、大変ですから、
私と一緒に少しずつ改良していきましょう。
まず、対角線部分の改良から。
尚、改良効果を調べるために乱数は外して、
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;
に戻しておきましょう。