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);
}
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==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);
}
参考ファイル
今回の改良も
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==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;
}
を削ったことです。
改良前
対角線改良後
逆対角線改良後
少しずつ速くなっています。
さて、次の改良は
