番号付け替えによる魔方陣自動性プログラム例
#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 **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);
}
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;
}
参考ダウンロード添付ファイル
実行結果
改良前が
ですから、８１倍の高速化に成功したことになります。
改良の影響は、次数が上がるほどあり、
５次ではおそらく１万倍以上速くなっているはずです。
おそらくというのは、改良前で５次を実験中ですが、
２時間たった今でもまだ結果が出ていないからです。
そして、６次ではより以上の高速化が実現できているはずですが、
それでも、６次魔方陣では歯は立ちません。
さらなる改良が必要です。
改良に入る前に、次話でコードの解説をしましょう。
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;
}
の特に最後の２つが？？ですよね。
