第９話 乱数最適実験コードと完成コード

乱数最適実験コード

#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);
int l;
clock_t hj,ow,sa,sam=1000000; //clock_t型の宣言、プログラム開始時間を取得するための変数
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;
　　 int lkr;
　　 for(l=0;l<200;l++){
　　　　　cout<<l+1<<"回目の試行"<<endl;
　　　　　hj=clock();
　　　　　syokika(n,k);
　　　　　zh(n,p,q);
　　　　　//ts(x,n,p,q);
　　　　　cout<<n<<"次魔方陣が"<<f(k,x,n,0,0,p,q)<<"個生成されました。"<<endl;
　　　　　ow=clock();
　　　　　sa=ow-hj;
　　　　　if(sa<sam){
　　　　　　　 sam=sa;
　　　　　　　 lkr=l;
　　　　　}
　　　　　if(sa<4000){
　　　　　　　 cout<<"４秒以内に魔方陣を１００個生産したシード値は"<<lkr<<"で"<<(double)sam/1000<<"そのときの時間は秒です。"<<endl;
　　　　　}
　　 　 　else{
　　　　　　　cout<<"４秒以内では魔方陣は１００個生成できませんでした。"<<endl;
　　　　　}
　　 }
　　 cout<<lkr<<" "<<(double)sam/1000<<endl;
　　 cout<<"魔方陣生成にかかった最短時間は"<<(double)sa/1000<<"秒です。"<<endl;
　　 cout<<"プロジェクト終了"<<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){
　　 ow=clock();
　　 sa=ow-hj;
　　 if(sa>4000 || sa>sam)return(cn);
　　 int i,j,s,t,w,v;
　　 s=q[g];
　　 t=p[g];
　　 if(s==n-1 && t==n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-1 && t==0){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][n-1-i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　if(s==0 && t==n-2){
　　　　　w=0;
　　　　　for(i=0;i<n-2;i++)w+=x[s][i];
　　　　　w+=x[s][n-1];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-2 && t==0){
　　　　　w=0;
　　　　　for(i=0;i<n-2;i++)w+=x[i][t];
　　　　　w+=x[n-1][t];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s>0 && s<n-1 && t==n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[s][i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-1 && t>0 && t<n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][t];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　if(g+1<n*n){
　　　　　　　 cn=f(k,x,n,cn,g+1,p,q);
　　　　　}
　　　　　else{
　　　　　　　 h(x,n);
　　　　　　　 cn++;
　　　　　　　 if(cn==100)return(cn);
　　　　　}
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 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;
　　　　　cn=f(x,n,cn,g+1);
　　　　　if(sa>4000 || sa>sam)return(cn);
　　　　　if(cn==100)return(cn);
　　　　　tobi:;
　　　　　if(v==1)k[i-1]=0;
　　 }
　　 return(cn);
}
参考ダウンロード添付ファイル
このプログラムによって、
次の乱数最適シード値を発見しました。

その結果、私のパソコンでは６次までは４秒以内に、
魔方陣を１００個生産できるようになりました。

完成コード
#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,sa; //clock_t型の宣言、プログラム開始時間を取得するための変数
　　 hj=clock();
　　 syokika(n,k);
　　 zh(n,p,q);
　　 //ts(x,n,p,q);
　　 cout<<n<<"次魔方陣が"<<f(k,x,n,0,0,p,q)<<"個生成されました。"<<endl;
　　 ow=clock();
　　 cout<<"魔方陣生成にかかった最短時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
　　 cout<<"プロジェクト終了"<<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];
　　 if(s==n-1 && t==n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-1 && t==0){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][n-1-i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　if(s==0 && t==n-2){
　　　　　w=0;
　　　　　for(i=0;i<n-2;i++)w+=x[s][i];
　　　　　w+=x[s][n-1];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-2 && t==0){
　　　　　w=0;
　　　　　for(i=0;i<n-2;i++)w+=x[i][t];
　　　　　w+=x[n-1][t];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s>0 && s<n-1 && t==n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[s][i];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　cn=f(k,x,n,cn,g+1,p,q);
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 if(s==n-1 && t>0 && t<n-1){
　　　　　w=0;
　　　　　for(i=0;i<n-1;i++)w+=x[i][t];
　　　　　w=n*(n*n+1)/2-w;
　　　　　if(w<1 || w>n*n)return(cn);
　　　　　if(k[w-1]==1)return(cn);
　　　　　x[s][t]=w;
　　　　　k[w-1]=1;
　　　　　if(g+1<n*n){
　　　　　　　 cn=f(k,x,n,cn,g+1,p,q);
　　　　　}
　　　　　else{
　　　　　　　 h(x,n);
　　　　　　　 cn++;
　　　　　　　 if(cn==100)return(cn);
　　　　　}
　　　　　k[w-1]=0;
　　　　　return(cn);
　　 }
　　 int ii,iii;
　　 if(n==5)srand(129);
　　 if(n==6)srand(118);
　　 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;
　　　　　cn=f(x,n,cn,g+1);
　　　　　if(cn==100)return(cn);
　　　　　tobi:;
　　　　　if(v==1)k[i-1]=0;
　　 }
　　 return(cn);
}
参考ダウンロード添付ファイル


改良結果



粘り強く実験を続ければ、
7次や８次でも数秒で１００個生産できるようになるかも知れませんが、
６次までできるようになったことに満足して第20講を終了します。
後に、一般種法や細胞構成法などを学ぶと、
100次魔方陣でも生成できるようになります。
第20講の終了は、同時に
『eclipse c言語 c++ 入門 初心者 使い方 基礎から応用まで 第２部』
の終わりを意味します。
講義は、第３部へと進展することになります。
第３部第21講では、並び換えを考えます。