第１９講 特殊種による魔方陣ソフトの高速化
第７話 特殊種による魔方陣作成ソフトソース例と解説

void f2(char g){
　　if(s==1)return;
　　int i,j,k,h,wa,kk,kkk,m,xx,yy,hh;
　　yy=a1[y[g]][x[g]];
　　array<String^>^ w=gcnew array<String^>(16);
　　rand();
　　rand();
　　kk=rand()%n;
　　m=n/2;
　　for(i=0;i<n;i++){
　　　　kkk=(kk+i)%n;
　　　　a2[y[g]][x[g]]=kkk;
　　　　xx=a2[y[g]][x[g]];
　　　　h=1;
　　　　hh=0;
　　　　if(p[yy][xx]==0){
　　　　　　p[yy][xx]=1;
　　　　　　hh=1;
　　　　}
　　　　else{
　　　　　　h=0;
　　　　}
　　　　if(h==1){
　　　　　　if(g<n){
　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　if(a2[y[g]][x[g]]==a2[j][j]){
　　　　　　　　　　　　h=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　　　if(h==1){
　　　　　　if(x[g]==n-y[g]-1 && g>n-1){
　　　　　　　　if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
　　　　　　　　if(n%2==1)if(a2[y[g]][x[g]]==a2[m][m])h=0;
　　　　　　　　if(h==1 && y[g]>0){
　　　　　　　　　　for(j=0;j<y[g];j++){
　　　　　　　　　　　　if(a2[y[g]][x[g]]==a2[j][n-j-1]){
　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　　　if(h==1){
　　　　　　if(n%2==1 && g>2*n-2){
　　　　　　　　if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][n-y[g]-1])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[n-x[g]-1][x[g]])h=0;
　　　　　　}
　　　　　　if(n%2==0 && g>2*n-1){
　　　　　　　　if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][n-y[g]-1])h=0;
　　　　　　　　if(h==1)if(a2[y[g]][x[g]]==a2[n-x[g]-1][x[g]])h=0;
　　　　　　}

　　　　　　if(h==1 && g>2*n-2 && x[g]>0){
　　　　　　　　for(j=0;j<x[g];j++){
　　　　　　　　　　if(a2[y[g]][x[g]]==a2[y[g]][j]){
　　　　　　　　　　　　h=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}

　　　　}

　　　　if(h==1){
　　　　　　if(g>3*n-4){
　　　　　　　　if(h==1 && y[g]>0){
　　　　　　　　　　for(j=0;j<y[g];j++){
　　　　　　　　　　　　if(a2[y[g]][x[g]]==a2[j][x[g]]){
　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　　　if(h==1){
　　　　　　if(g<n*n-1){
　　　　　　　　f2(g+1);
　　　　　　}
　　　　　　else{
　　　　　　　　for(j=0;j<n;j++){
　　　　　　　　　　for(k=0;k<n;k++){
　　　　　　　　　　　　w[k]=(n*a1[j][k]+a2[j][k]+1).ToString();
　　　　　　　　　　}
　　　　　　　　　　dataGridView1->Rows->Add(w);
　　　　　　　　}　　
　　　　　　　　for(j=0;j<16;j++)w[j]=L"";
　　　　　　　　dataGridView1->Rows->Add(w);
　　　　　　　　s++;
　　　　　　　　if(s==1000)return;
　　　　　　}
　　　　}
　　　　if(hh==1)p[yy][xx]=0;
　　}
}


（コピーペースト用


void f2(char g){
if(s==1)return;
int i,j,k,h,wa,kk,kkk,m,xx,yy,hh;
yy=a1[y[g]][x[g]];
array<String^>^ w=gcnew array<String^>(16);
rand();
rand();
kk=rand()%n;
m=n/2;
for(i=0;i<n;i++){
kkk=(kk+i)%n;
a2[y[g]][x[g]]=kkk;
xx=a2[y[g]][x[g]];
h=1;
hh=0;
if(p[yy][xx]==0){
p[yy][xx]=1;
hh=1;
}
else{
h=0;
}
if(h==1){
if(g<n){
for(j=0;j<g;j++){
if(a2[y[g]][x[g]]==a2[j][j]){
h=0;
break;
}
}
}
}
if(h==1){
if(x[g]==n-y[g]-1 && g>n-1){
if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
if(n%2==1)if(a2[y[g]][x[g]]==a2[m][m])h=0;
if(h==1 && y[g]>0){
for(j=0;j<y[g];j++){
if(a2[y[g]][x[g]]==a2[j][n-j-1]){
h=0;
break;
}
}
}
}
}
if(h==1){
if(n%2==1 && g>2*n-2){
if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][n-y[g]-1])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[n-x[g]-1][x[g]])h=0;
}
if(n%2==0 && g>2*n-1){
if(a2[y[g]][x[g]]==a2[x[g]][x[g]])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][y[g]])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[y[g]][n-y[g]-1])h=0;
if(h==1)if(a2[y[g]][x[g]]==a2[n-x[g]-1][x[g]])h=0;
}

if(h==1 && g>2*n-2 && x[g]>0){
for(j=0;j<x[g];j++){
if(a2[y[g]][x[g]]==a2[y[g]][j]){
h=0;
break;
}
}
}

}

if(h==1){
if(g>3*n-4){
if(h==1 && y[g]>0){
for(j=0;j<y[g];j++){
if(a2[y[g]][x[g]]==a2[j][x[g]]){
h=0;
break;
}
}
}
}
}
if(h==1){
if(g<n*n-1){
f2(g+1);
}
else{
for(j=0;j<n;j++){
for(k=0;k<n;k++){
w[k]=(n*a1[j][k]+a2[j][k]+1).ToString();
}
dataGridView1->Rows->Add(w);
}
for(j=0;j<16;j++)w[j]=L"";
dataGridView1->Rows->Add(w);
s++;
if(s==1)return;
}
}
if(hh==1)p[yy][xx]=0;
}
}


）

解説
ピンクの部分が今回のメインです。
　　　　hh=0;
　　　　if(p[yy][xx]==0){
　　　　　　p[yy][xx]=1;
　　　　　　hh=1;
　　　　}
　　　　else{
　　　　　　h=0;
　　　　}
で直交条件を満たしているか、検査しています。
p[yy][xx]が１のときが碁石をおいていない状態に対応し、
１のときが碁石がおいてある状態を指しています。
　　　　if(hh==1)p[yy][xx]=0;
は、for文でiをインクリメントする(増やす)際に碁石を取り除いてみます。
ピンクによって、同じ場所に碁石が重複しないようにしているのです。
それで、直交条件が満たされるわけです。

今回の改良によって、私のパソコンで魔方陣を１０００個作るのに
４次なら約１．９秒、５次なら約２．１秒になりました。
前回の3次・４次魔方陣作成改良版では、
４次は約１２．１秒、５次は約３８２７秒かかりましたから、
４次では約６．３倍、５次では約１８２２倍速くなりました。
７次以降なら作成速度は軽く１０万倍を超えるでしょう。
しかし、それでも７次以降では歯が立ちません。
７次以降を作らせるには、特殊種法から一般種法へと歩を進めなければならないわけですが、
特殊種法でも少し改良すると７次や８次ぐらいなら作れるようになります。

第１９講第６話へ 第１９講第８話へ



VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座